알고리즘 - 정렬·탐색·그래프·동적 계획법의 큰 그림

이 장에서 배우는 것

앞 장에서 데이터를 담는 그릇을 골랐다면, 이번에는 그 데이터를 어떤 순서로 처리할지 고른다. 알고리즘(algorithm)은 입력을 받아 원하는 결과를 만드는 유한한 절차다. 같은 입력과 같은 목표가 있어도 절차에 따라 살펴보는 후보의 수가 달라진다. 작은 목록에서는 드러나지 않던 차이가 항목 수가 늘면서 작업의 성패를 가르기도 한다.

알고리즘 과목의 지도를 읽을 때는 풀이 이름부터 외우기보다 문제의 생김새부터 살피는 편이 좋다. 순서를 정하는가, 조건을 만족하는 항목을 찾는가, 연결을 따라가는가, 제약 안에서 가장 좋은 조합을 고르는가를 먼저 묻는다. 이 장에서는 학습 과목을 고르는 작은 프로그램으로 이 질문들을 확인한다.

• 정렬·탐색·그래프·동적 계획법이 어떤 질문을 다루는지 구분한다.
• 모든 후보를 확인하는 풀이를 기준으로 삼고, 중복 계산을 줄일 기회를 찾는다.
• 같은 학습 과목 선택 문제를 두 방법으로 풀고 호출 수와 계산한 칸 수를 비교한다.
• 코딩 테스트의 조건과 실무의 요구사항을 구분하고, 면접에서 풀이의 근거를 설명한다.

문제 상황

다른 전공을 공부하다 개발 일을 시작한 사람이 이번 주에 보완할 내용을 고른다고 하자. 후보에는 논리 연습, 자료구조 복습, 정렬 연습, 탐색 연습, 그래프 연습, 복잡도 읽기, 동적 계획법 연습, 풀이 설명이 있다. 이번 주에 쓸 수 있는 시간은 여덟 시간이다. 각 항목에는 예상 시간과 현재 목표에 얼마나 도움이 되는지를 나타내는 점수가 붙어 있다.

이 점수는 전공 지식의 객관적인 가치가 아니다. 현재 맡은 일이나 준비 중인 면접을 기준으로 학습자가 정한 비교값이다. 같은 항목을 반복해서 선택하지 않고, 시간 한도를 넘기지 않으면서 점수 합계가 가장 큰 조합을 찾으려 한다. 전공 수업에서는 이처럼 가능한 선택 중 목적값을 가장 좋게 만드는 문제를 최적화 문제라고 부른다.

실제 학습 계획에는 피로, 일정, 선수 지식도 작용한다. 여기서는 계산 방법의 차이를 관찰하기 위해 예상 시간을 양의 정수로 정하고, 점수는 더할 수 있다고 가정한다. 선수 지식의 연결은 별도 예제로 살펴보되 선택 조건에는 넣지 않는다. 프로그램이 푸는 범위를 명확히 해야 출력된 숫자를 실제 계획에 적용할 때도 의미를 잘못 읽지 않는다.

여덟 시간 안에서 선택할 학습 후보

항목	예상 시간	목표 도움 점수
논리 연습	2	3
자료구조 복습	3	5
정렬 연습	4	6
탐색 연습	2	4
그래프 연습	3	4
복잡도 읽기	1	2
동적 계획법 연습	4	5
풀이 설명	2	3

점수가 가장 큰 항목부터 고르면 될 것 같지만, 항목 하나의 점수만으로 조합의 점수를 알 수는 없다. 네 시간짜리 항목을 먼저 넣는 순간 두 시간짜리 두 항목을 넣을 기회를 잃을 수 있다. 선택 규칙을 정하기 전에 무엇을 비교해야 정답이 되는지부터 밝혀야 한다.

문제의 생김새로 풀이를 분류한다

이 장의 핵심은 다섯 가지다. 정렬, 탐색, 그래프에서의 이동, 완전 탐색, 동적 계획법이다. 서로 경쟁하는 다섯 도구라기보다 한 문제 안에서도 이어 쓸 수 있는 관점이다. 예를 들어 후보를 이름순으로 정렬한 뒤 특정 과목을 찾고, 연결된 선수 지식을 확인한 다음, 시간 제약에 맞는 조합을 계산할 수 있다.

입력보다 먼저 확인할 문제의 질문

질문	전공 수업의 이름	이 장의 코드	실무의 쓰임
어떤 순서로 놓을까	정렬	이름순 목록 만들기	목록 표시, 처리 우선순위
원하는 값은 어디에 있을까	탐색	정렬된 이름에서 위치 찾기	기준값과 일치하는 항목 찾기
연결을 따라 어디까지 갈까	그래프 탐색	연결된 학습 항목 방문하기	의존 관계와 영향 범위 확인
가능한 후보는 무엇일까	완전 탐색	모든 선택 조합 확인하기	작은 입력의 정답 기준 만들기
같은 계산을 다시 하는가	동적 계획법	시간별 최고 점수 저장하기	제약이 있는 조합 계산

정렬과 탐색은 서로 다른 질문이다

정렬은 비교 기준에 따라 항목의 순서를 만드는 일이다. 완성 코드의 sorted는 학습 항목 이름을 Python 문자열 비교 규칙에 따라 정렬한다. 사람이 사용하는 사전의 세부 정렬 규칙까지 구현하는 예제는 아니다. 전공 수업에서는 비교할 기준을 키(key)라고 부르기도 한다. 여기서는 항목 이름 자체가 기준이다.

탐색은 원하는 값을 찾는 일이다. 처음부터 하나씩 비교하는 선형 탐색은 정렬되지 않은 목록에도 적용할 수 있다. 반면 이진 탐색(binary search)은 정렬된 범위의 가운데를 확인하고, 답이 있을 수 없는 절반을 제외한다. 완성 코드에서는 표준 라이브러리의 bisect_left로 이 과정을 사용한다. 이름이 들어갈 첫 위치를 돌려주므로, 그 위치에 실제로 같은 이름이 있는지 다시 확인해야 한다.

정렬 비용도 함께 계산해야 한다. 한 번만 찾을 작은 목록이라면 먼저 정렬하는 수고가 더 클 수 있다. 이미 정렬된 목록을 여러 번 찾는다면 다른 판단을 할 수 있다. 실무에서는 특정 알고리즘이 빠르다는 문장보다 입력의 상태와 작업의 반복 횟수가 선택의 근거가 된다.

연결을 가진 데이터에서는 방문 순서를 정한다

그래프(graph)는 대상과 대상 사이의 연결을 표현하는 모델이다. 대상을 정점, 연결을 간선이라고 부른다. 완성 코드에서는 논리에서 자료구조로, 자료구조에서 알고리즘으로 이어지는 작은 학습 연결을 사전으로 표현한다. 화살표는 앞의 항목에서 다음 항목으로 진행할 수 있다는 뜻이다.

너비 우선 탐색(breadth-first search)은 시작점에서 연결 한 번으로 갈 수 있는 정점들을 먼저 확인하고, 그다음 연결 두 번으로 갈 수 있는 정점들을 확인한다. 코드에서는 먼저 넣은 항목을 먼저 꺼내는 큐를 사용한다. 앞 장에서 본 자료구조가 여기서는 방문 순서를 유지하는 역할을 맡는다.

방문 기록은 같은 정점을 여러 번 처리하지 않도록 한다. 연결이 되돌아오는 경우에도 처리가 끝나게 하는 장치다. 다만 너비 우선 탐색 결과를 곧바로 학습 이수 순서로 사용해서는 안 된다. 여러 선수 과목을 모두 마쳐야 하는 조건은 별도 확인이 필요하다. 이 예제는 시작점에서 연결을 따라 방문하는 순서만 보여 준다.

완전 탐색으로 정답의 기준을 만든다

완전 탐색은 가능한 후보를 빠짐없이 확인하는 방법이다. 이번 문제에서는 항목마다 선택하거나 선택하지 않는 두 갈래가 있다. 항목이 여덟 개라면 최종 선택 조합은 2의 8제곱, 즉 256개다. 아무것도 선택하지 않는 조합도 포함한다.

완성 코드의 함수는 자기 자신을 다시 호출한다. 전공 수업에서는 이를 재귀(recursion)라고 부른다. 함수는 현재 항목을 건너뛰는 경우와 담는 경우를 각각 계산하고 더 좋은 점수를 반환한다. 모든 항목을 처리했을 때 시간을 초과했다면 -1을 반환한다. 점수가 음수가 아니라는 이번 입력 조건에서 -1은 유효한 조합보다 낮은 값이다.

재귀에는 멈추는 조건이 필요하다. 여기서는 현재 위치가 항목 수와 같아지면 더 내려가지 않는다. 각 호출에서 위치를 하나 늘리므로 이 조건에 도달한다. 전공 수업에서는 더 쪼개지 않고 답을 반환하는 조건을 기저 조건이라고 부른다. 재귀 코드를 읽을 때는 이 조건과 그 조건으로 가까워지는 변화를 먼저 확인한다.

이번 구현은 호출 수를 관찰하기 위해 시간 초과가 발생해도 마지막 항목까지 내려간다. 따라서 최종 조합 256개 외에 중간 선택 단계도 호출 횟수에 포함된다. 전체 호출 수는 1 + 2 + 4 + … + 256 = 511이다. 시간 초과 시 즉시 멈추는 방식도 가능하며, 불필요한 후보를 더 살피지 않는 처리를 가지치기라고 부른다. 그 경우에는 입력에 따라 호출 수가 달라진다.

완전 탐색은 비효율적인 풀이를 일부러 거치는 의식이 아니다. 작은 입력에서 조건을 정확히 구현하기 쉽고, 더 빠른 풀이의 결과를 확인할 기준이 된다. 먼저 정답을 계산하는 간단한 함수를 만들고, 같은 입력에 대한 개선된 함수의 결과와 비교하면 잘못된 최적화를 발견하기 쉽다.

입력이 커질 때 작업량이 어떻게 늘어나는지를 시간 복잡도라고 부른다. 전공 수업에서는 큰 입력에서 증가 양상을 표현하는 빅오 표기법을 쓴다. 이 완전 탐색의 시간 복잡도는 O(2ⁿ)이다. 여기서 n은 항목 수다. 항목 하나를 추가할 때 최종 조합 수가 두 배가 된다는 뜻이며, 특정 컴퓨터에서 몇 초 걸리는지를 뜻하지는 않는다.

동적 계획법은 같은 질문의 답을 보관한다

동적 계획법(dynamic programming)은 작은 문제의 답을 저장하고, 그 답으로 더 큰 문제를 계산하는 방법이다. 이번에는 “앞에서부터 몇 개의 항목을 고려했고, 쓸 수 있는 시간이 얼마인가”를 작은 문제로 삼는다. 이처럼 다음 계산을 결정하는 데 필요한 정보를 묶은 표현을 상태(state)라고 부른다.

여기서 저장할 값은 “지금까지 고려한 항목으로 주어진 시간 이내에 얻을 수 있는 최고 점수”다. 어떤 항목까지 고려했는지는 반복문의 진행 단계가 나타내고, 시간 한도는 목록의 위치가 나타낸다. 같은 상태에서는 앞서 어떤 조합을 거쳤는지와 관계없이 최고 점수 하나만 남겨도 된다. 앞으로 사용할 수 있는 항목이 같고, 점수를 단순히 더하기 때문이다.

새 항목의 시간이 cost, 점수가 score라고 하자. 시간 한도 limit에서 새 항목을 넣지 않는 답은 이전 단계의 previous[limit]이다. 넣는 답은 이전 단계의 previous[limit - cost] + score다. 두 값 중 큰 값을 저장한다. 작은 문제의 답에서 다음 답을 계산하는 이 규칙을 점화식이라고 부른다.

시간 한도별 최고 점수를 갱신하는 규칙

조건	새 단계의 값	이유
limit < cost	previous[limit]	새 항목을 담을 시간이 없다.
limit ≥ cost	max(previous[limit], previous[limit - cost] + score)	건너뛰기와 담기 중 좋은 값을 고른다.
아직 고려한 항목이 없음	모든 시간 한도에서 0	아무것도 선택하지 않는 점수가 0이다.

코드는 이전 단계와 새 단계를 서로 다른 목록에 담는다. 새 항목을 담는 계산이 이전 단계만 참조하므로 한 항목을 두 번 사용하지 않는다. 모든 항목을 처리한 뒤 여덟 시간 칸을 읽으면 답을 얻는다. 이런 식으로 작은 상태부터 순서대로 채우는 구현을 상향식 계산이라고 부른다.

시간 한도가 B라면 한 항목마다 0부터 B까지 B + 1칸을 계산한다. 따라서 시간 복잡도는 O(nB)이고, 이전 단계와 새 단계만 보관하므로 추가 공간은 O(B)다. 이번 입력에서는 8 × 9 = 72칸을 계산한다. 시간 단위를 분으로 바꾸어 한도가 커지면 칸 수도 늘어난다. 항목 수가 같다는 이유만으로 비용이 같다고 볼 수 없다.

모든 조합 문제에 이 상태를 쓸 수 있는 것은 아니다. 특정 두 항목을 함께 고르면 추가 점수를 주거나, 선수 과목 선택 여부가 필요하다면 시간과 현재 단계만으로는 판단할 수 없을 수 있다. 동적 계획법의 출발점은 표를 만드는 일이 아니라, 저장한 정보만으로 다음 선택을 판단할 수 있는지 설명하는 일이다.

완성 코드

다음 내용을 main.py에 저장한다. 정렬·이진 탐색·그래프 방문을 먼저 확인하고, 같은 후보 목록에 완전 탐색과 동적 계획법을 적용한다. 난수를 사용하지 않으며 입력이나 네트워크 연결을 기다리지 않는다. 두 선택 함수는 조합 자체가 아니라 최고 점수를 반환한다.

from bisect import bisect_left
from collections import deque


COURSES = (
    ("논리 연습", 2, 3),
    ("자료구조 복습", 3, 5),
    ("정렬 연습", 4, 6),
    ("탐색 연습", 2, 4),
    ("그래프 연습", 3, 4),
    ("복잡도 읽기", 1, 2),
    ("동적 계획법 연습", 4, 5),
    ("풀이 설명", 2, 3),
)
BUDGET = 8


def find_name(names, target):
    position = bisect_left(names, target)
    if position < len(names) and names[position] == target:
        return position
    return -1


def breadth_first(graph, start):
    queue = deque([start])
    seen = {start}
    order = []
    while queue:
        current = queue.popleft()
        order.append(current)
        for neighbor in graph[current]:
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    return order


def exhaustive(courses, budget):
    calls = 0

    def visit(index, used, score):
        nonlocal calls
        calls += 1
        if index == len(courses):
            return score if used <= budget else -1

        _, cost, value = courses[index]
        skipped = visit(index + 1, used, score)
        taken = visit(index + 1, used + cost, score + value)
        return max(skipped, taken)

    best = visit(0, 0, 0)
    return best, calls


def dynamic(courses, budget):
    previous = [0] * (budget + 1)
    cells = 0

    for _, cost, score in courses:
        current = [0] * (budget + 1)
        for limit in range(budget + 1):
            cells += 1
            best = previous[limit]
            if cost <= limit:
                best = max(best, previous[limit - cost] + score)
            current[limit] = best
        previous = current

    return previous[budget], cells


def main():
    names = sorted(name for name, _, _ in COURSES)
    position = find_name(names, "탐색 연습")
    print("이름순:", ", ".join(names))
    print("탐색 연습 위치:", position)
    print("없는 항목 위치:", find_name(names, "없는 과목"))

    graph = {
        "논리": ("자료구조",),
        "자료구조": ("알고리즘",),
        "알고리즘": (),
    }
    print("연결 방문:", " -> ".join(breadth_first(graph, "논리")))

    brute_best, calls = exhaustive(COURSES, BUDGET)
    dp_best, cells = dynamic(COURSES, BUDGET)
    assert brute_best == dp_best
    print("시간 한도:", BUDGET)
    print("완전 탐색 최고 점수:", brute_best)
    print("완전 탐색 함수 호출:", calls)
    print("동적 계획법 최고 점수:", dp_best)
    print("동적 계획법 함수 호출:", 1)
    print("동적 계획법 계산 칸:", cells)
    print("결과 일치:", brute_best == dp_best)


if __name__ == "__main__":
    main()

줄별 해설

가져오기와 입력. bisect_left는 정렬된 목록에서 삽입 위치를 찾는 함수다. deque는 양쪽 끝에서 항목을 넣고 꺼낼 수 있는 표준 라이브러리 자료구조다. COURSES의 각 튜플은 이름, 시간, 점수 순서다. 함수들은 이 순서를 입력 계약으로 사용한다. 이번 프로그램은 양의 정수 시간과 음수가 아닌 정수 점수가 주어지는 고정된 예제다.

find_name. 첫 줄은 탐색 범위를 반복해서 줄여 삽입 위치를 구한다. 다음 조건은 위치가 목록 안에 있는지 먼저 확인한다. and는 앞 조건이 거짓이면 뒤 조건을 평가하지 않으므로 목록 끝을 넘겨 읽지 않는다. 같은 값이 있으면 위치를 반환하고, 없으면 -1을 반환한다. 위치는 Python 목록과 같이 0부터 센다.

breadth_first의 준비. queue에는 다음에 확인할 정점이 들어간다. seen은 이미 발견한 정점의 집합이고, order는 실제로 꺼낸 순서를 담는 목록이다. 같은 데이터를 세 곳에 보관하는 이유는 각각 대기 순서, 중복 방지, 출력이라는 다른 역할을 갖기 때문이다.

breadth_first의 반복. popleft로 가장 먼저 기다린 정점을 꺼내고, 연결된 이웃을 차례로 확인한다. 새 이웃은 큐에 넣기 직전에 seen에 기록한다. 여러 경로에서 같은 정점을 발견해도 큐에는 한 번만 들어간다. 이 코드는 모든 정점 이름이 사전의 키로 존재한다고 가정한다. 방문 기록용 집합을 순회하지 않고 튜플에 적힌 이웃 순서를 사용하므로 방문 출력도 일정하다.

exhaustive와 visit. 바깥 함수가 호출 횟수를 만들고, 안쪽 함수가 선택을 진행한다. nonlocal은 안쪽 함수에서 바깥 함수의 calls를 바꾸겠다는 뜻이다. 호출마다 1을 더하므로 처음 호출과 마지막 단계의 호출도 센다. index는 다음에 결정할 항목의 위치, used는 이미 쓴 시간, score는 누적 점수다.

두 갈래의 반환값. 밑줄 변수는 이번 계산에 이름이 필요 없음을 나타낸다. skipped는 현재 항목을 건너뛴 결과이고 taken은 담은 결과다. 두 호출 모두 index를 하나 늘린다. max는 두 갈래에서 얻은 최고 점수 중 큰 값을 선택한다. 바깥 함수는 최종 점수와 총호출 수를 함께 반환한다.

dynamic의 previous. 길이가 budget + 1인 목록은 시간 한도 0인 경우까지 포함한다. 처음의 0은 아직 항목을 하나도 고려하지 않았을 때의 답이다. 시간 한도와 정확히 같은 시간을 써야 한다는 뜻이 아니므로, 남는 시간이 있어도 최고 점수를 저장한다.

current를 채우는 부분. 항목마다 새 목록을 만들고 각 시간 한도에서 두 선택을 비교한다. cells는 항목과 시간 한도의 쌍을 하나 계산할 때마다 증가한다. 반복이 끝난 뒤 previous가 current를 가리키게 하여 다음 항목의 기준으로 삼는다. 이전 모든 단계를 계속 보관하지 않으므로 메모리 사용을 줄일 수 있다.

main의 검증과 출력. assert는 두 결과가 다르면 실행 중 오류를 내는 확인문이다. 예제에서 두 구현의 불일치를 발견하는 장치이며, 외부 입력을 검증하는 용도로 삼지는 않는다. 마지막 조건문은 이 파일을 직접 실행할 때 main을 호출한다. 동적 계획법 함수는 main에서 한 번 호출되므로 호출 수는 1로 출력하고, 실제 반복 작업량은 cells로 별도 출력한다.

실행 결과

터미널에서 파일이 있는 디렉터리로 이동한 뒤 실행한다.

python3 main.py

예상 출력은 다음과 같다.

이름순: 그래프 연습, 논리 연습, 동적 계획법 연습, 복잡도 읽기, 자료구조 복습, 정렬 연습, 탐색 연습, 풀이 설명
탐색 연습 위치: 6
없는 항목 위치: -1
연결 방문: 논리 -> 자료구조 -> 알고리즘
시간 한도: 8
완전 탐색 최고 점수: 14
완전 탐색 함수 호출: 511
동적 계획법 최고 점수: 14
동적 계획법 함수 호출: 1
동적 계획법 계산 칸: 72
결과 일치: True

최고 점수 14를 만드는 조합의 한 예는 자료구조 복습, 탐색 연습, 복잡도 읽기, 풀이 설명이다. 시간은 3 + 2 + 1 + 2 = 8이고 점수는 5 + 4 + 2 + 3 = 14다. 코드는 선택 목록을 복원하지 않으므로 이 조합을 출력하지는 않는다. 최고 점수만 필요한 요구사항과 선택 내역도 필요한 요구사항은 구현 범위가 다르다.

호출 수 511과 1을 곧바로 속도 비율로 읽으면 안 된다. 동적 계획법의 한 번 호출 안에도 72칸을 채우는 반복문이 있다. 반대로 완전 탐색의 호출마다 수행하는 일도 서로 완전히 같지는 않다. 이 실험은 후보를 따라 내려가는 계산과 상태를 채우는 계산의 구조를 비교한다. 실행 시간은 입력 크기와 실행 환경을 정한 별도 측정이 필요하다.

두 결과가 같다는 사실은 이번 입력에 대한 확인이다. 모든 입력에서 정답이라는 근거는 선택을 빠짐없이 나누었는지, 각 상태가 필요한 정보를 담는지에 대한 설명에서 나온다. 입력을 바꾸어 비교하는 검증은 그 설명에 빠진 조건을 찾는 데 도움이 된다.

실무에서 자주 틀리는 것

정렬하지 않은 목록에 이진 탐색을 적용한다

bisect_left는 목록을 정렬해 주지 않는다. 아래의 첫 코드는 정렬 조건이 깨져 원하는 이름을 놓친다. 두 조각은 각각 독립적으로 실행할 수 있다.

from bisect import bisect_left

names = ["탐색", "논리"]
position = bisect_left(names, "탐색")
found = position < len(names) and names[position] == "탐색"
print(found)  # False

from bisect import bisect_left

names = sorted(["탐색", "논리"])
position = bisect_left(names, "탐색")
found = position < len(names) and names[position] == "탐색"
print(found)  # True

정렬하면서 위치도 바뀐다. 원래 목록의 위치가 필요하다면 이름과 원래 위치를 함께 보관해야 한다. 탐색 결과의 위치가 어느 목록을 기준으로 하는지까지 함수의 약속에 포함한다.

하나의 항목을 같은 단계에서 여러 번 담는다

동적 계획법을 한 목록으로 줄이면서 시간 한도를 작은 값부터 갱신하면, 방금 담은 항목의 점수를 다시 읽을 수 있다. 아래에서는 시간 2, 점수 3인 항목이 하나뿐인데도 점수 6을 얻는다.

best = [0] * 5
cost, score = 2, 3
for limit in range(cost, 5):
    best[limit] = max(best[limit], best[limit - cost] + score)
print(best[4])  # 6: 같은 항목을 두 번 사용했다.

best = [0] * 5
cost, score = 2, 3
for limit in range(4, cost - 1, -1):
    best[limit] = max(best[limit], best[limit - cost] + score)
print(best[4])  # 3

큰 시간 한도부터 갱신하면 참조하는 작은 칸은 이번 항목으로 아직 바뀌지 않았다. 다만 반복 방향을 외우는 것보다 어느 단계의 값을 읽는지 이해하는 일이 먼저다. 완성 코드가 이전 목록과 새 목록을 나눈 이유도 여기에 있다.

점수순 선택을 최적 조합이라고 생각한다

그 순간 좋아 보이는 선택을 계속하는 방법을 탐욕법(greedy method)이라고 부른다. 이 방법을 쓰려면 그 선택이 나중의 최적 결과를 해치지 않는다는 근거가 필요하다. 다음 첫 코드는 제한 시간 안에서 가장 높은 단일 점수만 골라 조합을 놓친다.

items = [(4, 7), (3, 6), (3, 6)]
budget = 6
used = 0
total = 0
for cost, score in sorted(items, key=lambda item: item[1], reverse=True):
    if used + cost <= budget:
        used += cost
        total += score
print(total)  # 7

items = [(4, 7), (3, 6), (3, 6)]
budget = 6
best = 0
for mask in range(1 << len(items)):
    used = 0
    total = 0
    for index, (cost, score) in enumerate(items):
        if mask & (1 << index):
            used += cost
            total += score
    if used <= budget:
        best = max(best, total)
print(best)  # 12

고친 코드에서는 정수의 각 이진 자리를 선택 여부로 사용한다. <<는 이진 자리를 왼쪽으로 옮기고, &는 해당 자리가 켜졌는지 확인한다. 여기서는 세 항목의 여덟 조합을 모두 확인하는 짧은 대안이다. 큰 입력을 위한 개선은 완성 코드의 동적 계획법이 맡는다.

한 입력의 일치만으로 검증을 끝낸다

두 구현이 기본 예제에서 같은 값을 내더라도 빈 입력과 시간 한도 0에서 어긋날 수 있다. 다음 첫 조각은 완성 코드의 main 안에서 기본 입력만 확인하는 경우다. 두 번째 조각으로 바꾸면 경계 조건도 함께 확인한다. 경계 조건은 입력 범위의 끝이나 특별히 작은 경우를 뜻한다.

assert exhaustive(COURSES, BUDGET)[0] == dynamic(COURSES, BUDGET)[0]

cases = (
    (COURSES, BUDGET, 14),
    ((), 8, 0),
    (COURSES, 0, 0),
    ((("짧은 복습", 2, 3),), 1, 0),
    ((("짧은 복습", 2, 3),), 2, 3),
)
for courses, budget, expected in cases:
    brute = exhaustive(courses, budget)[0]
    planned = dynamic(courses, budget)[0]
    assert brute == planned == expected
print("경계 조건 확인:", len(cases))  # 경계 조건 확인: 5

서로 다른 두 함수가 같은 실수를 할 수도 있다. 그래서 두 결과끼리만 비교하지 않고, 사람이 손으로 구한 예상값도 함께 둔다. 실제 서비스에서 시간이나 점수를 외부에서 받는다면 잘못된 형식과 허용 범위도 별도로 검사해야 한다.

한눈에 보기

코딩 테스트는 보통 입력 범위, 정답 조건, 시간 제한이 미리 주어진다. 실무에서는 어떤 값을 정답으로 삼을지부터 합의해야 할 수 있다. 학습 점수의 근거가 바뀌거나 특정 항목을 반드시 포함해야 한다면 문제 정의가 달라진다. 정답을 빠르게 계산하는 능력과 올바른 문제를 정의하는 능력이 함께 필요하다.

알고리즘을 선택하고 설명할 때 확인할 기준

관점	확인할 내용	면접에서 묻는 방식
정렬과 탐색	정렬 여부, 반복 조회 횟수, 결과 위치의 기준	이진 탐색에 정렬이 필요한 이유는 무엇인가
그래프 방문	연결 방향, 방문 기록, 큐에 넣는 시점	같은 정점이 여러 경로로 발견되면 어떻게 처리하는가
완전 탐색	선택지, 종료 조건, 후보 수	먼저 모든 후보를 확인한다면 비용은 얼마인가
동적 계획법	상태의 의미, 점화식, 초기값	왜 이 정보만 저장해도 다음 답을 구할 수 있는가
실무 적용	입력 범위, 변경 가능성, 검증과 유지 비용	입력이 커지거나 요구사항이 바뀌면 무엇을 바꾸는가

면접에서는 풀이 이름만 말하기보다 문제를 다시 정의하고, 가장 단순한 풀이의 비용을 설명한 뒤 개선 근거를 이어 말하는 편이 좋다. 이번 문제라면 “항목마다 두 선택이 있으므로 모든 조합을 확인할 수 있다. 이후에는 앞에서 고려한 항목과 시간 한도별 최고 점수를 저장한다”라고 설명할 수 있다. 마지막으로 같은 항목을 두 번 쓰지 않는 이유와 경계 조건을 덧붙인다.

더 깊게 볼 서재에는 Jon Kleinberg와 Éva Tardos의 Algorithm Design, Steven S. Skiena의 The Algorithm Design Manual을 둘 수 있다. 앞 책에서는 문제 구조와 풀이의 정당성을 설명하는 방식을, 뒤 책에서는 문제 유형을 찾아가는 관점을 살펴보기 좋다. 처음부터 모두 읽기보다 이번 코드의 완전 탐색과 동적 계획법을 설명할 수 있게 된 뒤 관련 부분을 찾아 읽는 식으로 활용한다.

알고리즘은 필요한 계산의 양을 설명한다. 같은 계산을 실제 장치가 어떻게 실행하는지는 또 다른 질문이다. 다음 장에서는 비트, CPU, 메모리 계층을 통해 코드가 실행되는 장치 쪽 지도를 살펴본다.

연습 문제

1. 완성 코드의 시간 한도를 0으로 바꾼다. 두 방법의 최고 점수, 완전 탐색 호출 수, 동적 계획법 계산 칸 수를 실행 전에 예상하고 확인한다.
2. 마지막에 시간 1, 점수 1인 새 항목을 추가하고 시간 한도는 8로 유지한다. 최고 점수를 추측하기 전에 완전 탐색 호출 수와 동적 계획법 계산 칸 수부터 구한다. 두 결과가 일치하는지도 확인한다.
3. 그래프의 알고리즘 항목에서 논리로 돌아오는 연결을 추가한다. 방문 기록이 있는 코드의 출력을 예상한다. 이어서 visited에 해당하는 seen을 없앴을 때 왜 종료가 보장되지 않는지 설명한다. 방문 기록을 없앤 프로그램은 실행하지 않는다.
4. main에 있는 두 선택 함수 호출 직후, 시간 한도를 0부터 8까지 바꾸며 두 결과가 같은지 확인하는 반복문을 추가한다. 이 검사가 동적 계획법의 정당성 설명을 대신할 수 있는지도 답한다.

정답과 해설

1. 두 최고 점수는 0이다. 모든 항목의 시간이 양수이므로 아무것도 선택하지 않아야 한다. 완전 탐색은 시간 초과 여부를 마지막에 검사하므로 여전히 511번 호출된다. 동적 계획법은 항목 여덟 개에 대해 시간 한도 0인 칸만 계산하므로 8칸이다. 두 함수의 반환값을 직접 확인하면 다음과 같다.

print(exhaustive(COURSES, 0))  # (0, 511)
print(dynamic(COURSES, 0))     # (0, 8)

2. 항목이 아홉 개가 되므로 마지막 조합은 512개이고 전체 호출은 1 + 2 + … + 512 = 1023번이다. 동적 계획법은 9 × 9 = 81칸을 계산한다. 다음 코드는 main 안이나 완성 코드의 함수 정의 아래에서 실행할 수 있다. 최고 점수는 두 방법 모두 14다.

expanded = COURSES + (("학습 기록", 1, 1),)
print(exhaustive(expanded, 8))  # (14, 1023)
print(dynamic(expanded, 8))     # (14, 81)

3. 출력은 논리, 자료구조, 알고리즘 순서로 유지된다. 알고리즘에서 논리를 다시 발견하지만 이미 seen에 있으므로 큐에 넣지 않는다. 방문 기록을 없애면 세 정점이 차례로 다시 큐에 들어가고 이 과정이 반복된다. 다음처럼 연결을 바꿔 확인한다.

graph = {
    "논리": ("자료구조",),
    "자료구조": ("알고리즘",),
    "알고리즘": ("논리",),
}
print(breadth_first(graph, "논리"))
# ['논리', '자료구조', '알고리즘']

4. 시간 한도를 바꿀 때도 동일한 후보 목록을 두 함수에 전달한다. 다음 코드를 main에 추가하면 아홉 경우를 확인하고 정해진 문장을 출력한다.

for budget in range(9):
    brute = exhaustive(COURSES, budget)[0]
    planned = dynamic(COURSES, budget)[0]
    assert brute == planned
print("시간 한도 0~8 비교: 일치")

이 검사는 현재 후보 목록의 아홉 가지 한도에서 결과가 같다는 증거다. 다른 시간과 점수를 가진 모든 목록까지 확인한 것은 아니다. 정당성은 각 항목을 건너뛰거나 담는 두 경우가 모든 선택을 포함하고, 담는 경우에 이전 단계의 답만 사용하며, 두 경우 중 큰 값을 저장한다는 설명으로 뒷받침한다. 코드 실험과 그 이유를 함께 말할 수 있으면 알고리즘 과목의 다음 주제를 찾아갈 기준이 생긴다.