완전 탐색

완전 탐색은 답이 될 수 있는 후보를 하나도 빼지 않고 전부 확인해서 답을 찾습니다. 문제를 받아 조건에 맞는 답을 돌려줍니다. 후보를 전부 보므로 답을 놓치지 않습니다. 대신 후보가 많아질수록 오래 걸립니다.

상세

완전 탐색(brute-force search, exhaustive search)은 알고리즘을 짜는 한 가지 방식입니다. 브루트 포스(brute force)라고도 부릅니다. 한 문제를 푸는 특정한 절차가 아닙니다. 여러 문제에 두루 쓰는 뼈대입니다.

이 절은 먼저 후보를 모아 놓은 범위인 탐색 공간을 봅니다. 이어서 완전 탐색이 밟는 단계를 그림과 파이썬 코드로 따라갑니다. 그다음 후보가 얼마나 불어나는지 세어 언제 이 방식을 고르는지 봅니다. 끝으로 완전 탐색에서 출발해 후보를 덜 보는 기법들을 봅니다.

탐색 공간

완전 탐색은 먼저 무엇이 후보인지 정해야 합니다. 답이 될 수 있는 후보를 모두 모은 것을 탐색 공간(search space)이라고 합니다. 탐색 공간이 정해져야 「전부 봤다」고 말할 수 있습니다.

숫자 칸이 넷인 자물쇠를 예로 들겠습니다. 한 칸에 0 부터 9 까지 열 가지 숫자가 올 수 있습니다. 칸이 넷이면 0000 부터 9999 까지 10,000 가지입니다. 이 10,000 개의 번호가 탐색 공간입니다.

칸을 하나 더 달면 번호는 100,000 가지로 열 배가 됩니다. 탐색 공간은 이렇게 입력이 조금 늘 때 크게 불어납니다. 얼마나 불어나는지는 뒤의 「후보가 불어나는 빠르기」 소절에서 셉니다.

탐색 공간을 전부 보면 답이 있을 때 반드시 찾습니다. 답이 없을 때도 「없다」고 확실히 말할 수 있습니다. 모든 후보를 확인했는데 맞는 것이 하나도 없었기 때문입니다.

만들기 · 확인하기 · 기록하기

완전 탐색은 세 가지 일을 되풀이합니다. 후보를 하나 만듭니다. 그 후보가 조건에 맞는지 확인합니다. 맞으면 답으로 기록합니다.

기록한 다음에 할 일은 문제의 종류에 따라 다릅니다. 「조건에 맞는 것이 있나」를 묻는 문제는 맞는 후보를 하나 만나면 바로 멈춥니다. 자물쇠가 열리면 나머지 번호는 돌려 볼 필요가 없습니다. 이렇게 예나 아니오로 답하는 문제를 결정 문제라고 부릅니다.

「가장 좋은 것」을 묻는 문제는 끝까지 봐야 합니다. 지금까지 본 후보 가운데 가장 좋은 것을 기억해 둡니다. 새 후보가 더 좋으면 그것으로 바꿉니다. 마지막 후보까지 봐야 기억해 둔 것이 답이 됩니다.

이런 문제가 최적화 문제입니다. 가장 짧은 경로 찾기나 가장 싼 조합 찾기가 여기 듭니다.

한 문제를 받았을 때 거치는 흐름은 아래와 같습니다. 두 종류의 문제는 답을 기록한 다음에 갈립니다.

flowchart TD
    A["후보를 하나 만든다"] --> B{"조건에 맞나"}
    B -->|예| C["답으로 기록한다 · 최적화 문제면 더 좋을 때만 바꾼다"]
    B -->|아니오| D{"남은 후보가 있나"}
    C -->|결정 문제| E["바로 멈춘다"]
    C -->|최적화 문제| D
    D -->|예| A
    D -->|아니오| F["끝 · 기록해 둔 답을 돌려준다 · 없으면 「없다」"]

반복문으로 후보 만들기

후보를 만드는 가장 흔한 도구는 반복문입니다. 후보가 두 값의 짝이면 반복문 두 개를 겹쳐 모든 짝을 만듭니다.

아래 함수는 목록에서 두 값을 골라 더한 값이 목표와 같은 짝을 찾습니다. 두 위치 i 와 j 의 짝이 후보입니다. 합이 목표와 같으면 그 짝을 돌려줍니다. 끝까지 없으면 None(값 없음)을 돌려줍니다.

def pair_sum(xs, target):
    n = len(xs)
    for i in range(n):
        for j in range(i + 1, n):
            if xs[i] + xs[j] == target:
                return (i, j)
    return None

pair_sum([3, 8, 2, 5], 7)  # (2, 3)
pair_sum([3, 8, 2, 5], 4)  # None

바깥 반복문이 첫 값을 고릅니다. 안쪽 반복문은 그 뒤의 값 가운데 둘째 값을 고릅니다. j 를 i + 1 부터 세는 까닭은 같은 짝을 두 번 보지 않기 위해서입니다. 3 과 8 의 짝을 봤으면 8 과 3 의 짝은 볼 필요가 없습니다.

[3, 8, 2, 5] 에서 목표 7 을 찾으면 여섯 짝을 차례로 봅니다. 3+8, 3+2, 3+5, 8+2, 8+5 는 7 이 아닙니다. 마지막 짝 2+5 가 7 이라 두 값의 위치 (2, 3) 을 돌려줍니다. 목표 4 는 여섯 짝을 다 봐도 없어서 None 이 나옵니다.

후보가 불어나는 빠르기

완전 탐색의 비용은 탐색 공간의 크기가 정합니다. 후보 하나를 확인하는 일에 후보 수를 곱하면 전체 일이 나옵니다. 그래서 이 소절은 후보 수를 셉니다.

후보가 어떤 모양이냐에 따라 입력이 커질 때 느는 빠르기가 크게 다릅니다. 완전 탐색에서 자주 만나는 모양은 아래 셋입니다. n 은 입력 원소의 수입니다.

짝은 앞 소절의 코드가 만든 후보입니다. 원소 네 개에서 짝은 여섯 개였습니다. 원소가 두 배가 되면 짝은 네 배쯤 됩니다.

원소마다 넣을지 뺄지 정한 묶음을 부분집합이라고 합니다. 하나도 안 넣은 빈 묶음도 부분집합에 듭니다. 원소 하나에 갈림이 둘이라 원소가 하나 늘 때마다 후보가 두 배가 됩니다.

배낭 문제는 무게 한도 안에서 가장 값진 물건 묶음을 고르는 문제입니다. 이 문제의 후보가 부분집합이라 물건이 n 개면 후보가 2ⁿ 개입니다.

아래 그림은 a, b, c 세 원소로 부분집합을 만드는 갈림입니다. 원소 하나를 정할 때마다 한 레벨 내려갑니다. 레벨마다 후보가 두 배가 되어 세 레벨을 내려가면 8 개가 됩니다.

flowchart TD
    subgraph L0["시작"]
        S["아직 아무것도 안 정함"]
    end
    subgraph L1["레벨 1 · a 를 정함 · 2개"]
        A1["a"]
        A0["빈 묶음"]
    end
    subgraph L2["레벨 2 · b 를 정함 · 4개"]
        B11["a b"]
        B10["a"]
        B01["b"]
        B00["빈 묶음"]
    end
    subgraph L3["레벨 3 · c 를 정함 · 8개"]
        C1["a b c"]
        C2["a b"]
        C3["a c"]
        C4["a"]
        C5["b c"]
        C6["b"]
        C7["c"]
        C8["빈 묶음"]
    end
    S -->|a 넣음| A1
    S -->|a 뺌| A0
    A1 -->|b 넣음| B11
    A1 -->|b 뺌| B10
    A0 -->|b 넣음| B01
    A0 -->|b 뺌| B00
    B11 -->|c 넣음| C1
    B11 -->|c 뺌| C2
    B10 -->|c 넣음| C3
    B10 -->|c 뺌| C4
    B01 -->|c 넣음| C5
    B01 -->|c 뺌| C6
    B00 -->|c 넣음| C7
    B00 -->|c 뺌| C8

모든 원소를 한 줄로 세운 순서를 순열이라고 합니다. 첫 칸에는 n 개 가운데 하나가 옵니다. 둘째 칸에는 남은 n−1 개 가운데 하나가 옵니다. 이렇게 칸마다 고를 수 있는 수를 곱해 나가면 n × (n−1) × … × 1 이 됩니다.

이 곱을 n! 로 적고 팩토리얼이라고 읽습니다. 도시를 도는 경로 찾기는 외판원 순회라고 부릅니다. 도는 순서가 곧 후보라 후보 수가 n! 입니다.

세 모양의 후보 수를 n 에 따라 늘어놓으면 아래와 같습니다.

n 이 10 에서 20 으로 두 배가 되는 동안 짝은 네 배쯤 늘었습니다. 부분집합은 1,024 배 늘었습니다. 순열은 수천억 배로 불어났습니다.

입력은 조금 커졌을 뿐입니다. 그런데 후보는 다 볼 수 없을 만큼 불어납니다. 이 현상을 조합 폭발이라고 부릅니다. 부분집합과 순열을 후보로 삼는 완전 탐색은 이 현상 때문에 작은 입력에서만 끝까지 돕니다.

비용을 적는 법

입력이 커질 때 드는 일이 어떤 빠르기로 느는지를 적는 표기가 빅오 표기법입니다. 짝을 모두 보는 앞의 코드는 O(n²) 입니다. n(n−1)/2 는 n 이 커질수록 n²/2 에 가까워지므로 n² 에 비례한다고 적습니다.

후보 하나를 확인하는 데도 일이 들면 그만큼 곱합니다. 부분집합 하나의 무게를 더하려면 원소 n 개를 훑어야 합니다. 그러면 부분집합을 모두 보는 비용은 O(n × 2ⁿ) 입니다.

최악과 최선은 문제의 종류에 따라 갈립니다. 결정 문제는 답을 일찍 만나면 일찍 끝납니다. 최악은 답이 맨 마지막 후보이거나 답이 아예 없을 때입니다. 이때는 탐색 공간을 전부 봅니다.

최적화 문제는 언제나 전부 봅니다. 마지막 후보가 더 좋을 수도 있어서 중간에 멈출 수 없습니다. 그래서 최선과 최악이 같습니다.

메모리는 후보를 다루는 방식이 정합니다. 후보를 하나씩 만들어 확인하고 버리면 지금 보는 후보 하나만큼만 듭니다. 후보를 전부 목록으로 만들어 두고 확인하면 후보 수만큼 듭니다.

부분집합과 순열은 흔히 재귀 함수로 만듭니다. 재귀는 함수가 자기 자신을 다시 부르는 것입니다. 원소 하나를 정할 때마다 한 번 더 부르므로 아직 안 끝난 호출이 n 개까지 쌓입니다. 쌓인 호출마다 메모리를 조금씩 쓰므로 후보를 하나씩 만드는 방식이어도 n 에 비례하는 메모리가 듭니다.

순차 탐색 · 가장 작은 완전 탐색

순차 탐색은 목록에서 찾는 값을 앞에서부터 하나씩 비교해 찾습니다. 목록의 값 하나하나가 후보인 완전 탐색입니다. 탐색 공간의 크기가 n 이라 비용은 O(n) 입니다.

목록이 정렬돼 있으면 사정이 달라집니다. 이진 탐색은 가운데 값과 한 번 비교해 절반의 후보를 버립니다. 찾는 값이 가운데 값보다 크면 왼쪽 절반에는 없기 때문입니다.

이진 탐색의 비교 횟수는 n 을 몇 번 반으로 나눠야 1 이 되는지와 같습니다. 이 횟수를 log n 으로 적습니다. 그래서 비용은 O(log n) 입니다.

두 방법의 차이는 문제가 가진 성질을 쓰느냐입니다. 정렬이라는 성질을 알면 보지 않고도 버릴 수 있는 후보가 생깁니다. 완전 탐색은 그런 성질을 하나도 쓰지 않는 풀이입니다.

완전 탐색을 고르는 경우

첫째는 입력이 작을 때입니다. 후보 수가 감당할 만하면 완전 탐색이 가장 짜기 쉬운 풀이입니다. 조건을 확인하는 코드만 맞으면 답이 맞으므로 틀릴 곳도 적습니다.

둘째는 입력이 커져도 감당할 만한 풀이가 알려지지 않은 문제입니다. 외판원 순회 같은 문제가 많습니다. 이런 문제는 가장 좋은 답을 보장하는 방법이 알려진 것마다 느립니다.

입력이 커지면 일이 n², n³ 처럼 늘지 않고 2ⁿ 처럼 불어납니다. 2ⁿ 은 n 이 하나 늘 때마다 두 배가 되는 수입니다. 그러니 입력이 작을 때는 완전 탐색으로 가장 좋은 답을 얻는 것도 한 방법입니다.

셋째는 다른 풀이를 검산할 때입니다. 후보를 덜 보는 복잡한 풀이를 짠 뒤 작은 입력에서 완전 탐색의 답과 비교합니다. 두 답이 다르면 복잡한 풀이 쪽에 버그가 있는 것입니다.

테스트에서 이렇게 정답을 대 주는 기준을 테스트 오라클이라고 부릅니다. 완전 탐색은 오래 걸려도 답을 놓치지 않아서 이 역할을 자주 맡습니다.

무차별 대입 공격

보안에서도 같은 생각을 씁니다. 비밀번호나 암호 키를 가능한 값부터 하나씩 대 보는 공격을 무차별 대입 공격이라고 합니다. 영어로 brute-force attack 이라 완전 탐색과 이름이 겹칩니다.

막는 쪽은 조합 폭발을 거꾸로 이용합니다. 비밀번호에 쓸 수 있는 글자가 많을수록 탐색 공간이 불어납니다. 비밀번호가 길수록 역시 불어납니다. 암호 키는 한 비트 길어질 때마다 후보가 두 배가 됩니다.

후보를 덜 보는 기법

완전 탐색은 다른 설계 기법의 출발점이기도 합니다. 완전 탐색 풀이를 먼저 세웁니다. 그다음 어디서 헛일을 하는지 보면 줄일 곳이 보입니다.

줄이는 방법의 하나는 답이 나올 수 없는 후보를 만들기 전에 버리는 것입니다. 후보를 만드는 갈림에서 가망 없는 갈래를 잘라 내는 일을 가지치기(pruning)라고 합니다. 앞의 부분집합 그림에서 한 갈래 아래를 전부 안 만드는 셈입니다.

아래 표는 완전 탐색에서 출발해 후보를 덜 보는 기법들입니다.

앞의 셋은 완전 탐색과 같은 답을 보장합니다. 답이 될 수 없는 후보만 버리거나 같은 계산을 한 번만 하기 때문입니다. 그리디 알고리즘은 문제에 따라 가장 좋은 답을 놓칠 수 있습니다.

짝 찾기도 줄일 수 있습니다. 값을 앞에서부터 훑으며 지금까지 본 값을 해시테이블에 넣어 둡니다. 새 값마다 「목표 − 새 값」이 이미 들어 있는지 찾습니다. [3, 8, 2, 5] 에서 목표 7 이면 5 를 볼 때 7 − 5 = 2 가 이미 들어 있어 짝이 나옵니다.

해시테이블은 값을 넣어 두고 다시 찾는 자료구조입니다. 값이 몇 개 들어 있든 찾기가 평균 한 번에 끝납니다. 이것을 O(1) 로 적습니다. 값마다 한 번씩만 찾으므로 전체 비용이 O(n) 으로 줄어듭니다.

관련 항목

완전 탐색과 나란히 쓰는 설계 기법

분할 정복 · 감소 정복 · 그리디 알고리즘 · 동적 계획법 · 재귀 백트래킹 · 분기 한정

완전 탐색의 후보를 덜 보게 하는 도구

가지치기 · 메모이제이션 · 해시테이블 · 이진 탐색 · 휴리스틱 · 근사 알고리즘

완전 탐색이 만들어 훑는 후보의 모양

탐색 공간 · 상태 공간 · 부분집합 · 순열 · 조합 · 팩토리얼

완전 탐색이 후보를 차례로 훑는 방법

순차 탐색 · 깊이 우선 탐색 · 너비 우선 탐색 · 재귀 · 호출 스택

완전 탐색으로 푸는 대표 문제

외판원 순회 · 배낭 문제 · 부분집합 합 문제 · N-퀸 문제 · 충족 가능성 문제 · 결정 문제 · 최적화 문제

완전 탐색의 비용을 재는 도구

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 조합 폭발 · 지수 시간 · 다항 시간 · NP-난해

완전 탐색을 공격에 쓴 수법과 그 방어

무차별 대입 공격 · 사전 공격 · 레인보우 테이블 · 비밀번호 해싱 · 키 길이 · 속도 제한

완전 탐색의 답으로 검산하는 테스트 기법

테스트 오라클 · 속성 기반 테스트 · 퍼징 · 단위 테스트

완전 탐색이 속하는 상위 분류

알고리즘 · 알고리즘 설계 기법 · 탐색 알고리즘 · 계산 복잡도 이론