완전탐색, 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다.
완전 탐색 자체로는 알고리즘이라기 보다는 문제를 푸는 기법이며, 답으로 가능한 경우의 수가 많을 때 시간복잡도가 크므로 경우의 수가 작은지 파악하는 것이 중요하다.
완전 탐색 기법
- 단순 Brute-force
- 비트마스크 Bitmask
- 재귀 함수
- 순열 Permutation
- BFS / DFS
단순 Brute-force
어느 기법을 사용하지 않고 단순히 반복문과 조건문 등으로 모든 case 들을 만들어 답을 구하는 방법이다.
비트마스크
2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이며, 문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우 유용하다.
재귀 함수
만들고자 하는 부분집합을 S’ 라고 할 때, S’ = { } 부터 시작해서 각 원소에 대해서 해당 원소가 포함이 되면 S’ 에 넣고 재귀 함수를 돌려주고, 포함이 되지 않으면 S’ 를 그대로 재귀 함수에 넣어주는 방식이며, 비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 이용한다.
순열
완전 탐색의 대표적인 유형이며, 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N! 이므로 완전 탐색을 이용하기 위해서는 N이 한자리수 정도는 되어야 한다.
순열에 원소를 하나씩 채워가는 방식이며, 재귀 함수를 이용하거나 permutaion 를 만들어주는 라이브러리를 이용한다.
DFS/BFS
난이도가 있는 문제로 완전 탐색 + BFS/DFS 문제가 많이 나온다. 대표적인 유형으로 길 찾기 문제가 있다. 단순히 길을 찾는 문제라면 BFS/DFS 만 이용해도 충분하나, 장애물을 설치하거나 목적지를 추가하는 등의 추가적인 작업이 필요한 경우에 백트래킹 알고리즘도 섞어서 BFS/DFS 를 이용한다.
