뭐든지 다 알아보자

백트래킹이란??

- 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행

- 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다.

- DFS(깊이 우선 탐색) 기반

VER 1.0

import sys

def backtracking():
    if len(s) == m:
        print(' '.join(map(str, s)))
        return
    for i in range(1, n+1):
        if visited[i] == True:
            continue
        visited[i] = True
        s.append(i)
        backtracking()
        s.pop()
        visited[i] = False


n,m = map(int, sys.stdin.readline().split())
s = []

visited =[False for i in range(n+1)]

backtracking()

재귀함수와 CONTINUE문 , return 문을 적절한 위치에 사용하여 반환시키도록 한다.

VER2.0

import itertools
import sys

n,m = map(int, sys.stdin.readline().split())

res = [i for i in range(1,n+1)]

array = itertools.permutations(res, m)
for i in array:
    for j in i:
        print(j , end = ' ')
    print()

array 안은 2차원 배열 ==> 2중 for문을 돌리자

itertools의 라이브러리에서 

permutations , combinations, combinations_with_replacement 

이 3가지의 라이브러리 확인해본다.

import itertools
import sys

n, m = map(int, sys.stdin.readline().split())
nums = [i for i in range(1, n+1)]

array = itertools.permutations(nums, m) #중복된 조합은 제외
#itertools의 permutations함수를 사용해서 풀이
#Permutations 는 배열에서 원하는 길이에 맞는 모든 조합을 구하는 함수이다.
for i in array:
    for j in i:
        print(j, end = ' ')
    print()
print('=======================')
array2 = itertools.combinations(nums,m) #중복된 조합 모두 포함

for i in array2:
    for j in i:
        print(j, end = ' ')
    print()
print('=======================')
array3 = itertools.combinations_with_replacement(nums,m)
#중복된 조합 모두 포함 , 1 1 / 2 2 등 본인의 조합도 포함하기
#(nums, m)
for i in array3:
    for j in i:
        print(j, end = ' ')
    print()

import sys

def fact(n):
    res = 1
    if n==1 or n==0:
        return 1
    else:
        for i in range(n,1, -1):
            res*=i
        return res
m = int(sys.stdin.readline())
A = list(str(fact(m)))

if '0' in A:
    for i in range(len(A)-1,-1,-1):
        if A[i]!='0':
            # print(i)
            print(len(A)-i-1)
            break
else:
    print(0)

==> range문 거꾸로 돌리는걸 통하여 뒤에서부터 0이아닌것의 리스트 인덱스값 구하기

import sys


M = int(sys.stdin.readline())
res = []
for k in range(M):
    N = int(sys.stdin.readline())
    B = {}
    for i in range(N):
        A = list(map(str, sys.stdin.readline().split()))

        if A[1] in B.keys():
            B[A[1]] += 1
        else:
            B[A[1]] = 1
    count = 1
    for key in B.keys():
        count *= B[key] +1
    res.append(count-1)
for i in res:
    print(i)

1. 딕셔너리 관련 식

B = {}  ==> B 딕셔너리 선언

A = list(map(str, sys.stdin.readline().split())) ==> A리스트에 데이터타입이 str로 저장

A =['sunglasses' , 'eyewear']

if A[1] in B.keys() : ==> B딕셔너리의 KEY 값에 A[1] 값이 있다면

     B[A[1]] += 1 ==> A[1]의 KEY값의 value 값에 1을 더한다.

else: ==> key값이 존재하지 않는다면

   B[A[1]] = 1 ==> 1로 초기화 한다.

EX ) 입력값 :

hat header

sung eye

tur header

B:{'header' : 2 , 'eye' : 1}

2. 조합구하기

count =1

for key in B.keys():

     count = count * (B[key] + 1) ==> 1* (2+1) * (1+1) = 6

count-1 ===> 겹치는거 제외해야하므로 -1을 처리한다.

import sys

def fact(n):
    if n==1 or n==0:
        return 1
    else:
        res=1
        for i in range(n, 0, -1):
            res*=i
        return res
n = int(sys.stdin.readline())
result = []
for i in range(n):
    A = list(map(int , sys.stdin.readline().rstrip().split()))
    A = sorted(A , reverse=True)
    res = fact(A[0])//(fact(A[0]-A[1])*(fact(A[1])))
    result.append(res)
for k in result:
    print(k)

sorted(A, reverse=True) ==> 내림차순으로의 정리 

29C13 = 67863915

import sys

def fact(n):
    if n==1 or n==0:
        return 1
    else:
        res=1
        for i in range(n, 0, -1):
            res*=i
        return res
A = list(map(int , sys.stdin.readline().rstrip().split()))
res = fact(A[0])//(fact(A[0]-A[1])*(fact(A[1])))

print(res%10007)

import sys

def fact(n):
    if n==1 or n==0:
        return 1
    else:
        res=1
        for i in range(n, 0, -1):
            res*=i
        return res
A = list(map(int , sys.stdin.readline().rstrip().split()))
print(fact(A[0])//(fact(A[0]-A[1])*(fact(A[1]))))

range(n,0,-1) ==> 거꾸로 출력할때 쓴다 ==> (n,0,-1) 와 같이 거꾸로일때 0은 기존의 +와는 다르게 0까지 계산한다는 점이 있다.

factorial 계산시 ==> for i in range(n, 0, -1) : res*=i ==> 시간복잡도에 있어 유리하다.

import sys
import math

N = int(sys.stdin.readline())

A=list(map(int,sys.stdin.readline().rstrip().split()))

res = []
a= A[0]
for i in range(1,len(A)):
    b = math.gcd(a,A[i])
    c = a//b
    d = A[i]//b
    print('{}/{}'.format(c,d))

gcd 함수 잘 기억하기정도?

import sys
import math

N = int(sys.stdin.readline())
maxs=0
A = []
for i in range(N):
    a = int(sys.stdin.readline())
    A.append(a)
A= sorted(A)
res = []
for i in range(1,len(A)):
    if i==1:
        maxs = A[i]-A[i-1]
    maxs = math.gcd(A[i]-A[i-1] , maxs)

for i in range(1,int(maxs**0.5)+1):
    if maxs%i == 0:

        if ( (i**2) != maxs) :
            res.append(maxs // i)
        if i!=1:
            res.append(i)
print(*sorted(list(set(res))))

1. 수학적 지식 활용

ex) 6 34 38 

maxs = 34-6

1) 34-6 = [28 gcd 28] ==>28

2) 38-34 = [4 gcd 28] ==> 4

1을 제외한 약수구하면 나머지값이 모두 동일하다.

2. 약수구하기 시간복잡도 생각에 따른 식 세우기

1) for i in range(1, int(8**0.5)+1) = for i in range(1, 3)

2) maxs = 8 ==> 8%(1과2) ==0

3) 1**2 = 1 != maxs(8) ==> 8//1 = 8 

4) 2**2 = 4 != maxs(8)  != 1 ==> 8//2 =4 , 2 추가 

3. 리스트 출력하는 애스터리스크(Asterlisk) ==> *

a = [1,2,3,4]

print(*a) ==> 1 2 3 4