자료구조 고르기 - 요구사항에서 구조로

이 장에서 배우는 것

자료구조를 직접 만들고 나면 다음 질문이 남는다. 같은 값을 저장하고 찾을 수 있는 구조가 여럿인데, 어떤 것을 골라야 하는가. 이름을 많이 외우는 것보다 중요한 일은 프로그램이 자주 하는 연산을 알아내는 일이다. 데이터를 넣는 횟수와 찾는 횟수, 정렬된 결과가 필요한지, 가장 급한 항목만 꺼내면 되는지를 먼저 적는다. 그러면 선택의 근거가 구체적으로 드러난다.

앞 장에서 만든 유니온 파인드는 두 항목이 같은 그룹에 속하는지 빠르게 확인하는 구조였다. 그 구조에 접두사 검색을 맡기지는 않는다. 이처럼 자료구조에는 잘 맞는 질문이 있다. 이 장에서는 앞 장들에서 만든 구조의 선택 기준을 정리하고, 같은 작업을 서로 다른 구조에 맡겨 비교 횟수를 확인한다. 구현 방법을 다시 넓게 펼치기보다, 구현한 것을 요구사항에 연결하는 데 집중한다.

• 연산의 종류와 빈도를 적어 자료구조 후보를 좁힌다.
• 캐시·랭킹·검색·작업 대기열의 요구사항을 구분한다.
• 같은 입력과 같은 결과를 기준으로 직접 구현한 구조를 비교한다.
• 연산 횟수의 의미와 측정 범위를 설명하고 면접 질문에 답한다.

문제 상황

개발 과제로 작은 작업 관리 프로그램을 만든다고 하자. 작업에는 정수 번호와 처리 순서가 있다. 처음에는 작업 번호 여덟 개를 저장하고, 요청받은 번호가 등록되어 있는지 확인하면 충분하다. 이때는 배열을 처음부터 훑어도 구현이 간단하다. 그러나 요구사항이 늘어나면 선택도 달라진다.

중복 요청을 걸러 내려고 작업 번호를 자주 조회한다면 해시 테이블이 후보가 된다. 다음에 처리할 작업 하나만 중요하다면 힙을 검토한다. 들어온 순서를 지켜야 한다면 큐가 필요하다. 이름의 앞부분으로 작업을 찾으려면 트라이를 검토한다. 모두 작업을 저장하지만, 실제로 답해야 할 질문은 서로 다르다.

여기서 “조회가 많다”는 말도 더 구체적으로 바꿔야 한다. 번호 하나가 존재하는지 묻는 것과 번호가 일정 구간에 들어가는 작업을 모두 찾는 것은 다른 연산이다. 전체 정렬 결과를 매번 출력하는 것과 가장 작은 값 하나를 꺼내는 것도 다르다. 모호한 요구사항을 연산으로 나누는 과정부터 자료구조 선택이 시작된다.

이번 완성 코드는 이 가운데 정확한 번호 조회만 비교한다. 앞 장들의 배열·정렬 배열·해시 테이블·이진 탐색 트리를 비교에 필요한 삽입과 조회만 남겨 한 파일에 담는다. 작업은 여덟 번의 삽입과 아홉 번의 조회다. 마지막 조회는 없는 번호를 찾는다. 자료구조마다 서로 다른 일을 시켜 놓고 빠르기를 비교하는 실수를 피하기 위한 설정이다.

요구사항을 연산 빈도로 바꾸기

어떤 연산이 얼마나 반복되는지 적은 것을 이 장에서는 작업 구성이라고 하겠다. 전공 수업에서는 이런 입력과 연산의 묶음을 작업 부하(workload)라고 부른다. 작업 구성이 바뀌면 유리한 자료구조도 바뀐다. 한 번 정렬한 뒤 수만 번 찾는 프로그램과, 값이 계속 들어오고 빠지는 프로그램은 같은 기준으로 고르기 어렵다.

전공 수업에서 시간 복잡도(time complexity)는 입력 크기가 커질 때 필요한 연산 수가 어떻게 증가하는지 나타내는 표현이다. O(n)은 항목 수에 비례해 증가하는 상한을, O(log n)은 탐색 범위를 반복해서 줄이는 형태의 상한을 나타낸다. O(1)도 실제 시간이 0이라는 뜻은 아니다. 입력 크기에 따라 횟수가 계속 늘어나지 않는다는 뜻이다. 여기서 n은 현재 저장한 항목 수다.

자주 수행하는 연산에서 자료구조 후보를 좁힌다

자주 하는 연산	후보	대표 비용	확인할 조건
위치 번호로 읽기	배열·동적 배열	O(1)	중간 삽입은 이동 필요
정확한 키 조회	해시 테이블	평균 O(1)	충돌과 여유 공간
고정된 자료에서 조회	정렬 배열	O(log n)	삽입은 최악 O(n)
변경과 범위 조회	균형 탐색 트리	삽입·단일 조회 O(log n)	범위 출력량은 별도
최우선 항목 꺼내기	힙	삽입·꺼내기 O(log n)	전체 정렬은 별도
도착 순서로 꺼내기	연결 큐·원형 큐	넣기·꺼내기 O(1)	용량 확장은 별도
접두사로 찾기	트라이	접두사 길이에 비례	결과 열거 비용 추가
같은 그룹인지 확인	유니온 파인드	최적화 시 분할 상환 O(α(n))	그룹 분리는 별도 문제

표의 분할 상환은 여러 연산의 총비용을 나누어 보는 방법이다. 특정 한 번의 비용과 구별해야 한다. α(n)은 전공 수업에서 역 아커만 함수라고 부르는, 매우 천천히 증가하는 함수다. 여기서는 앞 장의 경로 압축과 크기 기준 합치기를 함께 적용했을 때의 표기라는 점을 기억하면 된다. 이번 비교 코드에서는 그룹 연산을 수행하지 않으므로 이 비용을 측정하지 않는다.

평균 비용과 최악 비용도 구별한다. 해시 테이블의 평균 조회가 O(1)이라고 해서 모든 입력에서 비교 한 번으로 끝나는 것은 아니다. 여러 키가 같은 저장 후보 위치로 몰리는 충돌(collision)이 생기면 더 많은 칸을 검사한다. 균형을 유지하지 않는 이진 탐색 트리도 정렬된 입력을 받으면 한쪽으로 길게 늘어나 조회가 O(n)이 될 수 있다.

총비용을 생각할 때는 표 한 칸만 읽지 않는다. 삽입 횟수에 삽입 비용을 곱하고, 조회 횟수에 조회 비용을 곱한 뒤, 삭제와 결과 출력 비용도 더한다. 정확한 수식을 세우기 어렵더라도 어떤 항목이 지배적인지 확인할 수 있다. 조회가 대부분이고 갱신이 드물다면 정렬 배열을 유지하는 비용을 감수할 만하다. 반대로 중간 삽입이 반복된다면 배열의 값 이동이 부담이 될 수 있다.

메모리 사용량도 선택 기준이다. 연결 구조는 다음 노드를 가리키는 참조를 저장하고, 해시 테이블은 충돌을 줄이려고 빈 칸을 남긴다. 배열은 연속된 칸을 활용하지만 크기를 바꾸거나 중간을 비울 때 추가 작업이 생긴다. 비교 횟수가 적다는 이유만으로 전체 프로그램의 실행 시간이나 메모리 사용량까지 작다고 결론 내릴 수는 없다.

실무 사례와 면접 답변 연결하기

캐시는 조회와 퇴출을 함께 본다

캐시(cache)는 다시 사용할 가능성이 있는 결과를 보관하는 공간이다. 키로 값을 찾는 요구만 보면 해시 테이블이 어울린다. 그러나 용량이 가득 찼을 때 무엇을 내보낼지도 정해야 한다. 가장 오래 사용하지 않은 항목을 내보내는 정책을 전공 수업에서는 최근 최소 사용(LRU) 정책이라고 부른다.

이 정책은 해시 테이블과 이중 연결 리스트를 함께 사용하는 방식으로 구현할 수 있다. 해시 테이블은 키에서 노드를 찾고, 연결 리스트는 사용 순서를 관리한다. 조회한 노드를 앞쪽으로 옮기고 뒤쪽 노드를 제거한다. 이때 양방향 연결과 노드 참조가 있어야 해당 노드를 찾은 뒤 일정한 수의 연결 변경으로 이동할 수 있다. 단순히 “캐시는 해시 테이블”이라고 답하면 퇴출 요구가 빠진다.

랭킹은 몇 명을 보여 주는지 확인한다

랭킹에서 가장 높은 점수 하나가 필요한지, 상위 열 개가 필요한지, 모든 참가자의 순위가 필요한지 구별한다. 가장 높은 항목을 반복해서 꺼낸다면 최대 힙이 후보가 된다. 전체 결과를 가끔 출력하고 그 사이에는 점수가 바뀌지 않는다면 정렬한 배열을 보관하는 방법도 있다.

상위 k개만 유지한다면 크기 k의 최소 힙을 사용할 수 있다. 보관 중인 항목 가운데 가장 작은 점수를 새 후보와 비교해 남길 대상을 정한다. 다만 힙 안의 모든 항목이 순위대로 배치되는 것은 아니다. 특정 참가자의 정확한 순위를 빠르게 찾는 요구까지 있다면 추가 정보나 다른 구조가 필요하다.

검색은 정확 일치와 접두사를 구분한다

상품 번호의 정확한 일치 검색은 해시 테이블의 후보 작업이다. 이름의 앞부분이 같은 항목을 찾는 자동 완성은 트라이의 후보 작업이다. 가격이 두 경계 사이에 있는 항목을 찾는 작업은 정렬 배열이나 균형 탐색 트리를 검토할 수 있다. “검색이 빠른 구조”라는 하나의 답으로 이 세 요구를 대신하지 않는다.

검색 결과를 모두 반환하는 비용도 포함한다. 결과가 m개라면 m개를 전달하는 작업 자체가 필요하다. 탐색 시작점을 빨리 찾았더라도 결과가 많으면 전체 응답은 커진다. 면접에서 범위 검색을 설명할 때는 시작점을 찾는 비용과 결과를 방문하는 비용을 나누어 말하면 근거가 분명해진다.

작업 대기열은 순서와 변경을 확인한다

먼저 들어온 작업을 먼저 처리한다면 큐다. 우선순위가 높은 작업을 먼저 처리한다면 힙이다. 예약 시각이 빠른 작업을 먼저 처리하는 경우에도 시각을 기준으로 하는 최소 힙을 검토할 수 있다. 우선순위가 같은 작업의 도착 순서를 보장해야 한다면 삽입할 때 증가하는 번호를 함께 비교한다.

대기 중인 작업의 취소와 우선순위 변경이 잦다면 추가 설계가 필요하다. 힙만으로 임의의 작업 위치를 즉시 알 수는 없다. 작업 번호에서 힙 위치를 찾는 보조 구조를 두거나, 취소 표시 후 꺼낼 때 건너뛰는 방식을 검토한다. 자료구조 하나의 이름을 고른 뒤에도 실제 연산을 끝까지 따라가야 한다.

면접 질문에는 “무엇을 얼마나 자주 하는가, 어떤 순서를 보장하는가, 어떤 입력에서 나빠지는가”의 순서로 답해 보자. 예를 들어 “정확한 키 조회가 대부분이라 해시 테이블을 선택한다. 정렬 순서는 필요하지 않다. 충돌이 몰리거나 빈 칸이 부족해지면 비용이 늘어나므로 크기 조정 기준도 둔다”처럼 요구와 한계를 함께 설명한다.

비교 실험의 기준 정하기

공정한 비교에는 같은 입력, 같은 작업 순서, 같은 정답이 필요하다. 이번 실험은 키 여덟 개를 오름차순으로 넣은 뒤, 저장한 키 여덟 개와 없는 키 하나를 순서대로 찾는다. 배열은 순차 탐색을 하고, 정렬 배열은 이진 탐색을 한다. 해시 테이블은 충돌 시 다음 칸으로 이동한다. 이진 탐색 트리는 회전 없이 삽입한다.

측정 대상은 저장된 키와 요청한 키를 대조한 횟수다. 코드에서 cmp를 증가시키는 한 번을 키 대조 한 번으로 정의한다. 정렬 배열에서 대소 관계를 검사하고 이어서 같은지 검사하더라도 같은 위치의 키를 판정하는 한 단계를 한 번으로 센다. 따라서 이 값은 Python 비교 연산자 실행 횟수나 기계 명령 수가 아니다.

빈 칸 검사, 나머지 계산, 참조 이동과 값 복사는 세지 않는다. 해시 테이블은 빈 칸에 바로 들어가면 삽입 키 대조가 0이다. 그래도 삽입 자체의 비용은 있다. 정렬 배열 역시 값 이동을 세지 않으므로 이 실험 하나로 일반적인 삽입 비용을 판단해서는 안 된다. 측정하지 않은 일을 명시해야 숫자를 바르게 읽을 수 있다.

입력은 두 가지다. 첫 입력은 0부터 7까지다. 두 번째는 17의 배수 여덟 개다. 해시 테이블의 칸 수를 17로 정했으므로 두 번째 입력은 모두 같은 시작 칸으로 간다. 난수는 사용하지 않는다. 입력 자체가 고정되어 있어 실행할 때마다 같은 결과가 나온다.

마지막에는 내장 리스트와 딕셔너리로 같은 삽입·조회를 실행하고 결과를 검증한다. 앞선 구현의 내부 저장에는 고정 크기 리스트만 배열처럼 사용한다. 내장 구조의 내부 대조 횟수는 이 코드에서 알 수 없으므로 물음표로 표시한다. 대신 모든 구조에 삽입 여덟 번과 조회 아홉 번, 총 열일곱 번을 요청했다는 사실은 동일하게 출력한다. 요청 횟수와 내부 연산 횟수는 다른 값이다.

완성 코드

다음 내용을 main.py로 저장한다. 파일 하나로 실행하며 외부 패키지를 사용하지 않는다. 비교에 필요하지 않은 삭제·반복자·자동 확장은 포함하지 않았다. 각 구현은 중복 없는 정수 키를 받는다는 조건을 공유한다.

class Array:
    def __init__(self, capacity):
        self.data = [None] * capacity
        self.size = 0
        self.cmp = 0

    def add(self, key):
        if self.size == len(self.data):
            raise OverflowError("배열 용량 초과")
        self.data[self.size] = key
        self.size += 1

    def contains(self, key):
        for i in range(self.size):
            self.cmp += 1
            if self.data[i] == key:
                return True
        return False


class SortedArray(Array):
    def add(self, key):
        if self.size == len(self.data):
            raise OverflowError("배열 용량 초과")
        i = self.size
        while i > 0:
            self.cmp += 1
            if self.data[i - 1] <= key:
                break
            self.data[i] = self.data[i - 1]
            i -= 1
        self.data[i] = key
        self.size += 1

    def contains(self, key):
        lo = 0
        hi = self.size
        while lo < hi:
            mid = (lo + hi) // 2
            self.cmp += 1
            value = self.data[mid]
            if value == key:
                return True
            if value < key:
                lo = mid + 1
            else:
                hi = mid
        return False


class HashTable:
    def __init__(self, capacity):
        self.data = [None] * capacity
        self.cmp = 0

    def add(self, key):
        pos = key % len(self.data)
        for _ in range(len(self.data)):
            value = self.data[pos]
            if value is None:
                self.data[pos] = key
                return
            self.cmp += 1
            if value == key:
                return
            pos = (pos + 1) % len(self.data)
        raise OverflowError("해시 테이블 용량 초과")

    def contains(self, key):
        pos = key % len(self.data)
        for _ in range(len(self.data)):
            value = self.data[pos]
            if value is None:
                return False
            self.cmp += 1
            if value == key:
                return True
            pos = (pos + 1) % len(self.data)
        return False


class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


class SearchTree:
    def __init__(self, capacity):
        self.root = None
        self.cmp = 0

    def add(self, key):
        if self.root is None:
            self.root = Node(key)
            return
        node = self.root
        while True:
            self.cmp += 1
            if key == node.key:
                return
            if key < node.key:
                if node.left is None:
                    node.left = Node(key)
                    return
                node = node.left
            else:
                if node.right is None:
                    node.right = Node(key)
                    return
                node = node.right

    def contains(self, key):
        node = self.root
        while node is not None:
            self.cmp += 1
            if key == node.key:
                return True
            if key < node.key:
                node = node.left
            else:
                node = node.right
        return False


def show(name, insert_cmp, find_cmp):
    print(f"{name}: 삽입={insert_cmp}, 조회={find_cmp}, 요청=17")


def run_custom(name, factory, step):
    structure = factory(17)
    for i in range(8):
        structure.add(i * step)
    insert_cmp = structure.cmp
    structure.cmp = 0
    hits = 0
    for i in range(9):
        found = structure.contains(i * step)
        if found != (i < 8):
            raise AssertionError("조회 결과 불일치")
        if found:
            hits += 1
    if hits != 8:
        raise AssertionError("성공 횟수 불일치")
    show(name, insert_cmp, structure.cmp)


def run_builtin(step):
    values = [None] * 8
    mapping = {}
    for i in range(8):
        key = i * step
        values[i] = key
        mapping[key] = True
    list_hits = 0
    dict_hits = 0
    for i in range(9):
        key = i * step
        list_found = key in values
        dict_found = key in mapping
        expected = i < 8
        if list_found != expected or dict_found != expected:
            raise AssertionError("내장 결과 불일치")
        if list_found:
            list_hits += 1
        if dict_found:
            dict_hits += 1
    if list_hits != 8 or dict_hits != 8:
        raise AssertionError("내장 성공 횟수 불일치")
    show("내장 list", "?", "?")
    show("내장 dict", "?", "?")


def run_case(title, step):
    print(title)
    print("키 대조 횟수 / 요청 = 삽입 8회 + 조회 9회")
    run_custom("배열", Array, step)
    run_custom("정렬 배열", SortedArray, step)
    run_custom("해시 테이블", HashTable, step)
    run_custom("이진 탐색 트리", SearchTree, step)
    run_builtin(step)
    print("검증: 모든 구조에서 조회 8회 성공, 1회 실패")


def main():
    run_case("[분산 입력]", 1)
    print()
    run_case("[충돌 입력]", 17)


if __name__ == "__main__":
    main()

줄별 해설

저장 공간과 계수기를 준비한다

Array.__init__의 [None] * capacity는 정해진 수의 칸을 만든다. 이후 append나 중간 삽입 기능을 호출하지 않는다. size는 실제 사용 중인 칸 수이며, cmp는 키 대조 횟수다. add는 다음 빈 칸에 키를 기록한다. 기존 키를 검사하지 않으므로 삽입 대조 횟수는 0이다.

Array.contains는 사용 중인 칸만 차례로 방문한다. 성공하면 즉시 돌아오고, 끝까지 같은 키가 없으면 실패한다. 여덟 키를 차례로 찾을 때 대조 횟수는 1부터 8까지다. 없는 키는 여덟 번을 더 대조하므로 총합은 44다. 저장된 키 수가 늘면 실패 조회 한 번의 대조 횟수도 같은 만큼 늘어난다.

정렬 상태가 줄여 주는 일을 확인한다

SortedArray(Array)는 배열의 저장 공간 초기화를 물려받고 삽입과 조회를 바꾼다. add의 반복문은 뒤쪽 키를 검사하면서 필요한 만큼 오른쪽으로 옮긴다. 이번 입력은 오름차순이므로 첫 삽입을 제외하면 마지막 키 한 번만 대조하고 멈춘다. 따라서 삽입 대조는 7번이며 이동은 없다.

contains의 lo와 hi는 탐색할 구간의 시작과 끝 다음 위치다. 전공 수업에서는 끝을 포함하지 않는 반열린 구간이라고 부른다. 가운데 키보다 요청 키가 크면 앞부분을 제외하고, 작으면 뒷부분을 제외한다. 각 조회의 대조 횟수는 순서대로 4, 3, 2, 3, 1, 3, 2, 3, 3이며 총 24다. 단순히 절반이라는 비율보다, 한 단계마다 남는 구간이 줄어든다는 점이 중요하다.

해시 충돌과 트리 모양을 드러낸다

HashTable.add는 키를 칸 수로 나눈 나머지에서 시작한다. 이미 값이 있으면 키를 대조하고 다음 칸으로 이동한다. 이 방식은 전공 수업에서 선형 조사(linear probing)라고 부른다. 반복 횟수를 칸 수로 제한했으므로 테이블이 가득 차도 무한히 돌지 않는다. 삭제는 구현하지 않았으므로 조회 중 빈 칸을 만나면 탐색을 끝낼 수 있다.

분산 입력은 서로 다른 칸에 바로 들어간다. 삽입 키 대조는 0번이고, 성공 조회 여덟 번에서 각각 한 번씩 대조한다. 없는 키 8은 빈 칸을 만나므로 키 대조가 없다. 충돌 입력에서는 앞서 저장한 키를 지나서 삽입한다. 삽입 대조 합은 0부터 7까지 더한 28이고, 조회 합은 배열과 같은 44다.

Node는 키와 두 자식 참조를 가진다. SearchTree의 삽입은 요청 키의 대소에 따라 한쪽 자식으로 내려간다. 이번 입력은 계속 커지므로 모든 노드가 오른쪽으로 이어진다. 삽입 대조는 28번, 조회 대조는 44번이다. “이진 탐색 트리이므로 항상 로그 비용”이라는 주장을 이 입력이 반박한다. 균형 유지가 왜 별도의 요구였는지 연결해서 볼 수 있다.

측정과 검증을 분리한다

run_custom은 구조를 만든 뒤 삽입을 끝내고 계수기를 저장한다. 이어서 계수기를 0으로 돌려 조회만 센다. found != (i < 8)는 각 요청의 정답을 확인한다. 성공 횟수만 맞추면 잘못된 키에서 성공하고 다른 키에서 실패한 오류를 놓칠 수 있으므로 요청별 결과도 검사한다.

run_builtin은 같은 키를 내장 리스트와 딕셔너리에 넣는다. 딕셔너리의 값은 존재 여부 비교에 중요하지 않아 True로 통일했다. 여기서 요청 열의 17은 자료구조 수준의 논리적 작업 수다. 직접 구현의 add 호출과 내장 구조의 대입을 같은 삽입 요청으로 취급한다. 내부 메서드 호출 수를 뜻하지 않는다.

show는 숫자와 물음표를 같은 형식으로 출력한다. SearchTree.__init__의 capacity는 다른 구조와 생성 호출을 맞추기 위한 매개변수이며 트리의 용량을 제한하지 않는다. 마지막 실행 조건은 이 파일을 직접 실행했을 때만 main을 호출한다. 모든 검증은 불일치할 때 예외를 발생시키므로 결과가 다르면 조용히 비교표를 계속 출력하지 않는다.

실행 결과

다음 명령으로 실행한다. 물음표는 측정하지 않은 내부 횟수다. 0과 구별해서 읽어야 한다.

python3 main.py

[분산 입력]
키 대조 횟수 / 요청 = 삽입 8회 + 조회 9회
배열: 삽입=0, 조회=44, 요청=17
정렬 배열: 삽입=7, 조회=24, 요청=17
해시 테이블: 삽입=0, 조회=8, 요청=17
이진 탐색 트리: 삽입=28, 조회=44, 요청=17
내장 list: 삽입=?, 조회=?, 요청=17
내장 dict: 삽입=?, 조회=?, 요청=17
검증: 모든 구조에서 조회 8회 성공, 1회 실패

[충돌 입력]
키 대조 횟수 / 요청 = 삽입 8회 + 조회 9회
배열: 삽입=0, 조회=44, 요청=17
정렬 배열: 삽입=7, 조회=24, 요청=17
해시 테이블: 삽입=28, 조회=44, 요청=17
이진 탐색 트리: 삽입=28, 조회=44, 요청=17
내장 list: 삽입=?, 조회=?, 요청=17
내장 dict: 삽입=?, 조회=?, 요청=17
검증: 모든 구조에서 조회 8회 성공, 1회 실패

두 입력에서 정렬 배열의 횟수가 같은 이유는 키의 상대적인 순서가 같기 때문이다. 해시 테이블은 키의 나머지 값에 영향을 받으므로 결과가 달라진다. 트리는 키 사이의 간격보다 삽입 순서와 그에 따른 모양에 영향을 받는다. 같은 정수 집합이라도 어떤 특성이 구조에 영향을 주는지 구별할 수 있다.

다만 여덟 개짜리 실험만으로 복잡도를 증명할 수는 없다. 이 코드는 수업에서 분석한 경로를 실제 횟수와 연결하는 확인 도구다. 크기를 늘리는 실험에서는 배열과 기울어진 트리의 실패 조회가 n번, 이진 탐색의 한 번 조회가 최대 약 log₂(n) + 1번의 대조를 하는지 살핀다. 전체 조회 횟수까지 함께 늘렸다면 한 번의 비용과 전체 비용을 따로 읽어야 한다.

실무에서 자주 틀리는 것

누적된 계수기를 조회 비용으로 출력한다

다음 코드는 삽입 비용까지 포함한 값을 조회 비용이라고 부른다. 같은 계수기를 재사용할 때 측정 경계를 분명하게 나눈다. 아래 조각들은 완성 코드의 클래스가 정의된 상태에서 실행할 수 있다.

# 틀린 코드
table = HashTable(17)
table.add(0)
table.add(17)
table.contains(17)
print("조회 대조:", table.cmp)  # 삽입 대조도 포함된다.

# 고친 코드
table = HashTable(17)
table.add(0)
table.add(17)
table.cmp = 0
table.contains(17)
print("조회 대조:", table.cmp)  # 2

빠른 조회 결과만 보고 정답 검증을 생략한다

모든 조회에 실패를 반환하는 잘못된 구현도 대조 횟수만 보면 작게 나올 수 있다. 결과 검증을 측정과 함께 둔다. 실제로 저장된 키와 저장하지 않은 키를 모두 확인해야 한다.

# 틀린 코드
table = HashTable(17)
table.add(3)
table.contains(3)
print(table.cmp)

# 고친 코드
table = HashTable(17)
table.add(3)
if not table.contains(3):
    raise AssertionError("저장한 키를 찾지 못함")
if table.contains(4):
    raise AssertionError("없는 키를 찾았다고 응답함")
print("조회 결과 확인")

배열의 맨 앞을 지우며 큐라고 생각한다

내장 리스트의 첫 항목 제거는 뒤의 값들을 당기는 작업이 필요하다. 직접 만든 큐에서도 매번 전체를 옮기면 같은 문제가 생긴다. 고정 크기 배열에 읽을 위치를 따로 두면 꺼낼 때 이동을 피할 수 있다. 다음 코드는 이미 채워진 두 칸에서 한 항목을 꺼내는 부분만 보여 준다. 반복해서 넣으려면 앞 장의 원형 큐처럼 쓰기 위치와 빈 공간도 관리한다.

# 틀린 코드
pending = [10, 20]
job = pending.pop(0)

# 고친 코드
storage = [None] * 4
storage[0] = 10
storage[1] = 20
head = 0
size = 2
job = storage[head]
storage[head] = None
head = (head + 1) % len(storage)
size -= 1
print(job, size)  # 10 1

내장 구현의 내부 횟수를 추정값으로 채운다

메서드를 한 번 호출했다고 내부 작업도 한 번인 것은 아니다. 내장 구현을 감싼 함수에서 요청 횟수를 셀 수는 있지만, 그것을 내부 대조 횟수로 바꾸어 적지 않는다. 측정 불가도 실험 결과의 일부다.

# 틀린 코드
mapping = {3: True}
found = 3 in mapping
internal_comparisons = 1
print(found, internal_comparisons)

# 고친 코드
mapping = {3: True}
lookup_requests = 0
lookup_requests += 1
found = 3 in mapping
internal_comparisons = None
print(found, lookup_requests, internal_comparisons)

한눈에 보기

관측한 숫자를 요구사항과 구현 조건에 연결한다

관찰	이번 결과	선택에 주는 의미	빠진 비용
배열 순차 조회	44회 대조	적은 자료에는 단순함이 장점	실제 경과 시간
정렬 배열 조회	24회 대조	정렬 유지가 탐색 범위를 줄임	삽입 시 값 이동
해시 분산 입력	조회 8회 대조	분산이 좋으면 경로가 짧음	빈 칸 검사·해시 계산
해시 충돌 입력	조회 44회 대조	평균 비용에는 조건이 있음	크기 조정
기울어진 탐색 트리	조회 44회 대조	균형 유지 여부를 확인함	노드 할당·참조 이동
내장 구현	결과 일치·요청 17회	정답 비교의 기준으로 사용함	내부 대조 횟수

이 책은 자료구조를 만드는 쪽에서 저장 공간과 연산 경로를 살폈다. 《논리로 푸는 알고리즘》이 자료구조를 사용하는 쪽의 문제 해결을 다룬다면, 여기서 얻은 근거는 그 선택을 설명하는 데 쓰인다. 어떤 구조를 쓸지 망설여질 때는 반복되는 질문을 적고, 후보 구현에서 그 질문이 지나가는 경로를 따라가면 된다.

연습 문제

1. 분산 입력에서 조회만 두 번씩 반복하면 각 직접 구현의 조회 대조 횟수와 전체 요청 횟수는 얼마가 되는가. 삽입은 한 번만 수행한다고 가정한다. 조회 반복문을 바꾸어 확인하라.
2. 정렬 배열에 7부터 0까지 역순으로 삽입하면 삽입 대조 횟수와 값 이동 횟수는 각각 얼마인가. SortedArray에 이동 계수기를 추가해 확인하라. 조회 순서는 기존과 같게 유지하라.
3. 작업 번호로 자주 조회하고, 가장 오래 사용하지 않은 작업을 용량 초과 시 제거해야 한다. 구조 두 개를 조합해 설명하고, 조회 성공 시 바뀌는 상태를 적어라.
4. “이 실험에서 해시 테이블의 조회가 8회 대조였으므로 어떤 입력에서도 가장 빠르다”라는 결론의 문제점을 세 가지 적어라.

정답과 해설

1. 배열은 88회, 정렬 배열은 48회, 해시 테이블은 16회, 이진 탐색 트리는 88회다. 조회가 상태를 바꾸지 않으므로 기존 횟수의 두 배다. 전체 요청은 삽입 8회와 조회 18회를 더한 26회다. 완성 코드의 조회 반복문 바깥에 for _ in range(2):를 추가하고, 성공 횟수 기대값을 16으로 바꾼다. 출력 함수의 요청 수도 26으로 바꿔야 표시와 실제 작업이 일치한다.

2. 삽입 대조와 이동은 각각 28회다. 새 키는 기존 키보다 항상 작아서 앞서 저장한 키를 모두 검사하고 한 칸씩 옮긴다. 각 합은 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7이다. 초기화에서 self.moves = 0을 두고, self.data[i] = self.data[i - 1] 다음에 self.moves += 1을 넣는다. 최종 저장 순서는 같으므로 기존 순서로 조회하면 조회 대조는 여전히 24회다. 이는 키 대조 외에 값 이동도 측정해야 하는 이유를 보여 준다.

3. 해시 테이블과 이중 연결 리스트를 조합한다. 해시 테이블의 값에는 작업 노드의 참조를 저장한다. 조회에 성공하면 해당 노드를 현재 위치에서 떼어 가장 최근 사용 위치로 옮긴다. 용량을 넘으면 가장 오래 사용한 위치의 노드를 리스트와 해시 테이블에서 함께 제거한다. 두 구조가 같은 작업 집합을 나타내도록 갱신해야 한다.

4. 첫째, 충돌 입력에서는 조회 대조가 44회로 늘었다. 둘째, 비교표는 빈 칸 검사·해시 계산·메모리 사용·경과 시간을 측정하지 않았다. 셋째, 정렬 순서나 범위 조회처럼 다른 요구사항을 실험하지 않았다. 따라서 결론은 “이번 분산 입력의 정확 일치 조회에서 측정한 키 대조가 가장 적었다”까지다. 선택의 근거를 측정한 범위 안에서 말하는 것이 중요하다.