[자료구조] 완전탐색 (Exhaustive search)

완전탐색 (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)

[알고리즘 설계] 1. 완전탐색(Exhaustive Search)

[Java/알고리즘] 완전 탐색(Exhaustive Search) 이해하기 -2 : 종류 별 이해