완전 탐색 개요

완전탐색 개요

 

정답이 될 가능성이 있는 모든 후보 (candidates)를 체계적(반복문, 재귀, 비트마스크 등)으로 확인하는 알고리즘

 

다른말로 브루트 포스 ( brute force ) 라고도 한다.

---

탐색 알고리즘과 완전탐색의 개념을 혼동하는 경우가 있어 각각 정리해보았다.

 

 

탐색 알고리즘 과 완전 탐색의 구분

 

---

대표적인 탐색 (search) 알고리즘 

 

- 선형 탐색 O(n)

리스트를 처음부터 하나하나 비교해가며 탐색

 

- 이진 탐색 O(logn)

리스트를 정렬 후 가운데 값을 비교한다. 비교한 값이 찾는 값보다 클 경우 오른쪽 1/2 구간을 탐색한다. 나머지를 배제 이 과정을 반복한다.

 

- 비선형 탐색 (DFS, BFS)

너비 우선 탐색, 깊이 우선 탐색

---

완전 탐색

 

구현 방법에 따라 구분

 

대표적인 3가지

 

- 반복문

- 재귀

- 비트마스크

 

구현 방법이므로 3가지를 혼용 하며 사용할 수 있다.

---

여기서 생각해야 할 것은

 

1. 어떤 문제가 완전탐색 문제인가 파악 할 수 있어야 한다는 것.

 

2. 정답이 될 수 있는 모든 후보들을 나열하는 것

 

3. 문제에 따라 적합한 구현 방법 적용.

 

(for문이 2개 이상 중첩될 경우 실행 시간 제약에 걸릴 수 있다. 이 경우 재귀를 이용하여 해결)