완전탐색(Complete Search)

알고리즘을 공부하다보면 알고리즘 패러다임(algorithm paradigm)이라는 것을 배우게 된다. 위키피디아의 정의에 따르면 패러다임(paradigm)이란 ‘어떤 한 시대 사람들의 견해나 사고를 근본적으로 규정하고 있는 테두리로서의 인식 체계, 또는 사물에 대한 이론적인 틀이나 체계를 의미하는 개념’이다. 비슷하게 알고리즘 패러다임이란 여러 알고리즘들을 묶을 수 있는 개념이 아닐까라고 조심스럽게 생각해본다. 대표적인 알고리즘 패러다임으로는 완전탐색(Complete search), 분할정복(Divide-and-conquer), 동적계획법(Dynamic programming), 탐욕법(Greedy method) 등이 있다. 이들은 모두 많은 알고리즘의 토대가 되는 기본 틀을 제공하므로 문제를 잘 해결하고 싶은 사람이라면 꼭 알아두어야 한다. 이번 포스트에서는 알고리즘의 설계할 때 가장 먼저 생각해봐야 하는 완전탐색에 대해서 간략하게 소개하고자 한다.

완전 탐색이란?

어떤 문제를 해결하고자 할 때, 시도해볼 수 있는 가장 단순한 방법은 무엇일까? 예를 들어 비밀번호가 무엇인지 잊어먹은 자물쇠의 비밀번호가 4자리라고 하자. 자물쇠의 비밀번호를 찾는 가장 쉬운 방법은 무엇일까? 아마도 비밀번호가 될 수 있는 모든 경우를 다 해보면 알아낼 수 있지 않을까? 비밀번호가 4자리이므로 \(10^4=10000\)번 시도해보면 된다. 물론 시간은 걸리겠지만 모든 경우를 다 해보면 확실히 답을 찾을 수 있다.

이와 같이 답이 될 수 있는 모든 경우를 만들어보면서 답을 찾는 방법을 완전탐색이라고 한다. 흔히 Brute-force search, Exhaustive search, Complete search라는 표현을 쓴다. 완전탐색은 모든 경우를 다 고려해본 후 결론(답)에 이르기 때문에 속도가 매우 느리다. 하지만 모든 경우를 다 해볼수 있을 정도로 입력이 작다면 충분히 시도해볼만한 방법이다. 그리고 완전 탐색 알고리즘을 설계하면서 답의 구조나 패턴을 파악할 수 있어 더 좋은 알고리즘을 설계하는데 도움을 줄 수도 있고, 다른 방식으로 설계한 알고리즘이 작은 입력에서 정확하게 동작하는지 검증하는 용도로도 사용할 수 있다.

완전 탐색은 보통 반복문 또는 재귀 함수로 구현한다. 일반적으로 반복문으로 작성하는 것이 속도면에서 유리하겠지만, 다양한 형태의 문제를 보다 간결하게 구현하는데에는 재귀 함수가 좋다. 완전탐색에 대한 개념을 좀더 확실하게 하고 싶다면 아래 문제들을 풀어보면 좋을 것 같다.

연습 문제

BOJ 2309 일곱 난쟁이 (문제 보기)

가능한 모든 조합 \(\binom n k = \binom 9 7\)을 모두 만들어보면 된다.

BOJ 1182 부분 집합의 합 (문제 보기)

집합의 각 원소를 고르거나 고르지 않는 모든 경우 ( \(2^N\))를 모두 만들어보면 된다.

BOJ 1759 암호 만들기 (문제 보기)

모든 문자들을 사전순으로 정렬한 후 \(\binom C L\)의 경우를 모두 만들어보고, 최소 한 개 모음과 최소 두 개의 자음으로 구성되어 있는지 확인하면 된다.

BOJ 10974 모든 순열 (문제 보기)

c++ STL std::next_permutation 함수를 사용하면 편한 문제이지만, 직접 재귀 함수로 모든 순열을 만들어보는 것도 좋다.

BOJ 10971 외판원 순회2 (문제 보기)

모든 순열(도시들의 나열)을 만들어보면 되는 문제다.

BOJ 10448 유레카 이론 (문제 보기)

세 개의 삼각수의 합이 될 수 있는 모든 경우를 미리 생성하여 그 정보를 저장해두면 된다.

BOJ 1018 체스판 다시 칠하기 (문제 보기)

보드의 각 위치에서 흰색으로 시작하는 경우와 검정색으로 시작하는 경우를 모두 따져보면 되는 문제이다.

참고 자료

• 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만
• Competive Programming 3, Steven Halim