자료구조 - 고르는 기준이 성능을 바꾼다

이 장에서 배우는 것

앞 장에서 집합은 원소의 모임이고, 그래프는 대상 사이의 관계를 나타내는 방법이라고 살펴보았다. 이번에는 그 원소와 관계를 프로그램 안에 어떤 형태로 담을지 정한다. 같은 과목 목록이라도 순서대로 보여 줄 때와 이미 공부한 과목인지 확인할 때 필요한 작업이 다르다. 저장할 값만 보고 그릇을 고르면, 데이터가 늘어난 뒤에 자주 실행하는 작업이 느려질 수 있다.

값을 저장하고 연결하는 방식을 전공 수업에서는 자료구조(data structure)라고 부른다. 이 과목의 핵심은 구조의 이름을 많이 외우는 데 있지 않다. 어떤 작업을 반복하는지 찾고, 그 작업에 맞는 구조를 고르며, 선택에 따르는 비용을 설명하는 데 있다. 이번 장에서는 다음 네 가지를 확인한다.

• 배열과 연결 리스트가 원소를 찾고 추가하는 방식의 차이를 설명한다.
• 해시, 트리, 힙을 포함 검사, 계층 표현, 우선순위 처리에 연결한다.
• 입력 크기가 늘어날 때 작업량이 어떻게 변하는지 시간 복잡도로 비교한다.
• 학습 과목 목록을 이용해 리스트와 집합의 포함 검사 시간을 측정하고, 측정 결과의 한계를 설명한다.

문제 상황

다른 분야를 공부하다 개발 일을 시작한 사람이 학습 기록 프로그램을 만든다고 하자. 화면에는 공부할 과목을 원하는 순서로 보여 준다. 이미 공부한 과목에는 표시를 붙인다. 과목별 세부 주제는 부모와 자식 관계로 묶고, 오늘 공부할 항목은 우선순위에 따라 하나씩 꺼낸다.

처음에는 모든 데이터를 리스트에 넣어도 충분하다. 그런데 기록이 과목에서 세부 개념과 연습 항목으로 늘어나면, 화면을 만들 때마다 “이 항목을 이미 공부했는가”라는 검사가 반복된다. 리스트의 앞부분에 있는 항목은 빨리 찾지만, 없는 항목은 끝까지 살펴봐야 한다. 같은 검사를 여러 번 수행한다면 이 차이가 쌓인다.

여기서 필요한 질문은 “리스트가 느린가”가 아니다. “순서가 필요한 데이터인가”, “포함 검사가 얼마나 반복되는가”, “중복을 보존해야 하는가”다. 화면 순서를 위한 리스트와 이수 여부를 위한 집합을 함께 두는 선택도 가능하다. 자료구조를 고르는 일은 이런 요구사항을 저장 방식으로 번역하는 작업이다.

저장 위치와 연결 방식이 작업 비용을 바꾼다

배열과 Python 리스트

원소를 연속된 칸에 저장하고 위치 번호로 접근하는 구조를 배열(array)이라고 한다. 위치 번호는 인덱스(index)라고 부른다. 첫 칸의 위치와 한 칸의 크기를 알면 특정 번호의 칸으로 바로 갈 수 있다. 반면 중간에 빈자리를 만들려면 뒤쪽 원소를 옮겨야 한다.

Python의 리스트는 크기를 늘릴 수 있는 배열 방식으로 구현된다. 다만 리스트의 연속된 칸에는 객체 자체가 아니라 객체를 가리키는 참조가 들어간다. 참조는 값을 찾아갈 수 있게 하는 연결 정보다. 리스트 안의 문자열 객체까지 모두 나란히 놓인다는 뜻은 아니다.

완성 코드의 courses[1]은 두 번째 참조 칸을 바로 읽는다. courses.insert(1, "이산수학")은 그 위치 뒤의 참조들을 옮겨 자리를 만든다. 위치로 읽는 일과 중간에 넣는 일은 같은 리스트에서 일어나지만 비용이 다르다. 리스트 끝에 붙이는 append는 대체로 빠르지만, 확보한 공간이 부족하면 더 큰 저장 공간을 마련하고 참조들을 옮겨야 한다.

연결 리스트는 무엇을 연결하는가

값과 다음 원소를 가리키는 정보를 한 묶음으로 저장한 뒤, 묶음끼리 연결하는 구조를 연결 리스트(linked list)라고 한다. 각 묶음은 노드(node)다. 첫 노드에서 출발해 다음 연결을 따라가므로, 다섯 번째 원소를 읽으려면 앞의 연결들을 거쳐야 한다.

연결 리스트는 삽입할 위치의 노드를 이미 알고 있으면 연결 몇 개를 바꾸어 원소를 끼울 수 있다. 하지만 “값이 자료구조인 노드를 찾아 그 뒤에 삽입하라”는 요청이라면 먼저 찾는 시간이 필요하다. 전공 면접에서 삽입 비용을 물을 때 이 조건을 빠뜨리기 쉽다.

완성 코드에서는 값과 다음 노드를 담은 사전으로 작은 연결 리스트를 만든다. 사전은 키와 값을 짝지어 저장하는 Python 자료형이다. 실제 서비스용 연결 리스트를 만드는 목적이 아니라, next에 저장된 참조를 따라가는 동작을 확인하기 위한 모델이다. 마지막 노드의 다음 값은 연결이 없음을 나타내는 None으로 둔다.

실무에서는 직접 연결 리스트를 구현하기 전에 필요한 작업을 제공하는 표준 자료형을 살펴보는 편이 좋다. 예를 들어 양쪽 끝에서 자주 넣고 빼는 작업에는 collections.deque가 있다. 구조 이름과 구현 연습, 실제 도구 선택은 서로 구분해서 생각해야 한다.

찾기·계층·우선순위에 맞는 구조를 고른다

해시는 위치를 좁혀 찾는다

값을 계산에 넣어 저장 위치를 정하는 데 사용할 수 있는 정수로 바꾸는 것을 해시(hash)라고 한다. 이 계산 결과를 이용해 저장 공간의 일부부터 살펴보는 구조가 해시 테이블이다. Python의 set과 dict는 해시 테이블을 바탕으로 한다. set은 중복 없는 원소를, dict는 키와 값의 짝을 저장한다.

리스트에서 없는 값을 확인하려면 모든 원소와 비교해야 한다. 집합은 해시를 이용해 살펴볼 위치를 좁힌다. 다만 서로 다른 값이 같은 해시 결과를 가질 수 있다. 이를 충돌(collision)이라고 하며, 충돌이 나면 값이 실제로 같은지 추가로 확인해야 한다. 따라서 집합의 포함 검사를 “항상 한 번만 비교한다”라고 설명하면 부정확하다.

집합에 넣을 값은 저장된 동안 해시와 동등성 판단이 일관되게 유지되어야 한다. 일반적인 문자열과 정수는 집합 원소로 사용할 수 있지만, 내용이 바뀌는 리스트는 사용할 수 없다. 또한 집합은 학습 순서를 표현하는 도구가 아니다. 완성 코드에서는 집합 자체를 출력하지 않고 포함 검사 결과만 출력해 실행마다 같은 내용을 보게 한다.

트리는 부모와 자식의 관계를 담는다

각 항목 아래에 하위 항목이 이어지는 계층 구조를 트리(tree)라고 한다. 가장 위의 노드는 루트, 바로 아래로 연결된 노드는 자식, 그 위의 노드는 부모다. 자식이 없는 노드는 잎이라고 부른다. 학습 과목 아래에 세부 주제를 묶는 일, 폴더 구조를 표현하는 일에 잘 맞는다.

트리라고 해서 검색이 저절로 빨라지지는 않는다. 검색에 쓰는 이진 탐색 트리는 한 노드의 자식을 최대 둘로 제한하고, 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값을 두는 규칙을 사용한다. 이때 루트에서 아래로 몇 번 내려가는지가 중요하다. 가장 긴 내려가는 경로의 간선 수를 트리의 높이라고 한다.

노드들이 한쪽으로만 이어지면 높이가 커져 연결 리스트처럼 순서대로 찾아야 할 수 있다. 높이가 지나치게 커지지 않도록 유지하는 트리를 균형 탐색 트리라고 부른다. 이번 코드의 트리는 검색용 구현이 아니라 과목의 하위 주제를 표현한 일반 트리다. 두 용도를 섞지 않아야 한다.

힙은 가장 급한 항목을 꺼내는 데 맞는다

지금 처리할 항목 중 우선순위가 가장 높은 것을 반복해서 꺼내는 저장 방식을 우선순위 큐(priority queue)라고 한다. 이를 구현하는 대표 구조가 힙(heap)이다. Python 표준 라이브러리의 heapq는 가장 작은 값이 맨 앞에 오도록 유지하는 최소 힙을 제공한다.

최소 힙은 부모 값이 자식 값보다 크지 않게 유지한다. 이 규칙은 전체 원소가 정렬되어 있다는 뜻이 아니다. 맨 앞의 최소값은 바로 확인할 수 있지만, 그다음 칸이 두 번째로 작은 값이라고 가정해서는 안 된다.

완성 코드에서는 숫자가 작을수록 먼저 공부한다고 정하고, 우선순위 숫자와 과목 이름을 묶어 넣는다. 여러 값을 순서대로 묶는 Python 자료형을 튜플이라고 한다. 튜플은 앞 요소부터 비교하므로, 우선순위가 같으면 문자열 이름으로 순서를 정한다. 입력 순서까지 보존해야 한다면 중간에 순번을 넣는 방법이 필요하다.

시간 복잡도는 입력 증가에 대한 설명이다

입력 크기가 커질 때 필요한 작업량이 어떤 속도로 늘어나는지 나타내는 것을 시간 복잡도(time complexity)라고 한다. 여기서는 원소 수를 n이라고 쓴다. 전공 수업에서는 증가 양상을 설명할 때 O 표기법을 자주 사용한다. O(1)은 입력 크기가 늘어도 작업량이 일정한 범위에 머무는 형태이고, O(n)은 입력 크기에 비례해 늘어나는 형태다. 실제 몇 초인지를 직접 알려 주는 표시는 아니다.

O(log n)은 후보 범위가 일정 비율로 줄거나, 균형 잡힌 트리의 층을 따라 이동할 때 나타나는 형태다. n이 두 배가 되어도 필요한 단계는 조금만 늘어난다. 이 장에서는 로그를 계산하는 공식보다 “전체 원소를 훑는가, 몇 층만 내려가는가”를 먼저 구별하면 된다.

같은 구조에서도 작업과 조건에 따라 비용이 다르다

구조	작업	시간 복잡도	조건
Python 리스트	인덱스로 읽기	O(1)	유효한 위치를 안다
Python 리스트	값 포함 검사	O(n)	최악에는 끝까지 비교한다
Python 리스트	끝에 추가	분할 상환 O(1)	한 번의 확장은 O(n)일 수 있다
연결 리스트	노드 뒤에 삽입	O(1)	해당 노드를 이미 안다
해시 테이블	포함 검사	평균 O(1), 최악 O(n)	해시 계산과 비교 비용을 일정하다고 본다
균형 탐색 트리	값 검색	O(log n)	높이의 균형을 유지한다
최소 힙	최소값 확인 / 꺼내기	O(1) / O(log n)	꺼낸 뒤 힙 규칙을 복구한다

여러 번의 작업에 든 총비용을 작업 수로 나누어 보는 분석을 분할 상환 분석(amortized analysis)이라고 한다. 리스트 끝에 추가할 때 가끔 큰 복사가 생겨도, 긴 추가 작업 전체로 보면 한 번당 비용을 일정한 수준으로 설명할 수 있다는 뜻이다. 무작위 입력의 평균을 구한다는 뜻과는 다르다.

메모리 사용량이 입력 크기에 따라 어떻게 늘어나는지는 공간 복잡도라고 한다. 이미 있는 리스트로부터 집합을 만들면 원소 수에 비례하는 추가 저장 공간과 변환 시간이 필요하다. 포함 검사 한 번을 위해 큰 집합을 새로 만드는 것이 유리하다고 단정할 수 없다. 반면 만들어 둔 집합을 반복해서 조회한다면 변환 비용을 여러 조회에 걸쳐 나누어 생각할 수 있다.

면접에서는 “리스트와 집합 중 무엇이 빠른가”라는 질문 뒤에 조건을 붙여 답하는 편이 좋다. 포함 검사인지, 위치로 읽기인지, 순서를 보존해야 하는지, 집합 생성 비용을 포함하는지부터 말한다. “연결 리스트 삽입은 왜 빠른가”에는 위치를 찾는 비용과 연결을 바꾸는 비용을 나누어 답한다. “힙과 정렬된 리스트의 차이는 무엇인가”에는 전체 순서 보장 여부와 반복해서 최소값을 꺼내는 작업을 연결한다.

완성 코드

다음 내용을 main.py로 저장한다. 외부 패키지와 네트워크를 사용하지 않으며 난수도 사용하지 않는다. 앞부분은 구조별 동작을 확인하고, 뒷부분은 리스트와 집합에 같은 포함 검사를 실행한다.

실제 경과 시간은 컴퓨터 상태에 따라 달라지므로, 정확한 시간값을 출력하면서 출력 전체를 고정할 수는 없다. 이 프로그램은 시간을 측정하고 차이와 비율까지 계산해 반환값에 보관하되, 표준 출력에는 고정된 검사 결과만 표시한다. 실행 결과의 재현성과 시간 측정의 변동성을 구분하기 위한 구성이다.

from heapq import heapify, heappop
from time import perf_counter_ns


def structure_demo():
    courses = ["자료구조", "운영체제"]
    courses.insert(1, "이산수학")
    print("리스트 두 번째:", courses[1])

    tail = {"value": "자료구조", "next": None}
    head = {"value": "이산수학", "next": tail}
    middle = {"value": "논리", "next": head["next"]}
    head["next"] = middle
    names = []
    node = head
    while node is not None:
        names.append(node["value"])
        node = node["next"]
    print("연결 순서:", " -> ".join(names))

    completed = {"이산수학", "자료구조", "자료구조"}
    print("집합 원소 수:", len(completed))
    print("자료구조 이수:", "자료구조" in completed)

    tree = {"자료구조": ["배열", "해시", "트리"]}
    print("하위 주제:", ", ".join(tree["자료구조"]))

    tasks = [(3, "네트워크"), (1, "자료구조"), (2, "운영체제")]
    heapify(tasks)
    print("먼저 공부:", heappop(tasks)[1])


def count_hits(container, queries):
    hits = 0
    for value in queries:
        if value in container:
            hits += 1
    return hits


def measure(container, queries, repeats):
    best_ns = None
    expected_hits = None
    for _ in range(repeats):
        start = perf_counter_ns()
        hits = count_hits(container, queries)
        elapsed_ns = perf_counter_ns() - start
        if expected_hits is None:
            expected_hits = hits
        elif hits != expected_hits:
            raise RuntimeError("반복 중 검사 결과가 달라졌다")
        if best_ns is None or elapsed_ns < best_ns:
            best_ns = elapsed_ns
    return best_ns, expected_hits


def main():
    structure_demo()
    size = 10_000
    records = list(range(size))
    record_set = set(records)
    queries = [size - 1, size] * 100
    repeats = 3

    count_hits(records, queries)
    count_hits(record_set, queries)
    list_ns, list_hits = measure(records, queries, repeats)
    set_ns, set_hits = measure(record_set, queries, repeats)
    if list_hits != set_hits:
        raise RuntimeError("두 구조의 검사 결과가 다르다")

    timings = {
        "list_ns": list_ns,
        "set_ns": set_ns,
        "difference_ns": list_ns - set_ns,
        "list_over_set": list_ns / set_ns if set_ns else None,
    }
    print("기록 수:", size)
    print("포함 검사 수:", len(queries))
    print("찾은 수:", list_hits, "/", set_hits)
    print("결과 일치:", list_hits == set_hits)
    print("시간 측정:", repeats, "회씩 완료")
    print("실측 시간과 비율: 반환값에 보관")
    return timings


if __name__ == "__main__":
    main()

줄별 해설

첫 두 줄은 표준 라이브러리에서 필요한 함수를 가져온다. heapify는 기존 리스트를 힙 규칙에 맞게 바꾸고, heappop은 최소값을 꺼낸다. perf_counter_ns는 짧은 경과 시간을 측정할 때 쓸 수 있는 시계의 값을 정수로 반환한다. 단위는 나노초지만, 시계가 실제로 구별하는 최소 시간 간격까지 반드시 1나노초라는 뜻은 아니다.

structure_demo의 courses 두 줄은 리스트 중간에 값을 넣고 인덱스로 읽는 예다. 이후 tail과 head는 연결된 노드를 표현한다. middle을 만들 때 기존 다음 노드를 먼저 연결하고, 그다음 head의 다음 연결을 middle로 바꾼다. 이 순서 덕분에 기존 tail로 가는 길이 유지된다.

while 문은 연결이 없는 None을 만날 때까지 다음 노드로 이동한다. 이런 식으로 구조의 원소를 차례로 방문하는 작업을 순회라고 한다. names는 방문 순서를 출력하기 위한 별도 리스트다. 연결 리스트 자체가 리스트로 변한 것은 아니다.

completed에는 같은 문자열을 두 번 적었지만 집합은 중복을 남기지 않는다. 따라서 원소 수는 2다. tree는 부모 이름을 키로, 자식 이름 목록을 값으로 갖는 한 층짜리 트리 표현이다. tasks에서는 heapify 이후 heappop으로 우선순위 1인 항목을 꺼낸다. 이 예는 힙의 내부 배열 전체를 정렬된 목록처럼 사용하지 않는다.

count_hits는 컨테이너와 검사할 값 목록을 받는다. 컨테이너는 여러 값을 담는 객체를 통틀어 부르는 말이다. 같은 함수에 리스트와 집합을 각각 전달하므로 바뀌는 것은 포함 검사를 수행하는 자료구조다. 발견할 때마다 hits에 1을 더하고 마지막에 횟수를 반환한다.

measure는 같은 검사를 repeats번 측정한다. 시작 시각과 종료 시각의 차이가 한 번의 경과 시간이다. expected_hits는 반복마다 결과가 같은지 확인하고, best_ns는 관측한 시간 중 가장 작은 값을 보관한다. 최솟값을 택하면 다른 작업에 방해받아 길어진 측정의 영향을 줄일 수 있지만, 그것만으로 정확성이 보장되지는 않는다.

main의 records는 0부터 9,999까지 담는다. queries는 마지막 원소인 9,999와 존재하지 않는 10,000을 100번씩 번갈아 담는다. 두 경우 모두 리스트에서는 거의 전체를 살펴봐야 하므로 선형 탐색의 비용이 드러나기 쉽다. 반면 앞쪽 원소만 찾는 업무까지 대표하는 입력은 아니다.

집합 생성은 측정 전에 끝난다. 따라서 이 실험은 이미 준비된 구조를 조회하는 비용을 비교한다. 측정 전 count_hits를 한 번씩 호출하는 것은 같은 코드를 미리 실행해 보는 준비 과정이다. 측정에는 함수 호출, 반복문, 조건 검사와 합계 증가 비용도 포함된다. 포함 검사 한 동작만 완전히 분리한 시간은 아니다.

timings는 두 측정값, 차이, 비율을 보관한다. 차이가 양수면 리스트 쪽 관측 시간이 더 길었다는 뜻이다. 비율이 5라면 이 입력과 실행에서 리스트가 집합보다 다섯 배의 시간이 걸렸다는 뜻이며, 모든 환경의 보장값은 아니다. 드물게 측정값이 0이면 나누기를 피하고 None을 기록한다.

마지막 조건문은 파일을 직접 실행했을 때 main을 호출한다. 반환된 사전은 자동으로 출력되지 않는다. 시간값을 살펴보고 싶다면 코드를 읽을 때 main의 반환값을 확인하면 된다. 어떤 구조가 빠를 것이라는 기대를 강제하는 검사문은 넣지 않았다. 실행 환경에 따른 속도 차이를 프로그램 오류로 취급해서는 안 되기 때문이다.

실행 결과

macOS 또는 Linux에서 다음 명령으로 실행한다. 시간값을 출력하지 않으므로 아래 출력은 실행마다 같다.

python3 main.py

리스트 두 번째: 이산수학
연결 순서: 이산수학 -> 논리 -> 자료구조
집합 원소 수: 2
자료구조 이수: True
하위 주제: 배열, 해시, 트리
먼저 공부: 자료구조
기록 수: 10000
포함 검사 수: 200
찾은 수: 100 / 100
결과 일치: True
시간 측정: 3 회씩 완료
실측 시간과 비율: 반환값에 보관

이 결과에서 고정적으로 확인할 사실은 두 구조가 같은 답을 냈고, 각각 세 번 측정했다는 것이다. 어느 구조가 몇 배 빨랐는지는 출력만으로 판단할 수 없다. timings의 실측값을 살필 때도 입력 크기, 검사할 값의 위치, 집합 생성 비용의 포함 여부를 함께 기록해야 비교의 뜻이 유지된다.

실무에서 자주 틀리는 것

반복할 때마다 집합을 다시 만든다

아래 코드는 매번 집합을 생성한다. 검사 대상은 그대로인데 변환 비용을 계속 지불한다.

records = ["이산수학", "자료구조"]
queries = ["자료구조", "운영체제"]
hits = 0
for query in queries:
    if query in set(records):
        hits += 1
print(hits)

반복 전에 집합을 만들면 이 예에서는 같은 결과 1을 얻는다. 원본이 바뀌는 업무라면 집합도 언제 갱신할지 정해야 한다.

records = ["이산수학", "자료구조"]
queries = ["자료구조", "운영체제"]
record_set = set(records)
hits = 0
for query in queries:
    if query in record_set:
        hits += 1
print(hits)

집합으로 바꾸면서 순서와 중복을 잃는다

다음 코드는 두 번 기록한 복습을 한 번으로 줄인다. 집합은 화면에 표시할 학습 이력 자체를 대신할 수 없다.

history = ["자료구조", "운영체제", "자료구조"]
history = set(history)
print(len(history))

이력과 이수 여부를 따로 관리하면 이력은 3개를 유지하고 포함 검사 결과는 True가 된다.

history = ["자료구조", "운영체제", "자료구조"]
completed = set(history)
print(len(history))
print("자료구조" in completed)

연결을 바꾸다가 기존 다음 노드를 잃는다

다음 코드에서는 head의 연결을 먼저 덮어쓴다. middle이 자기 자신을 다음 노드로 가리키며, 이 연결을 계속 따라가면 순회가 끝나지 않는다. 출력은 True다.

tail = {"value": "자료구조", "next": None}
head = {"value": "이산수학", "next": tail}
middle = {"value": "논리", "next": None}
head["next"] = middle
middle["next"] = head["next"]
print(middle["next"] is middle)

기존 연결을 새 노드에 먼저 보관한 뒤 앞 노드를 연결한다. is는 두 값이 같은 객체를 가리키는지 검사한다. 고친 코드의 출력도 True이며, 이번에는 tail로 이어짐을 확인한다.

tail = {"value": "자료구조", "next": None}
head = {"value": "이산수학", "next": tail}
middle = {"value": "논리", "next": head["next"]}
head["next"] = middle
print(middle["next"] is tail)

작은 값이 앞에 있다는 이유로 힙이라고 생각한다

임의의 리스트에서 첫 값을 꺼내는 일은 최소값을 꺼내는 일과 다르다. 아래 출력은 3이다.

tasks = [3, 1, 2]
print(tasks.pop(0))

먼저 힙을 구성하고 힙 연산으로 꺼내면 1이 출력된다. 힙을 유지하는 도중 새 항목을 추가할 때도 일반 append 대신 heapq.heappush를 사용해야 규칙이 유지된다.

from heapq import heapify, heappop

tasks = [3, 1, 2]
heapify(tasks)
print(heappop(tasks))

한눈에 보기

학습 기록 프로그램의 요구사항과 자료구조 선택

필요한 일	후보	선택 이유	함께 확인할 점
과목을 정한 순서로 표시	리스트	위치로 읽고 순회하기 쉽다	중간 삽입은 뒤쪽 이동이 필요하다
알고 있는 노드 뒤에 항목 연결	연결 리스트	연결을 바꾸어 삽입한다	노드를 찾는 시간은 별도다
이수한 과목인지 반복 확인	집합	평균적으로 빠른 포함 검사	순서와 중복을 보존하지 않는다
과목 아래에 세부 주제 묶기	트리	부모와 자식의 계층 표현	검색 성능은 구조 규칙에 달렸다
가장 급한 학습 항목 꺼내기	최소 힙	작은 우선순위를 반복 추출	전체 정렬을 보장하지 않는다

전공 과목과의 차이를 점검할 때는 다섯 구조를 모두 직접 구현할 수 있는지보다 먼저, 위 표의 선택 이유를 자기 업무에 대입할 수 있는지 확인한다. 포함 검사는 알지만 충돌을 설명하기 어렵다면 해시를 먼저 보완한다. 삽입이 빠르다는 말은 기억하지만 위치 탐색을 빼놓는다면 연결 리스트를 다시 그려 본다. 코드가 돌아가는 것과 비용을 설명하는 것 사이의 간격을 구체적인 학습 항목으로 바꾸는 방법이다.

더 깊게 볼 서재에서는 배열과 연결 구조의 구현을 다루는 자료구조 기본서, 비용을 세는 과정을 설명하는 알고리즘 분석 입문서, Python 자료형의 동작과 메모리 사용을 다루는 언어 기본서를 고른다. 연결 리스트를 따라가며 직접 그림을 그리는 예와 해시 충돌을 추적하는 예가 있는지 목차를 확인하면 좋다. 책 이름보다 지금 설명하지 못하는 질문을 해결할 수 있는 구성이 선택 기준이다.

사실 확인이 필요할 때는 Python 내장 자료형 문서, heapq 문서, 시간 측정 함수 문서를 참고할 수 있다. 다음 장에서는 이렇게 고른 자료구조 위에서 정렬과 탐색 등의 처리 절차를 어떻게 구성하는지 살펴본다.

연습 문제

1. 완성 코드의 queries를 [0] * 200으로 바꾸기 전에 찾은 수와 시간 차이의 변화를 예상하라. 실행 후 무엇이 고정적으로 달라지고 무엇은 환경에 따라 달라지는지 구분하라.
2. 기록을 한 번만 조회하는 작업을 비교하려고 한다. 집합 생성 비용까지 포함하려면 측정 구간을 어떻게 바꾸어야 하는가. 실행 가능한 함수를 작성하라.
3. 우선순위가 같은 과목을 입력 순서대로 꺼내도록 튜플에 순번을 추가하라. 운영체제, 자료구조 순서로 입력했을 때 같은 순서로 출력되는지 확인하라.
4. 면접에서 “연결 리스트의 삽입은 O(1)이고 트리 검색은 O(log n)이다”라는 설명을 받았다. 각각 빠진 조건을 말하고, 완성 코드의 연결 리스트 삽입에서 조건이 충족되는 위치를 찾아라.

정답과 해설

1. 0은 리스트의 첫 원소이므로 긴 순회가 필요 없다. 두 구조의 찾은 수는 모두 200으로 바뀐다. 리스트와 집합의 시간 차이는 줄어들 수 있고 순서가 뒤집힐 수도 있다. 실제 시간이나 배율은 고정된 정답이 아니다. 다음 코드를 완성 코드의 함수 정의 뒤에서 실행하면 두 줄 모두 200을 출력한다.

   records = list(range(10_000))
   queries = [0] * 200
   print(count_hits(records, queries))
   print(count_hits(set(records), queries))
   

2. 집합 변환을 시작 시각과 종료 시각 사이에 넣는다. 기존 리스트가 준비되어 있다는 조건은 유지하고, 한 번의 조회를 위해 집합을 만드는 전체 비용을 측정하는 예다. 함수가 반환하는 시간은 실행마다 달라진다.

   from time import perf_counter_ns
   
   
   def compare_once(records, query):
       start = perf_counter_ns()
       list_found = query in records
       list_ns = perf_counter_ns() - start
   
       start = perf_counter_ns()
       prepared = set(records)
       set_found = query in prepared
       set_ns = perf_counter_ns() - start
   
       return list_ns, set_ns, list_found == set_found
   
   
   result = compare_once(list(range(10_000)), 10_000)
   print(result[2])
   

   출력은 True다. 한 번의 측정만으로 일반적인 성능 결론을 내리기에는 부족하지만, 어느 비용을 포함하는 실험인지 분명하게 드러낸다.

3. 튜플을 우선순위, 순번, 이름 순서로 만든다. 우선순위가 같으면 순번이 먼저 비교되므로 과목 이름의 정렬 순서가 결과에 개입하지 않는다.

   from heapq import heapify, heappop
   
   tasks = [(1, 0, "운영체제"), (1, 1, "자료구조")]
   heapify(tasks)
   while tasks:
       print(heappop(tasks)[2])
   

   출력은 운영체제 다음 자료구조다.

4. 연결 리스트는 삽입 위치의 노드를 이미 알고 있다는 조건이 필요하다. 완성 코드에서는 head를 직접 가지고 있으므로 그 뒤에 넣는 연결 변경만 하면 된다. 값으로 위치를 찾아야 한다면 탐색 비용이 추가된다.

   트리는 검색 규칙과 높이 조건이 필요하다. 균형 탐색 트리에서는 O(log n) 검색을 기대할 수 있지만 일반 계층 트리 전체에 같은 설명을 적용할 수 없다. 완성 코드의 tree는 하위 주제를 표현하며, 균형 탐색 트리의 검색 성능을 실험하는 코드가 아니다.