가능한 모든 경우를 전부 해보는 방법. 최적화가 하나도 없으니 답을 못 찾을 일이 없고, 그래서 다른 모든 방법의 기준선이 된다. 네 자리 비밀번호를 만 개 전부 넣어보는 것이 완전 탐색이다.
느리다는 이유로 얕보기 쉽지만, 코딩테스트에서는 모든 문제에서 가장 먼저 검토해야 할 접근이다. N의 범위가 작으면 완전 탐색이 곧 정답이고, 크더라도 완전 탐색으로 부분 점수는 챙길 수 있다.
순열과 조합 네 갈래
무엇을 어떻게 고르느냐로 넷으로 갈린다. 순서 있게 나열하면서 같은 것을 또 써도 되면 중복 순열이라 O(Nᴹ), 같은 것을 못 쓰면 순열이라 O(N! / (N-M)!)이다. 순서를 따지지 않고 고르기만 하면 중복 조합과 조합이 된다.
문제를 읽고 이 넷 중 어느 것인지부터 정하면 절반은 끝난다. N과 M이 최대 7이라면 7⁷은 약 82만이라 완전 탐색으로 충분하다는 판단이 바로 선다.
재귀 함수의 골격
네 경우 모두 재귀 함수의 정의가 같은 꼴이라, 함수를 어떻게 정의할지가 문제 풀이의 절반이다.
// k번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다
static void rec(int k) {
if (k == M + 1) { // M개를 다 골랐다. 한 가지 방법을 완성했다
// 결과 처리
return;
}
for (...) { // k번째 자리에 올 수 있는 후보들
selected[k] = 후보;
rec(k + 1);
}
}selected 배열을 M + 1 크기로 잡는 이유는 다 채웠는지 확인하려고 한 칸 더 두는 것이다.
네 경우의 차이는 안쪽 for문이 어디서부터 어디까지 도느냐뿐이다. 중복을 막으려면 이미 쓴 값을 건너뛰고, 순서가 상관없으면 직전에 고른 값보다 큰 것만 본다.
가지치기를 얹은 백트래킹
여기에 가지치기를 얹은 것이 백트래킹이다. 내려가다가 이 가지는 답이 될 수 없다는 것이 확실해지면 더 내려가지 않고 돌아 나온다. 탐색 공간을 잘라내니 훨씬 빨라진다. N-Queen 문제가 대표적이어서, 퀸을 놓다가 이미 공격당하는 자리가 나오면 그 아래는 전부 볼 필요가 없다.
높은 시간복잡도
시간복잡도가 대체로 높다. 반드시 답을 찾고 구현이 단순하다는 장점을 그 하나가 다 깎아먹는다. 그래도 만점 풀이가 안 떠오를 때 부분 점수를 얻는 길로는 남는다.