2. 완전 탐색

📚 완전 탐색(Brute Force) 이란?

: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 -> 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법

: 완전 탐색 자체로는 알고리즘이라고 부르긴 그렇고, 문제 푸는'방법'이라고 이해하면 편할 것 같다.

: 이 방식은 절대 답을 못 구하는 경우는 없으므로 나름 강력한 방법!

 

예를 들어 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해보자. 이 자물쇠의 암호를 해결하기 위해  0000 ~ 9999까지 모두 시도해보는 것이다.(최대 10,000번의 시도로 해결 가능)

🧩 완전 탐색 방법

완전 탐색 자체가 알고리즘은 아니기 때문에 완전 탐색 방법을 이용하기 위해서 여러 알고리즘 기법이 이용된다. 주로 이용되는 기법들은 다음과 같다. 

기본적으로 완전 탐색은 N의 크기가 작을 때 이용이 되기 때문에 보통 시간 복잡도가 지수승이나, 팩토리얼 꼴로 나올 때 많이 이용된다. 

 1. 단순 Brute-Force

어느 기법을 사용하지 않고 단순히 for문과 if문 등으로 모든 case들을 만들어 답을 구하는 방법이다. 이는 아주 기초적인 문제에서 주로 이용되거나, 전체 풀이의 일부분으로 이용하며, 따라서 당연히 대회나 코테에서는 이 방법만을 이용한 문제는 거의 나오지 않는다. 

2. 비트마스크(Bitmask)

bitmask는 2진수를 이용하여 연산하는 방식이다. 완전 탐색에서 비트마스크는 문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용이 가능하다. 

 

길이가 4인 [1, 2, 3, 4] 리스트가 존재한다고 가정한다. 여기서 몇가지 값을 뽑아 부분집합을 만들어보려고 한다.

(1), (2), (3), (4), (1, 2), (1, 3) ...

대충 이렇게 많은 경우의수가 존재할 수 있다. 지금은 리스트의 길이가 4여서 크게 무리는 없지만 만약에 200이라면? 말이 달라진다. 엄청난 메모리가 소모될 것이고 오버헤드가 발생할 확률이 높다.

이때 바로 bitmask를 사용하여 좀더 효율적으로 표현할 수 있다. 

[ 1, 2, 3, 4 ]
--------------
  1  1  1  1
  1  1  1  0
  1  1  0  1
  1  1  0  0 
  ....

리스트의 길이만큼에 해당하는 bit list 를 생성하고, 존재(1) 아니면 (0)으로 표기한다. 이것을 다시 10진수로 바꿔서 표현할 수도 있다. 

그렇다면 부분집합을 배열이 아니라 정수로도 관리할 수 있다. 그리고 이때 바로 비트연산자를 통해서 삽입, 삭제, 조회 등을 효율적으로  진행할 수 있다.

3. 재귀 함수 

재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식이다.

위에서 언급한 부분집합 문제를 예로 들면, 만들고자 하는 부분집합을 S'라고 할 때, S' = { } 부터 시작해서 각 원소에 대해서 해당 원소가 포함이 되면 S'에 넣고 재귀 함수를 돌려주고, 포함이 되지 않으면 S'를 그대로 재귀 함수에 넣어주는 방식이다. 

비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 이용된다. 

4. 순열

완전 탐색의 대표적인 유형이다. 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N! 이므로 완전 탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 한다. 

순열에 원소를 하나씩 채워가는 방식이며, 재귀 함수를 이용하거나 C++에서는 next_permutation이라는 아주 유용한 함수를 제공하고 있다. 

5. BFS / DFS

약간의 난이도가 있는 문제로 완전 탐색 + BFS/DFS 문제가 많이 나온다. 대표적인 유형으로 길 찾기 문제가 있다. 단순히 길을 찾는 문제라면 BFS/DFS만 이용해도 충분하지만, 주어진 도로에 장애물을 설치하거나, 목적지를 추가하는 등의 추가적인 작업이 필요한 경우에 이를 완전 탐색으로 해결하고 나서, BFS/DFS를 이용하는 방식이다. 

 

 

 

 

🎲 참고 

https://paintycode.tistory.com/48

[알고리즘] 완전탐색 (Exhaustive Search)

https://rebro.kr/59

완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘