- 완전탐색은 모든 경우를 살펴보기에 시간이 오래 걸립니다. 시간을 단축시키고 싶다면백트래킹을 사용합니다.백트래킹이란 탐색 과정에서 더 이상 답이 되지 않는 분기를 발견했을 때 되돌아가는 기법을 의미합니다.
- 완전탐색은 크게 반복문 / 재귀 / 큐로 구현할 수 있습니다.
관련 알고리즘
반복문
순열 조합 DFS
재귀
큐
BFS
순열 permutation
n개의 수 중 r개를 뽑아 줄을 세우는 방법의 수
1. 라이브러리 사용하기
from itertools import permutations
arr = [0, 1, 2, 3]
for i in permutations(arr, 4):
print(i)
2. 직접 구현하기
chk = [False] * (N + 1)
ans = []
def permutation(n, m):
if m == 0:
print(*ans)
else:
for i in range(1, n + 1):
if not chk[i]:
chk[i] = True
ans.append(i)
permutation(n, m - 1)
ans.pop()
chk[i] = False
permutation(N, M)
중복 순열 permutaion of repetition
n개의 수 중 중복을 허용하여 r개를 뽑아 줄을 세우는 방법의 수
1. 라이브러리 사용하기
from itertools import product
arr = [0, 1, 2 ,3]
for i in product(arr, repeat = 2):
print(i)
2. 직접 구현하기
ans = []
def permutation(n, m):
if not m:
print(*ans)
else:
for i in range(1, n + 1):
ans.append(i)
permutation(n, m - 1)
ans.pop()
permutation(N, M)
조합 combination
n개의 수 중 r개를 뽑는 방법의 수
1. 라이브러리 사용하기
from itertools import combinations
arr = [0, 1, 2, 3]
for i in combinations(arr, 2):
print(i)
2. 직접 구현하기
ans = []
def combination(n, m, idx):
if not m:
print(*ans)
else:
for i in range(idx + 1, n + 1):
ans.append(i)
combination(n, m - 1, i)
ans.pop()
combination(N, M, 0)
중복 조합 repeated combination
n개의 수 중 중복을 허용하여 r개를 뽑는 방법의 수
1. 라이브러리 사용하기
from itertools import combinations_with_replacement
arr = [0, 1, 2, 3]
for i in combinations_with_replacement(arr, 2):
print(i)
2. 직접 구현하기
ans = []
def combination(n, m, idx):
if not m:
print(*ans)
else:
for i in range(idx, n + 1):
ans.append(i)
permutation(n, m - 1, i)
ans.pop()
combination(N, M, 1)
