1. 브루트 포스 / 완전 탐색
직역하면 '난폭한 힘'으로, 모든 경우의 수를 탐색하여 원하는 결과를 찾아내는 방식의 알고리즘이다. 완전탐색이라고도 한다.
쉽게 말하면 모든 경우를 무식하게 일일히 나열한다는 의미이다. 이는 반드시 답을 찾을 수 있고, 구현이 단순하다는 장점이 있으나 복잡도(complexity)에 매우 민감하다는 단점을 가지고 있다. 암호학에서도 브루트 포스 공격은 생각보다 유효한 의미를 가진다.
예를 들어 4자리 비밀번호를 구할 때, 0000부터 9999까지 하나하나 대입해보고 있는 방식은 매우 비효율적일 것이다.
때문에 완전탐색을 이용할 만한 문제인지 잘 파악하는 것이 중요하다.
2. 방식
1. Brute-force
단순 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법.
2. 순열(Permutation)
서로 다른 N개의 원소를 일렬로 나열하는 방법. 경우의 수 N!에서 N이 한자리 수는 되어야 한다.
3. 재귀호출
자기 자신을 호출하는 방법. 재귀함수는 매개변수를 통해서 종료 조건, 즉 Base Condition 에 점차 다가가도록 설계하는 것이 원칙이다. 그렇지 않다면 재귀 함수는 무한 루프에 빠질 수 있다.
모든 경우의 수에서 각각의 원소가 포함되거나, 포함되지 않는 두 가지 상황으로만 구성되는 경우 사용한다.
4. 비트마스크(Bitmask)
비트 연산을 통해 부분 집합을 표현하는 방법. 여기서 비트 연산이란 AND, OR, NOT, XOR, Shift 연산을 의미한다.
재귀 호출처럼, 모든 경우의 수에서 각각의 원소가 포함되거나, 포함되지 않는 두 가지 상황으로만 구성되는 경우 사용한다.
5. BFS, DFS
BFS(너비 우선 탐색)은 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방법이다. 주로 큐로 구현한다.
DFS(깊이 우선 탐색)은 하나의 요소를 방문하고 그 요소의 자식 요소를 우선하여 따라 내려가며 방문하는 방법이다. 주로 스택이나 재귀로 구현한다.
BFS, DFS의 대표적인 예시로는 길 찾기 문제가 있는데, 단순 길 찾기에는 BFS, DFS만 써도 무방하나 장애물이 있다거나 목적지를 추가하는 등 추가적인 연산이 필요할 때는 완전탐색을 병용하기도 한다.
2. 완전 탐색을 사용하는 경우와 사용 방법
완전탐색을 사용하는 경우
1. 입력으로 주어지는 데이터(N)의 크기가 매우 작다.
완전탐색 문제는 N의 크기에 크게 영향을 받으므로 당연히 N의 크기가 매우 작아야 한다.
2. 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있다.
답의 범위가 아주 제한적인 경우에는, 임의로 답을 고정시켜놓고 주어진 조건들이 답에 적합한지 역으로 확인해보는 방법을 이용해볼 수 있다.
3. 여러 문제 조건 중 한 조건을 고정시키면 문제 풀이가 간단해진다.
완전탐색 사용 방법
선형 구조일 경우
- 주어진 문제를 선형 구조로 구조화한다.
- 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
- 구성된 해를 정리한다.
비선형 구조일 경우
BFS, DFS를 기본적으로 사용한다.
3. 백트래킹(BackTracking)과의 차이
백트래킹은 재귀적으로 현재 상태가 제한 조건을 위배하는지 판단하여, 해당 방향이 해답이 될 가능성이 없다, 즉 '유망하지 않다'고 판단되면, 되돌아가 다시 해를 탐색하는 방법이다.
불필요한 가지를 탐색하지 않기 때문에 가지치기(pruning)라고도 한다. 이때 재귀의 방식을 사용하여 DFS를 진행하며 가망있는 가지만 탐색한다. 대표적인 백트래킹 문제의 예시로 N-Queen문제가 있다.
얼핏보면 백트래킹과 DFS가 재귀의 방식을 사용하기에 DFS와 백트래킹을 같거나 완전히 포함되는 개념이 아닌가 생각하기 쉽지만, 차이점이 있다.
DFS는 모든 경우의 수를 헤아린다. 그러나 백트래킹은 불필요한 경우의 수는 완전히 배제한다. 결과적으로 DFS는 모든 노드를 방문하는 것이 목적이지만, 백트래킹은 유망하지 않은 경우의 수를 줄이는 것이 목적이다.
즉, DFS와 백트래킹은 유사한 부분이 있으며 기본적으로 사용 목적이 다르지만 두 기법을 혼용하여 사용하는 것이 가능하다. 완전히 다른 개념이 아니라 재귀 호출을 통한 기법 중 하나 이기 때문이다.
출처
https://hongjw1938.tistory.com/78
https://hongjw1938.tistory.com/88
https://rebro.kr/59
https://hcr3066.tistory.com/26
