자료구조
[자료구조] 완전탐색 (Exhaustive search)
Voyage_dev
2024. 4. 14. 21:14
완전탐색 (Exhaustive search)
⇒ 모든 가능한 경우의 수를 탐색 하여 최적의 결과를 찾는 방법
모든 알고리즘 문제에서 가장 중요한 것 → 정확한 답 → 가장 확실한 방법 및 컴퓨터의 빠른 연산속도를 활용하는 가장 좋은 접근 방법
문제를 처음 접하면 반드시 완전탐색으로 풀 수 있는가를 생각해 보자. 모든 문제에서 완전탐색으로 답을 내지 못 한 문제는 복잡도를 더 이상 줄일 수 없기 때문이다.
완전탐색 종류
알고리즘 종류 설명 장점 단점
| 브루트 포스 | ‘모든 경우의 수를 탐색’하면서 원하는 결과를 얻는 알고리즘을 의미. | 가능한 모든 경우를 다 검사하기 때문에 예상된 결과를 얻을 수 있음 | 경우의 수가 많을 경우 시간이 오래 걸림 |
| 비트마스크 | ‘모든 경우의 수를 이진수로 표현‘하고 ‘비트 연산’을 통해 원하는 결과를 빠르게 얻는 알고리즘을 의미. | 이진수 연산을 이용하여 계산 속도가 빠름 | 경우의 수가 많아질수록 메모리 사용량이 늘어남 |
| 백트래킹 | 결과를 얻기 위해 진행하는 도중에 ‘막히게 되면’ 그 지점으로 다시 돌아가서 ‘다른 경로를 탐색’하는 방식을 의미. 결국 모든 가능한 경우의 수를 탐색하여 해결책을 찾는다 | 경우의 수를 줄이면서도 모든 경우를 탐색할 수 있음 | 재귀 함수를 이용하기 때문에 스택 오버플로우가 발생할 가능성 있음 |
| 순열 | ‘순열을 이용하여 모든 경우의 수를 탐색‘하는 방법. 순열은 서로 다른 n개 중에서 r개를 선택하여 나열하는 방법을 의미 | 경우의 수가 적을 때 사용하면 유용함 | 경우의 수가 많을 경우 시간이 오래 걸림 |
| 재귀함수 | ‘자기 자신을 호출‘하여 모든 가능한 경우의 수를 체크하면서 최적의 해답을 얻는 방식을 의미. | 코드가 간결하며, 이해하기 쉽습니다. | 스택 오버플로우가 발생할 가능성이 있음 |
| DFS/BFS | 깊이 우선 탐색(DFS: Depth-First Search)- 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미.너비 우선 탐색(Breadth-First Search: BFS)- 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 의미. | 미로 찾기 등에 유용함 | 최악의 경우, 모든 노드를 다 방문해야 하므로 시간이 오래 걸림 |
- 브루트 포스 : for문을 이용하여 처음부터 끝까지 탐색하는 방법
- 비트 마스크 : 이진수 표현을 자료구조로 쓰는 기법 (AND, OR, XOR, SHIFT, NOT)
- 백트래킹 : 분할정복을 이용한 기법, 재귀함수를 이용, 해를 찾아가는 도중에 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다.
- 재귀함수 : 함수 내에서 함수 자기 자신을 계속해서 호출하는 것
- 순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수
- BFS(너비 우선 탐색)
- DFS(깊이 우선 탐색)
완전탐색 시간 복잡도
알고리즘 시간 복잡도
| 브루트 포스 | O(nm) |
| 비트마스크 | O(2^n * n) |
| 백트래킹 | 최악의 경우, O(n!) |
| 순열 | O(n!) |
| 재귀함수 | O(n) |
| DFS/BFS | O(V+E) |
- 비트마스크 > DFS/BFS > Brute-Force > 재귀함수 > 순열 > 백트래킹
연습
Reference
[Java/알고리즘] 완전 탐색(Exhaustive Search) 이해하기 -1 : 정의 및 종류
[Algorithm] 완전탐색 (Exhaustive Search)