[알고리즘] 완전탐색

뜻

가능한 경우의 수를 모두 조사해서 정답을 찾는 방법.

활용

완전 탐색 알고리즘 동작 과정

1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산
2. 가능한 모든 방법을 다 고려
3. 실제 답을 구할 수 있는지 적용

완전탐색의 종류:

1. Brute Force : 
   반복 / 조건문을 통해 가능한 모든 방법을 단순히 찾는 경우 (시간이 오래걸림)
2. Backtracking :
   현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 알고리즘.
   분할정복을 이용한 기법으로 재귀함수를 이용하고 해를 찾아가는 도웆ㅇ 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다.
3. Permutation :
   순열은 임의의 수열이 주어졌을 때 그것을 다른 순서로 연산하는 방법이다. 서로 다른 N개를 일렬로 나열하는 순열의 경우는 N!이므로 완전탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 한다.
4. Bit Mask :
   2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이다. 완전 탐색에서 비트마스크는 문제에서 나올 수 있는 모든 경우의 수가 각각 원소가 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용 가능하다.
   

   

5. 재귀함수 :
   재귀함수를 통해 문제를 만족하는 경우들을 만들어가는 방식이다.
6. DFS/BFS + 완전탐색 : 
   난이도가 있는 문제롤 많이 나온다. 단순히 길을 찾는 문제이면 DFS/BFS만 이용해도 충분하지만, 주어진 도로에 장애물을 설치하거나 목적지를 추가하는 등의 추가적인 작업이 필요한 경우에 이를 완전 탐색으로 해결하고 나서 DFS/BFS를 이용해야 한다.