완전탐색

윤·2023년 9월 24일

Exhaustive search algorithm brute force 완전탐색

알고리즘

목록 보기

2/23

완전탐색

모든 경우의 수를 시도하는 방법. 무식하게 모든 경우의 수를 탐색해보는 알고리즘이다. 브루트-포스 알고리즘(Brute-Force) 라고도 한다.

직관적이어서 이해가 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.

특별한 알고리즘이라기보단, 문제를 푸는 방법 이라고 생각하는게 편하다.

하지만 문제 해결 알고리즘을 사용할 때, 기본적으로 중요한 두가지 규칙 있다.
1. 문제를 해결할 수 있는가
2. 효율적으로 동작하는가

무식한 브루트포스 방식으로 1번은 만족하겠지만, 경우의 수와 실행 시간이 비례하기 때문에 2번을 만족하는 것이 어려울 수 있다.

따라서 완전탐색 기법을 사용할 때에는 그 문제에 대한 파악이 중요하다.

가능한 모든 가짓수를 대략적으로 계산한다.
어떤 방법으로 구현할 지 생각해본다(단순 for문, 순열, 재귀, BFS/DFS 등)
실제 답을 구할 수 있는지 적용한다.

완전탐색 기법

위의 2번에 적용할 수 있는 기법에 대해 알아보자.
1. 단순 브루트포스
2. 비트마스크
3. 순열
4. BFS/DFS
5. 재귀 함수
6. 백트래킹(Backtracking)

1. 브루트 포스(Brute-Force)

단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법
전체 풀이의 일부분으로 이용하며, 이 방법만을 사용하는 문제는 거의 나오지 않는다.

2. 비트마스크(bitmask)

2진수를 활용하는 컴퓨터의 연산을 이용하는 방식
각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용하게 사용이 가능

3. 순열(Permutation)

완전 탐색의 대표적인 유형
임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법
즉, 순서가 중요!
[1,2,3]과 [3,2,1]이 차이가 있듯이, 같은 데이터가 입력된 수열이지만 그 순서에 따라 의미가 있고 이 순서를 통해 연결되는 이전/다음 수열을 찾아낼 수 있는 경우를 계산할 수 있다
서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N!이다.
시간복잡도가 O(N!)으로 높은 시간 복잡도를 가진다. 따라서 이 방법은 문제에서 주어진 N의 크기를 고려해야 한다. (한자리 수 정도)

4. BFS/DFS

그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법
약간의 난이도가 있는 문제로 완전 탐색 + BFS/DFS 문제가 많이 나온다. 단순한 길 찾기 문제에서는 BFS/DFS만 이용해도 충분하지만, 주어진 도로에 장애물이 존재하는 등 추가적인 작업이 필요할 때 이를 완전 탐색으로 해결하고 BFS/DFS를 이용하는 방식이다.

5. 재귀 함수(Recursive)

비트마스크와 마찬가지로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용하게 사용
포함 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그대로 함수를 호출

6. 백트래킹(Backtracking)

재귀를 이용한 완전 탐색
현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 생기면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그대로 방금 왔던 길을 되짚어가는 알고리즘
가지치기(Pruning)라고도 표현하는데, 불필요한 가지를 쳐내면서 답을 찾아내서 붙은 이름
보통 반복문의 횟수를 줄일 수 있어 효율적이지만, 최악의 경우에는 여전히 완전 탐색을 하기 때문에 경로를 찾아 가지치는 방법이 효율성을 결정하게 된다.

모든 경우의 수를 탐색하여 최적의 결과를 찾아가는 완전탐색에서 백트래킹은 해결책을 찾아가는 도중에 막히게 되면 다시 돌아가 다른 경로로 탐색을 하여, 결국 모든 가능한 경우의 수를 탐색해 해결책을 찾아가는 방식으로 사용된다.
주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현

완전탐색 실전 사용 예시

보통 완전 탐색 문제는 난이도가 쉬워 초급자들도 큰 어려움을 겪지 않는다. 하지만 약간의 난이도가 있는 문제에서, 알고리즘 공부를 어느정도 한 사람들이 "이게 완전 탐색이라고?" 하는 반응을 보이는 경우가 꽤나 있다.
문제를 봤을 때 완전 탐색이지 않을까?라는 생각을 한 번 정도는 해볼 만한 경우들을 보자.

1. 입력으로 주어지는 데이터(N)의 크기가 매우 작다.
보통 n = 10만, 20만 같은 크기를 주는 경우가 많다.
하지만 대부분 완전 탐색 문제는 N의 크기가 매우 작다.
순열, 조합 같은 문제들은 완전탐색이므로 기본적으로 시간복잡도가 O(2^n)이거나 O(N!)이므로 N의 크기가 매우 작아야 한다.

2. 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있다.
답의 범위가 제한적인 경우에, 답을 고정시켜 놓고 주어진 조건들이 답에 적합한지 역으로 확인해보는 방법이다. 가능한 답을 모두 확인하는 과정에서 완전 탐색이 이용된다.

3. 여러 문제 조건 중 한 조건을 고정시키면 문제 풀이가 간단해진다.
조건에 따라 가지 수가 바뀌기 때문에, 하나의 조건을 고정하여 문제를 해결한 후 범위를 좁게 설정하여 문제를 해결하는 것이다.