✔️ 완전탐색 알고리즘이란?
완전탐색은 가능한 경우의 수를 모두 조사해서 정답을 찾는 방법으로, 무식하게 가능한 것을 다 해보겠다는 의미로 Brute Force라고도 부른다.
✔️ 완전탐색 알고리즘 활용
완전탐색 알고리즘 동작 과정
- 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산
- 가능한 모든 방법을 다 고려
- 실제 답을 구할 수 있는지 적용
완전탐색의 종류
1) Brute Force 기법
Brute Force 기법은 반복 / 조건문을 통해 가능한 모든 방법을 단순히 찾는 경우를 말한다. 예를 들어, 4자리로 된 번호 자물쇠를 푼다고 할 때 최악의 경우 10000 * 1초 = 대략 166분 (컴퓨터의 연산 속도 : 대략 1초에 1억) 이 걸릴 수 있다.
2) 백트래킹 (Backtracking)
백트래킹 (Backtracking)은 현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 알고리즘이다. 분할정복을 이용한 기법으로, 재귀함수를 이용하고 해를 찾아가는 도중 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다.
3) 순열 (Permutation)
순열은 임의의 수열이 주어졌을 때 그것을 다른 순서로 연산하는 방법이다. 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N!이므로 완전 탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 한다.
from itertools import permutations
permutations(arr, n)
# permutations 이용
# n개씩 순열 조합해서 모든 경우의 수 판정4) 비트 마스크 (Bit Mask)
비트 마스크 (Bit Mask)는 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이다. 완전 탐색에서 비트마스크는 문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용 가능하다.
예를 들어, 원소가 5개인 집합의 모든 부분집합을 구하는 경우를 생각해보면, 어떤 집합의 부분집합은 집합의 각 원소가 해당 부분집합에 포함되거나 포함되지 않는 두 가지 경우만 존재한다. 따라서 5자리 이진수를 이용하여 각 원소의 포함 여부를 체크할 수 있다.
5) 재귀함수
재귀함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식이다.
위에서 언급한 부분집합 문제를 예로 들면, 만들고자 하는 부분집합을 S'라고 할 때, S' = {} 부터 시작해서 각 원소에 대해서 해당 원소가 포함이 되면 S'에 넣고 재귀함수를 돌려주고 포함이 되지 않으면 S'를 그대로 재귀함수에 넣어주는 방식이다.
비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 사용된다.
6) DFS/BFS
약간 난이도가 있는 문제로 완전탐색 + DFS/BFS 문제가 많이 나온다. 예를 들어, 단순히 길을 찾는 문제라면 DFS/BFS만 이용해도 충분하지만, 주어진 도로에 장애물을 설치하거나 목적지를 추가하는 등의 추가적인 작업이 필용한 경우에 이를 완전 탐색으로 해결하고 나서 DFS/BFS를 이용해야 한다.
👉 참고
알고리즘 - 완전탐색(Exhaustive Search)
완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘
