1. 완전탐색

가능한 경우의 수를 모두 나열하면서 원하는 답을 찾는 방법이다. 전체를 하나하나 다 따져보기 때문에 Brute-Force라고도 하는데 사전을 찾아보면 '폭력', '억지 기법 ((무차별 대입해 억지로 문제를 푸는))'라는 뜻이 있다. '10개의 서로 다른 정수 중 두 개를 택해 그 합이 최대가 되는 경우'가 완전탐색의 예가 되겠다.

대신 모든 경우를 전부 따져야 하기 때문에 경우의 수가 매우 많아지는 문제에 대해서는 제한 시간 내에 해결이 힘들 수 있다.

2. 완전탐색 알고리즘

완전탐색 기법에는 여러 알고리즘이 존재하는데, 대표적으로 아래와 같다.

2-1. 단순 Brute-Force

특별한 방법 대신 단순히 반복문과 조건문으로 모든 경우를 따지는 식이다.

2-2. 비트마스크(Bitmask)

각 원소가 A이거나 B인, 즉 두 가지 상태만을 가질 수 있을 때 사용할 수 있다. '원소가 n개인 집합의 모든 부분 집합'을 구한다면 각 원소가 포함되는지 포함되지 않는지를 0, 1로 구분하여 배열에 저장해둘 수 있다.

2-3. 재귀함수

비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 사용하면 좋다. 포함이 되면 해당 원소를 넣고 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식이다.

2-4. 순열

순열(permutation)은 서로 다른 N개를 일렬로 나열하는 방법(경우의 수)를 말한다. 재귀함수를 이용하거나 C++의 next_permutation()함수를 이용할 수 있다.

2-5. 너비우선탐색(BFS), 깊이우선탐색(DFS)

너비우선탐색(Breadth-first search, BFS)는 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식이며, 깊이우선탐색(depth-first search, DFS)는 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식이다.
이들은 길 찾기 등에 주로 쓰이는 알고리즘으로, 단순 길찾기에는 BFS/DFS만 써도 무방하나 장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색을 병용하기도 한다.

3. 주의점

완전탐색을 풀 때는 주로 입력의 개수(N)이 작을 때가 좋다. 시간복잡도가 $O(2^N)$ 혹은 $O(N!)$이기 때문에 N의 크기가 증가할수록 복잡도는 폭발적으로 증가한다.

참고한 블로그(하단 링크 참조)에서는 '답의 범위가 작고, 임의의 답이 조건을 만족하는지 역추적할 수 있을 때' 그리고 '여러 조건 중 하나를 고정시키면 풀이가 간단해질 때' 완전탐색 기법을 사용하길 권장했다.

4. 예시문제

아래의 문제들은 완전탐색으로 풀이할 수 있는 문제들이다. 다만 해당 방법이 완전탐색이 맞는지 아닌지는 확실하지 않다...

4-1. 모음사전 (프로그래머스)

👉 문제 링크
🔍 풀이방식.
길이를 1씩 늘려가며 해당 자릿수에 가능한 모든 경우를 찾았다. 모음의 개수가 5개 뿐이라 가능했다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<char> vowels = { 'A', 'E', 'I', 'O', 'U' };
vector<string> dict;

void makeDict(string word, int len)
{
	if (len == word.length())
	{
		dict.push_back(word);
		return;
	}

	for (char vowel : vowels)
		makeDict(word + vowel, len);
}

int solution(string word) {
	for (int len = 1; len <= 5; len++)
		makeDict("", len);

	sort(dict.begin(), dict.end());

	for (int i = 0; i < dict.size(); i++)
	{
		if (word == dict[i])
			return (i + 1);
	}
}

4-2. 피로도 (프로그래머스)

👉 문제 링크
🔍 풀이방식
역시 던전의 크기가 최대 8로 작은 수이므로 모든 경우를 다 따져도 $8!$밖에 되지 않는다. 따라서 next_permutation() 함수로 순열을 통해 모든 경우를 나열해 풀이했다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(int k, vector<vector<int>> dungeons)
{
    sort(dungeons.begin(), dungeons.end());

    int physical = k;
    int cnt = 0;
    int maxCnt = -1;
    do
    {
        for (int i = 0; i < dungeons.size(); i++)
        {
            if (physical < dungeons[i][0])
                break;

            physical -= dungeons[i][1];

            if (physical <= 0)
                break;

            cnt++;
        }

        if (maxCnt < cnt)
            maxCnt = cnt;
        physical = k;
        cnt = 0;
    } while (next_permutation(dungeons.begin(), dungeons.end()));

    return maxCnt;
}

4-3. 카펫 (프로그래머스)

👉 문제 링크
🔍 풀이방식
세로 길이를 하나씩 늘려가며 가능한 경우를 찾았다. 가로 길이가 세로 길이보다 크거나 같은 조건을 반복문의 탈출 조건으로 걸었다.

def solution(brown, yellow):
    temp = (brown + 4)/2
    height = 1
    width = temp - height
    
    while width >= height:
        if yellow == (width * height - brown):
            return [width, height]
        else:
            height += 1
            width = temp - height

참고자료

• Rebro, "완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘," Rebro의 코딩 일기장
• "깊이 우선 탐색," 위키피디아
• "너비 우선 탐색," 위키피디아