완전탐색
완전탐색(Exclusive Search)이란?
- 이름에서 나타내듯, 모든 경우의 수를 탐색하여 최적의 결과를 찾는 방법을 의미한다.
- 모든 가능성을 고려하므로 항상 최적의 해를 찾을 수 있다. 그러나 경우의 수가 많아지면 시간과 메모리의 부담이 커질 수 있다.
완전탐색 알고리즘의 종류
1. 브루트포스
- 단순한 반복문(for)와 조건문(if)로 모든 경우의 수를 만들어 답을 구하는 방법
- 장점 : 가능한 모든 경우를 검사하므로 예상된 결과를 얻을 수 있음
- 단점 : 경우의 수가 많을 경우 시간이 오래 걸림
2. 비트마스크
- 모든 경우의 수를 이진수로 표현하고 비트 연산을 통해 원하는 결과를 빠르게 얻는 알고리즘
- 장점 : 이진수 연산을 사용하므로 계산 속도가 빠름
- 단점 : 경우의 수가 많아질수록 메모리 사용량이 늘어남
- 나올 수 있는 모든 경우의 수가 각 원소가 포함되거나 포함되지 않는 두가지 선택으로 구성되는 경우 유용하게 사용할 수 있음
- 예시) 원소가 n개인 집합의 모든 부분 집합을 구할 때, 각 원소가 포함되는지/않는지를 0과 1로 구분하여 확인할 수 있다.
[1,2,3,4,5] => 11111
[2,3,4,5] => 11110
[1,2,5] => 10011
[2] => 000103. 백트래킹
- 결과를 얻기 위해 진행하던 도중 막히게 되면 그 지점으로 다시 돌아가서 다른 경로를 탐색함으로써 모든 경우의 수를 탐색하여 해결책을 찾음
- 장점 : 경우의 수를 줄이면서 모든 경우를 탐색할 수 있음
- 단점 : 재귀 함수를 이용하므로 스택 오버플로우가 발생할 수 있음
4. 순열
- 순열 (서로 다른 n개 중 r개를 선택하여 나열하는 방법)을 이용하여 모든 경우의 수를 탐색
- 장점 : 경우의 수가 적을 때 유용
- 단점 : 경우의 수가 많으면 시간이 오래 걸림
- 경우의 수는 N!이며, 완전 탐색을 이용하려면 N이 한자리 수는 되어야 한다. 순열에 원소를 하나씩 채우는 방식이며 재귀 함수를 이용할 수 있다.
5. 재귀 함수
- 자기 자신을 호출하여 모든 가능한 경우의 수를 확인하며 최적의 해답을 얻음
- 장점 : 코드가 간결하고 이해하기 쉬움
- 단점 : 스택 오버플로우가 발생할 수 있음
- 비트마스크와 마찬가지로 주로 각 원소가 포함되는/않는 두 가지 선택을 가질 때 이용된다. 피보나치 수열이 대표적인 예시
6. DFS/BFS
- 깊이 우선 탐색(DFS; Depth First Search)
: 루트 노드에서 시작하여 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법 - 너비 우선 탐색(BFS; Breadth First Search)
: 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법 - 장점 : 미로찾기 등에 유용
- 단점 : 최악의 경우 모든 노드를 방문해야하므로 시간이 오래 걸림
완전탐색의 시간복잡도
[비교] 비트마스크 > DFS/BFS > 브루트포스 > 재귀함수 > 순열 > 백트래킹
- 비트마스크 : O(2^n*n)
- DFS/BFS : O(N+E) // N : Node의 개수, E : 간선의 개수
- 브루트포스 : O(nm) // 경우의 수 * 방법1개를 시도하는데 걸리는 시간복잡도
- 재귀함수 : O(n)
- 순열 : O(n!)
- 백트래킹 : 최악의 경우, O(n!)
Ref.
https://adjh54.tistory.com/196
https://hstory0208.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89Exhaustive-search%EC%9D%B4%EB%9E%80
