완전탐색 - 다 해보는 것이 기준선이다

열쇠 꾸러미에 열쇠가 서른 개 달려 있고 열어야 할 문은 하나다. 어느 게 맞는지 모른다면 방법은 하나뿐이다. 하나씩 꽂아보는 것.

먼저 꾸러미를 꺼낸다

문제를 받으면 영리한 방법부터 떠올리려는 습관이 있다. 순서가 거꾸로다. 먼저 물을 것은 “다 해보면 몇 번인가”다.

이유는 둘이다.

첫째, 다 해보는 게 답인 경우가 정말 많다. 열쇠가 서른 개면 최악이 서른 번이고, 그건 1초도 안 걸린다. 여기서 더 영리해질 이유가 없다.

둘째, 세어보기 전에는 영리한 방법이 필요한지도 모른다. 후보가 몇 개인지 모르는 채로 최적화부터 하면, 필요 없는 복잡함을 들여놓고 그걸 평생 유지한다.

그래서 완전탐색은 못 미더워서 마지막에 쓰는 방법이 아니라, 판단의 출발점이다. 이 방법의 비용을 알아야 “이걸로 충분한가”에 답할 수 있다.

후보가 몇 개인지 센다

세는 법은 단순하다. 고를 자리마다 몇 가지가 가능한지 곱한다.

열쇠 서른 개 중 하나를 고르는 건 서른 가지다. 그런데 문이 두 개고 각 문에 맞는 열쇠를 짝지어야 한다면 30 × 29다. 자리가 늘 때마다 곱이 하나씩 붙는다.

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (nums[i] + nums[j] == target) { … }   // 모든 쌍을 본다

두 수를 고르는 모든 경우다. n이 1,000이면 약 50만 번이고 이건 순식간이다. n이 10만이면 50억 번이고, 이건 안 끝난다. 같은 코드인데 n 하나로 갈린다.

폭발하는 모양을 알아본다

문제가 되는 건 자리가 늘어나는 종류다. 이때는 후보가 곱셈으로 불어난다.

아래 두 줄이 완전탐색이 무너지는 자리다. 표기가 2ⁿ이나 n!이 되는 순간 n을 하나 늘리는 것만으로 시간이 배로 뛴다. 늘어나는 모양에 이름을 붙이는 일이 여기서 값을 한다. 이 표기를 알아보면 “이건 다 해보면 안 되는 문제”라는 판단이 코드를 짜기 전에 선다.

아닌 길은 일찍 접는다

후보가 많아도 전부 끝까지 볼 필요는 없다. 가망 없는 갈래는 도중에 접는다. 이걸 가지치기라고 한다.

예를 들어 예산 100 안에서 물건을 골라 담는 문제라면, 담는 도중에 이미 100을 넘겼다면 그 아래는 볼 필요가 없다. 뒤에 무엇을 더 담든 값은 줄지 않기 때문이다.

이 판단 한 줄로 트리의 한 가지가 통째로 사라진다. 남은 후보가 줄어드는 게 아니라 가지에 매달린 모든 잎이 한꺼번에 사라진다.

⚠️ 가지치기는 답을 바꾸지 않아야 한다. “여기 아래에는 답이 절대 없다”가 확실할 때만 자른다. “아마 없을 것 같다”로 자르면 그건 알고리즘이 아니라 추측이고, 어느 입력에서 틀리는지 알 수 없게 된다.

접고 되돌아 나온다

가지치기를 하려면 갔다가 돌아 나오는 구조가 필요하다. 한 갈래를 골라 들어가고, 막히면 골랐던 것을 취소하고 다음 갈래로 간다. 이 꼴을 백트래킹이라 부른다.

void pick(int idx, int sum) {
    if (sum > TARGET) return;        // 여기가 가지치기
    if (idx == n) { check(sum); return; }

    chosen[idx] = true;
    pick(idx + 1, sum + nums[idx]);  // 고르고 들어간다
    chosen[idx] = false;             // 되돌린다
    pick(idx + 1, sum);              // 안 고르고 들어간다
}

chosen[idx] = false 한 줄이 “되돌아 나오기”다. 이 줄을 빼먹으면 앞 갈래에서 고른 흔적이 다음 갈래에 묻어가서, 답이 조용히 틀린다. 오류 메시지도 없다.

그래프를 깊이 우선으로 도는 것이 정확히 이 모양이고, 실제로 백트래킹은 후보들이 만드는 트리를 깊이 우선으로 도는 일이다.

다 해봐도 되는 크기를 감으로 안다

실무에서 쓸 만한 감각 하나를 못 박아 두면 좋다. 요즘 컴퓨터는 단순한 연산을 초당 대략 1억 번 한다.

이 하나로 판단이 선다.

• n = 1,000에서 O(n²)이면 100만 번. 괜찮다.
• n = 100,000에서 O(n²)이면 100억 번. 안 된다.
• n = 20에서 2ⁿ이면 100만 번. 괜찮다.
• n = 40에서 2ⁿ이면 1조 번. 안 된다.

정확한 숫자를 외울 필요는 없다. 자릿수만 맞으면 판단이 갈린다. 100만이면 하고, 100억이면 다른 길을 찾는다. 이 감각이 없으면 될 일에 시간을 쓰거나 안 될 일에 뛰어든다.

실무에서: 완전탐색은 채점 기준이다

실무 코드에 완전탐색이 그대로 남는 일은 드물다. 그런데 개발 과정에서는 거의 매번 쓰인다. 정답이 무엇인지 알려주는 기준이기 때문이다.

정교한 방법은 대개 어딘가를 건너뛴다. 건너뛴 게 정말 봐도 안 되는 것이었는지는 눈으로 확인이 안 된다. 이때 쓰는 방법이 이렇다.

• 작은 입력을 잔뜩 만들어 완전탐색과 빠른 방법의 답을 맞춰본다.
• 두 답이 갈리는 입력이 나오면, 그게 곧 최소 재현 케이스다.
• 갈리지 않으면 최적화가 답을 안 바꿨다는 근거가 쌓인다.

성능 튜닝을 할 때도 같은 순서가 안전하다. 느려도 확실한 것부터 만들고, 그걸 기준 삼아 빠른 걸 검증한다. 빠른 것부터 만들면 틀렸을 때 틀린 줄을 모른다.

여기에 하나 더. 완전탐색이 안 끝난다는 사실 자체가 정보다. “다 해보면 100억 번”이라는 계산이 나왔다면, 그 문제는 후보를 줄이는 성질이 어딘가에 반드시 있다는 뜻이다. 뒤에 볼 방법들은 전부 그 성질을 찾아내 쓰는 이야기다.

정리

• 문제를 받으면 먼저 다 해보면 몇 번인지 센다. 세어보기 전에는 더 나은 방법이 필요한지도 모른다.
• 세는 법은 고를 자리마다 가능한 수를 곱하는 것이다. 자리가 늘면 곱이 붙는다.
• 2ⁿ과 n!이 나오면 완전탐색은 무너진다. 하나 늘 때 배로 뛰기 때문이다.
• 가지치기는 답이 절대 없는 갈래만 자른다. “아마 없을 것 같다”로 자르면 알고리즘이 아니다.
• 초당 1억 번이라는 감각 하나로 대부분의 판단이 선다. 자릿수만 맞으면 된다.
• 완전탐색은 버리는 게 아니라 빠른 방법이 맞는지 채점하는 기준으로 남는다.

다음 글은 가장 많이 쓰이면서 가장 자주 오해받는 절차를 본다. 줄을 세우는 일, 정렬이다.