알고리즘 선택·검사 입력·다음 학습

알고리즘의 이름과 코드를 외웠다고 새 문제에 바로 적용할 수 있는 것은 아닙니다. 같은 "찾기" 문제라도 자료가 정렬되어 있는지, 몇 번이나 찾는지에 따라 알맞은 방법이 다르고, 같은 "길 찾기"라도 간선의 개수를 줄일지 비용을 줄일지에 따라 다른 알고리즘이 필요했습니다. 이 마지막 글에서는 문제를 보고 알고리즘을 고를 때 먼저 물어야 할 질문들을 정리하고, 만든 코드를 어떤 입력으로 검사할지, 검사와 증명이 각각 무엇을 알려 주는지 살펴본 뒤, 이 교재 다음에 공부할 거리를 소개합니다.

알고리즘을 고르기 전에 묻는 질문

알고리즘을 고르는 일은 이름을 떠올리는 것보다 문제에 대한 질문에 답하는 것에서 시작합니다. 아래 표는 이 교재에서 다룬 문제들에 대해 먼저 물어야 할 질문과, 그 답에 따라 고를 방법을 모은 것입니다.

표의 질문은 대부분 입력에 관한 것입니다. 자료가 정렬되어 있다는 사실 하나로 이진 탐색을 쓸 수 있게 되고, 비용이 음수가 아니라는 사실 하나로 Dijkstra 알고리즘을 쓸 수 있게 됩니다. 반대로 그 조건이 깨지면 같은 알고리즘이 틀린 답을 냅니다. 그래서 알고리즘을 고를 때는 "무엇이 빠른가"보다 "이 입력에서 무엇이 맞는가"를 먼저 따져야 합니다.

문제를 푸는 접근 방법에도 이름이 있습니다. 문제를 나누어 각각 풀고 합치는 분할 정복, 지금 가장 좋아 보이는 선택을 되돌아보지 않는 탐욕법, 작은 문제의 답을 저장해 다시 쓰는 동적 계획법, 가능한 선택을 하나씩 해 보고 되돌리는 백트래킹이 이 교재에서 만난 것들입니다. 이 이름들은 특정한 알고리즘이 아니라 생각의 방향이라서, 문제를 처음 볼 때 "이 문제를 작은 같은 문제로 나눌 수 있는가", "작은 문제가 겹치는가" 같은 질문을 떠올리게 해 줍니다.

검사할 입력 고르기

코드를 만들었으면 실수가 드러나기 쉬운 입력부터 검사합니다. 이 교재에서 실수를 자주 드러낸 입력은 다음과 같습니다. 빈 입력과 원소 하나는 반복 범위와 첫 원소 접근의 실수를, 같은 값의 반복은 값을 잃거나 두 번 쓰는 실수와 안정성 문제를 드러냈습니다. 이미 정렬된 입력과 역순 입력은 조기 종료와 최악의 경우를, 찾는 값이 없는 경우는 -1 같은 특별한 반환값의 처리를 시험했습니다. 그래프에서는 비용 0인 간선, 거절해야 할 음수 비용, 닿을 수 없는 정점이, 문자열에서는 겹치는 일치와 해시 충돌이 중요한 검사 입력이었습니다.

입력이 작다면 가능한 입력을 모두 만들어 쉬운 방법과 비교할 수도 있습니다. 아래 코드는 값이 0, 1, 2 가운데 하나이고 길이가 0부터 4까지인 리스트를 모두 만들어, 힙 정렬의 결과를 sorted와, 첫 위치를 찾는 이진 탐색의 결과를 리스트의 index와 비교합니다. 마지막으로 KMP도 A와 B로 된 짧은 문자열에서 단순한 방법과 비교합니다.

from itertools import product


def binary_search_first(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    if lo < len(values) and values[lo] == target:
        return lo
    return -1


def sift_down(values, root, size):
    while 2 * root + 1 < size:
        child = 2 * root + 1
        if child + 1 < size and values[child + 1] > values[child]:
            child += 1
        if values[root] >= values[child]:
            return
        values[root], values[child] = values[child], values[root]
        root = child


def heap_sort(values):
    result = list(values)
    n = len(result)
    for root in range(n // 2 - 1, -1, -1):
        sift_down(result, root, n)
    for end in range(n - 1, 0, -1):
        result[0], result[end] = result[end], result[0]
        sift_down(result, 0, end)
    return result


def kmp_matches(text, pattern):
    lps, j = [0] * len(pattern), 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = lps[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        lps[i] = j
    matches, j = [], 0
    for i, character in enumerate(text):
        while j > 0 and character != pattern[j]:
            j = lps[j - 1]
        if character == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            j = lps[j - 1]
    return matches


count = 0
for length in range(5):
    for values in product([0, 1, 2], repeat=length):
        ordered = sorted(values)
        assert heap_sort(values) == ordered
        for target in [-1, 0, 1, 2, 3]:
            expected = ordered.index(target) if target in ordered else -1
            assert binary_search_first(ordered, target) == expected
        count += 1
print(f"정렬과 이진 탐색: {count}개 입력 통과")

count = 0
for text_length in range(8):
    for text in product("AB", repeat=text_length):
        text = "".join(text)
        for pattern_length in range(1, 4):
            for pattern in product("AB", repeat=pattern_length):
                pattern = "".join(pattern)
                expected = [i for i in range(len(text) - len(pattern) + 1) if text[i:i + len(pattern)] == pattern]
                assert kmp_matches(text, pattern) == expected
                count += 1
print(f"KMP: {count}쌍 통과")

정렬과 이진 탐색: 121개 입력 통과
KMP: 3570쌍 통과

product([0, 1, 2], repeat=length)는 0, 1, 2 가운데 하나를 length번 골라 늘어놓은 모든 튜플을 차례로 내놓습니다. 같은 값을 다시 골라도 되고 순서가 다르면 다른 튜플로 치므로, 길이가 k이면 3ᵏ개입니다. 길이 0부터 4까지의 입력은 1 + 3 + 9 + 27 + 81 = 121개이고, 그 하나하나에 대해 찾을 값 다섯 개를 시도했으므로 이진 탐색은 605번 검사한 셈입니다. KMP는 길이 0부터 7까지의 text 255개와 길이 1부터 3까지의 pattern 14개의 모든 쌍인 3570쌍을 검사했습니다. 값을 0, 1, 2나 A, B로 좁혔기 때문에 같은 값의 반복, 겹치는 일치처럼 실수가 잘 드러나는 경우가 자연스럽게 많이 들어갑니다.

입력의 크기를 조금만 늘려도 모든 입력을 만드는 일은 금세 불가능해집니다. 그럴 때는 정렬의 정답 조건·안정성·시간 측정에서 한 것처럼 시드를 정한 무작위 입력을 많이 만들어 비교합니다. Python에는 Hypothesis처럼, 결과가 만족해야 할 성질을 적어 두면 입력을 자동으로 만들어 그 성질이 깨지는 예를 찾아 주는 라이브러리도 있습니다.

검사와 증명이 알려 주는 것

검사를 통과했다는 것은 검사한 입력들에서 틀리지 않았다는 뜻입니다. 위 코드는 길이 4 이하의 리스트에서 힙 정렬이 맞는다는 것을 보여 주지만, 길이 5인 리스트에 대해서는 아무것도 말해 주지 않습니다. 모든 입력에서 맞는다는 것은 이 교재의 각 글에서 불변조건과 귀납법으로 설명한 것처럼, 증명으로 보여야 합니다.

그렇다고 검사가 쓸모없는 것은 아닙니다. 증명은 머릿속의 알고리즘이 맞다는 것을 보여 줄 뿐, 그것을 코드로 옮기면서 생긴 실수까지 잡아 주지는 않습니다. lo = mid + 1을 lo = mid로 잘못 적은 코드는 증명을 아무리 잘해도 끝나지 않습니다. 그래서 둘은 함께 씁니다. 증명으로 알고리즘이 맞는 이유를 이해하고, 검사로 코드가 그 알고리즘을 바르게 옮겼는지 확인합니다. 검사를 마친 뒤에는 어떤 범위의 입력을 무엇과 비교했는지를 함께 적어 두는 것이 좋습니다. "길이 0부터 4까지, 값이 0부터 2까지인 리스트 121개를 sorted와 비교했다"처럼 적어 두면, 나중에 다른 사람이 무엇을 더 검사해야 하는지 알 수 있습니다.

이 교재 다음에

이 교재는 자료구조와 알고리즘의 기초를 다루었고, 그 너머에는 넓은 분야가 이어집니다. 정점·간선·인접 목록과 인접 행렬에서 잠깐 언급했듯이 모든 정점을 한 번씩 지나는 길을 찾는 문제처럼 빠른 알고리즘이 알려지지 않은 문제들이 있고, 이런 문제들을 분류하는 계산 복잡도 이론과, 최적에 가까운 답을 빠르게 찾는 근사 알고리즘이 그 다음 주제입니다. 그래프에서는 모든 정점을 가장 싸게 잇는 최소 신장 트리, 작업의 선후 관계를 따라 순서를 정하는 위상 정렬, 네트워크로 보낼 수 있는 최대 양을 구하는 최대 유량 같은 문제가 기다리고 있습니다. 자료구조에서는 정렬된 순서를 유지하며 넣고 빼는 균형 이진 탐색 트리와, 원소들이 같은 무리인지 빠르게 확인하는 서로소 집합 구조가 자주 쓰입니다.

이 사이트의 다른 교재와도 이어집니다. 이 교재에서 쓴 귀납법과 그래프의 정의는 이산수학에서 더 엄밀하게 다루고, 우선순위 큐와 스케줄링은 운영체제에서, 외부 정렬과 해시와 탐색 구조는 데이터베이스에서 실제 시스템의 모습으로 다시 만납니다. 시험을 준비하는 요약이 필요하다면 정보관리기술사 교재를 볼 수 있지만, 요약으로 용어를 떠올리는 것과 직접 상태를 추적하고 코드를 실행해 이해하는 것은 다른 일입니다. 공부하다 막히면 Python 설치부터 첫 실행과 오류 읽기, 불변조건·종료와 반례 찾기, 리스트·배열·문자열·딕셔너리의 역할로 돌아가 기초를 다시 확인하세요.

정리

• 알고리즘을 고를 때는 이름보다 입력과 요구에 관한 질문, 곧 정렬되어 있는지, 몇 번 하는지, 비용이 음수인지, 안정성이 필요한지 같은 질문에 먼저 답합니다.
• 분할 정복, 탐욕법, 동적 계획법, 백트래킹은 특정 알고리즘이 아니라 문제를 대하는 접근 방법입니다.
• 빈 입력, 원소 하나, 같은 값의 반복, 정렬된 입력과 역순 입력, 찾는 값이 없는 경우처럼 실수가 잘 드러나는 입력으로 검사하고, 작은 입력은 모두 만들어 쉬운 방법과 비교할 수 있습니다.
• 검사는 검사한 입력에서의 정확성을, 증명은 모든 입력에서의 정확성을 알려 주며, 둘은 서로를 대신하지 않고 함께 씁니다.
• 검사를 마친 뒤에는 어떤 범위의 입력을 무엇과 비교했는지 적어 두어 남은 검사 범위를 분명히 합니다.

연습 문제

1. 빠르다는 이유만으로

음수 비용의 간선이 있는 그래프에서 최소 비용 경로를 구할 때, "Dijkstra 알고리즘이 빠르다"는 이유로 그것을 골라도 될까요?

2. 검사 뒤에 적어 둘 것

본문의 코드처럼 작은 입력을 모두 만들어 검사를 통과했을 때, "다 됐다"고 적기 전에 함께 적어 두어야 할 것은 무엇일까요?

3. 상황에 맞는 구조 고르기

학생 1만 명의 점수를 담아 두고, 이름으로 한 학생의 점수를 아주 자주 찾으며, 가끔 점수 상위 10명을 뽑아야 합니다. 어떤 자료구조와 알고리즘을 쓰면 좋을까요?

이것으로 자료구조·알고리즘 교재를 마칩니다. 전체 목차는 자료구조·알고리즘에서 다시 볼 수 있습니다.