여러 기업들의 코딩 테스트를 준비하다보면 완전 탐색을 해야하는 문제가 많은데, 그런 문제를 만났을때 가장 직관적이기도 하고 쉽게 생각나는 것이 주어진 조건에 맞는 순열 혹은 조합을 모두 구해서 체크하는 것이다.
하지만 생각은 빨리 나는데 구현을 처음 해보면 은근 쉽지가 않다. 그래서 구현 방법 3가지를 정리해놓으려고 한다.
- itertools 모듈
파이썬의 itertools 모듈을 이용하면 쉽게 사용할 수 있다.
다른 상세한 내용은 구글링해도 될 듯하여 간단한 코드만 보고 넘어가자.
2. 재귀 함수
itertools를 사용하면 되긴하지만, 다른 언어나 외부 모듈을 사용하지 못하는 경우 혹은 공부를 위해서 구현해보고 싶은 사람은 직접 구현해야 한다.
일단 첫 번째로 재귀 함수로 구현하는데, 한 가지 원소를 뽑고 그 원소를 제외한 리스트로 조합 혹은 순열을 구하는 것이다.
combination([1,2,3,4],2) = ([1] + combination([2,3,4],1)) and
([2] + combination([3,4],1)) and ([3] + combination([4],1))
permutation([1,2,3,4],2) = ([1] + permutation([2,3,4],1)) and
([2] + permutation([1,3,4],1)) and ([3] + permutation([1,2,4],1)) and
([4] + permutation([1,2,3],1))
와 같은 논리로 해결한다.
코드는 다음과 같다.
3. dfs / bfs
완전 탐색은 조합이나 순열을 사용하지 않고도 dfs, bfs같은 탐색 알고리즘을 통해서도 구현 가능하다.
조합, 순열도 같은 방식으로 구현할 수 있다.
코드는 dfs로 구현한 것이다.
중복 순열, 중복 조합의 경우에는 다른 구현 방법이 있겠지만, 그냥 그대로 구한 다음에 중복된 원소를 빼주는 과정만 추가하면 간단할 것 같다.
