가능한 경우의 수를 모두 나열하면서 원하는 답을 찾는 방법이다. 전체를 하나하나 다 따져보기 때문에 Brute-Force라고도 하는데 사전을 찾아보면 '폭력', '억지 기법 ((무차별 대입해 억지로 문제를 푸는))'라는 뜻이 있다. '10개의 서로 다른 정수 중 두 개를 택해 그 합이 최대가 되는 경우'가 완전탐색의 예가 되겠다.
대신 모든 경우를 전부 따져야 하기 때문에 경우의 수가 매우 많아지는 문제에 대해서는 제한 시간 내에 해결이 힘들 수 있다.
완전탐색 기법에는 여러 알고리즘이 존재하는데, 대표적으로 아래와 같다.
특별한 방법 대신 단순히 반복문과 조건문으로 모든 경우를 따지는 식이다.
각 원소가 A이거나 B인, 즉 두 가지 상태만을 가질 수 있을 때 사용할 수 있다. '원소가 n개인 집합의 모든 부분 집합'을 구한다면 각 원소가 포함되는지 포함되지 않는지를 0, 1로 구분하여 배열에 저장해둘 수 있다.
비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 사용하면 좋다. 포함이 되면 해당 원소를 넣고 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식이다.
순열(permutation)은 서로 다른 N개를 일렬로 나열하는 방법(경우의 수)를 말한다. 재귀함수를 이용하거나 C++의 next_permutation()
함수를 이용할 수 있다.
너비우선탐색(Breadth-first search, BFS)는 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식이며, 깊이우선탐색(depth-first search, DFS)는 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식이다.
이들은 길 찾기 등에 주로 쓰이는 알고리즘으로, 단순 길찾기에는 BFS/DFS만 써도 무방하나 장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색을 병용하기도 한다.
완전탐색을 풀 때는 주로 입력의 개수(N)이 작을 때가 좋다. 시간복잡도가 혹은 이기 때문에 N의 크기가 증가할수록 복잡도는 폭발적으로 증가한다.
참고한 블로그(하단 링크 참조)에서는 '답의 범위가 작고, 임의의 답이 조건을 만족하는지 역추적할 수 있을 때' 그리고 '여러 조건 중 하나를 고정시키면 풀이가 간단해질 때' 완전탐색 기법을 사용하길 권장했다.
아래의 문제들은 완전탐색으로 풀이할 수 있는 문제들이다. 다만 해당 방법이 완전탐색이 맞는지 아닌지는 확실하지 않다...
👉 문제 링크
🔍 풀이방식.
길이를 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);
}
}
👉 문제 링크
🔍 풀이방식
역시 던전의 크기가 최대 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;
}
👉 문제 링크
🔍 풀이방식
세로 길이를 하나씩 늘려가며 가능한 경우를 찾았다. 가로 길이가 세로 길이보다 크거나 같은 조건을 반복문의 탈출 조건으로 걸었다.
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