완전 탐색이란?
답을 찾기 위해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법이다. 완전 탐색 자체가 알고리즘은 아니고 문제를 푸는 방법이라고 할 수 있다.
시간이 오래 걸린다는 단점이 존재
완전 탐색 기법
완전 탐색 방법을 이용하기 위해 여러 알고리즘 기법들이 이용된다.
- 재귀 함수
- 순열
- 조합
재귀 함수
브루트 포스 알고리즘으로 코드를 구현한다면 대게 for문으로 같은 동작을 반복하는 경향이 있다. 이때 반복되는 부분을 재귀 함수로 만들어서 호출해주면 코드를 간결하게 표현할 수 있으므로 유용하게 사용된다.
순열
완전 탐색의 대표적인 유형
서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N! 이므로 완전 탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 한다.
순열에 원소를 하나씩 채워가는 방식이며, 재귀 함수를 이용하거나 파이썬에서는 permutations라는 아주 유용한 도구가 존재한다.
permutations
사용법
from itertools import permutations
arr = ["A", "B", "C"]
itertools.permutations(arr, 2)
결과 : [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]리턴값
: 경우에 대한 쌍을 튜플 형식으로 반환한다.
조합
n개의 원소 중 r개를 순서 없이 골라낸 것
파이썬에서는 combinations라는 기능을 제공한다.
import itertools
arr = ['A', 'B', 'C']
nCr = itertools.combinations(arr, 2)
print(list(nCr))
결과 : [('A', 'B'), ('A', 'C'), ('B', 'C')]
chick! chick!