완전 탐색 기법
1. 단순 Brute-Force
2. 비트마스크 Bitmask
3. 재귀함수
4. 순열 (Permutation)
5. BFS/DFS
완전 탐색 기법 소개
단순 Brute-Force
- 어느 기법을 사용하지 않고, 단순히 for/if문 등으로 모든 case를 만들어 답을 구하는 방식
- 아주 기초적인 문제에 주로 이용되거나, 전체 풀이의 일부분으로 이용
비트마스크 Bitmask
-
2진수를 이용하는 컴퓨터 연산을 이용하는 방식
-
완전 탐색에서 비트마스크는 문제에 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 선택으로 구성되는 경우에 유용하게 사용 가능
-
ex) 원소가 5개인 집합의 모든 부분집합을 구하는 경우를 생각해보자.어떤 집합의 부분집합은 집합의 각 원소가 해당 부분집합에 포함되거나, 포함되지 않는 두 가지 경우만 존재한다.
따라서 5자리 이진수 (0~31)를 이용하여 각 원소의 포함 여부를 체크할 수 있다.
-
위 그림과 같이 0부터 31까지의 각 숫자들이 하나의 부분집합에 일대일로 대응된다.
재귀함수
- 재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식
- 위에서 언급한 부분집합 문제를 예로 들면, 만들고자 하는 부분집합을 S'라고 할 때, S' = { } 부터 시작해서 각 원소에 대해서 해당 원소가 포함이 되면 S'에 넣고 재귀 함수를 돌려주고, 포함이 되지 않으면 S'를 그대로 재귀 함수에 넣어주는 방식
- 비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 이용된다.
순열
- 완전 탐색의 대표적인 유형
- 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N! 이므로 완전 탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 함
- 순열에 원소를 하나씩 채워가는 방식이며, 재귀 함수를 이용하거나 C++에서는 next_permutation이라는 아주 유용한 함수를 제공
BFS/DFS
- 약간의 난이도가 있는 문제로 완전 탐색 + BFS/DFS 문제가 많이 나옴
- 대표적인 유형으로 길 찾기 문제
- 단순히 길을 찾는 문제라면 BFS/DFS만 이용해도 충분하지만, 주어진 도로에 장애물을 설치하거나, 목적지를 추가하는 등의 추가적인 작업이 필요한 경우에 이를 완전 탐색으로 해결하고 나서, BFS/DFS를 이용하는 방식
출처: https://rebro.kr/59 [Rebro의 코딩 일기장]
