자료구조 질문 - 배열·리스트·해시·트리·힙

이 장에서 배우는 것

앞 장에서 프로젝트의 선택과 어려움을 설명했다면, 이제 그 선택을 자료구조의 성질로 뒷받침해야 한다. 중고 거래 서비스에서 상품을 순서대로 보여 주는 일, 상품 번호로 정보를 찾는 일, 처리할 신고를 우선순위에 따라 꺼내는 일은 서로 다른 요구다. 면접관은 자료구조 이름을 몇 개 기억하는지보다, 요구를 연산으로 바꾸고 비용과 한계를 설명할 수 있는지를 확인한다.

이 장에서는 먼저 필요한 연산을 정하고, 그 연산에 맞는 자료구조를 고르는 방식으로 답한다. 마지막에는 체이닝 해시 테이블을 직접 만들어 같은 버킷 수에서 항목이 늘어날 때 충돌과 탐색 횟수가 어떻게 달라지는지 확인한다.

• 배열과 연결 리스트를 접근·탐색·삽입·삭제 비용으로 비교한다.
• 해시 테이블의 충돌 처리와 적재율을 실제 비교 횟수로 설명한다.
• 이진 탐색 트리와 균형 트리, 힙의 서로 다른 순서 보장을 구분한다.
• 스택과 큐의 활용 예를 들고 Python의 적절한 도구를 선택한다.
• 결론, 근거, 경험이나 예시, 한계와 대안 순서로 답하고 꼬리 질문에 대응한다.

문제 상황

가상의 중고 거래 서비스 팀에 지원한 지원자가 프로젝트에서 상품 목록과 신고 처리 기능을 만들었다고 설명했다. 면접관은 “상품 목록은 왜 리스트에 저장했나”라고 묻는다. 지원자는 “추가와 삭제가 편해서 사용했다”라고 답한다. 면접관이 “맨 앞의 상품을 삭제해도 같은 비용인가”라고 되묻자 답이 막힌다.

문제는 Python 문법을 모르는 데 있지 않다. 리스트라는 이름만으로 연결 리스트의 특성을 떠올렸고, 어디에서 무엇을 삭제하는지 구체화하지 않았기 때문이다. Python의 list는 동적 배열이다. 배열 끝에 추가하는 일과 배열 앞에서 삭제하는 일은 비용이 다르다.

서비스 요구를 더 나누면 선택 기준이 보인다. 화면에 상품을 순서대로 표시하려면 순회가 필요하다. 상품 번호로 상세 정보를 찾으려면 키 탐색이 필요하다. 신고를 접수 순서대로 처리하려면 큐가, 긴급도 순서대로 처리하려면 우선순위 큐가 필요하다. 한 자료구조가 이 요구를 모두 같은 비용으로 처리하지는 않는다.

면접 질문과 평가 의도

질문	의도	답변 핵심	꼬리 질문
배열과 연결 리스트는 어떻게 다른가	저장 방식과 연산 비용 연결	배열은 인덱스 접근, 연결 리스트는 위치를 아는 노드 주변의 변경에 유리하다	삭제할 노드를 찾는 비용은 얼마인가
Python list의 끝 추가는 왜 상수 시간이라고 하는가	분할 상환 비용 이해	대부분은 빈 공간에 쓰지만 확장 시 복사가 발생할 수 있다	한 번의 추가도 항상 상수 시간인가
해시 테이블은 키를 어떻게 찾는가	해시와 동등성 구분	해시로 후보 위치를 정하고 키를 비교한다	다른 키의 해시가 같으면 어떻게 하는가
해시 충돌은 어떻게 처리하는가	구현 대안 이해	체이닝은 버킷에 여러 항목을, 개방 주소법은 다른 슬롯에 항목을 둔다	삭제 처리는 어떻게 다른가
적재율이 커지면 어떤 일이 생기는가	평균 비용의 조건 이해	체인이 길어지거나 빈 슬롯 탐색이 늘어난다	버킷 수를 늘리기만 하면 되는가
이진 트리와 이진 탐색 트리는 같은가	구조와 순서 규칙 구분	자식 수 제한과 키의 순서 규칙은 별개다	중복 키는 어디에 두는가
균형 트리는 왜 필요한가	높이와 탐색 비용 연결	편향을 제한해 탐색 경로를 짧게 유지한다	균형 유지에는 비용이 없는가
힙과 정렬된 배열은 어떻게 다른가	부분 순서 이해	힙은 부모와 자식의 관계를 보장하며 전체 정렬은 아니다	중간 순위 항목도 바로 찾을 수 있는가
스택과 큐는 어디에 쓰는가	처리 순서와 구현 연결	되돌리기에는 스택, 접수 순서 처리에는 큐를 적용한다	list의 앞에서 꺼내면 왜 느린가
시간 복잡도만 같으면 성능도 같은가	분석 범위와 현실적 판단	메모리 배치, 상수 비용, 입력 크기도 영향을 준다	어떤 조건으로 측정하겠는가

연산의 위치까지 말해야 자료구조 비교가 된다

배열과 연결 리스트의 차이

배열(array)은 원소를 연속된 공간에 배치해 인덱스로 위치를 계산한다. 고정 크기 배열은 용량이 정해져 있고, 동적 배열은 공간이 부족할 때 더 큰 저장 공간을 확보한다. Python list는 객체 자체를 모두 연속 배치하는 방식이 아니라 객체를 가리키는 참조들을 배열 형태로 관리한다. 따라서 참조의 배치와 각 객체의 배치를 구분해야 한다.

연결 리스트(linked list)는 노드에 값과 다음 노드로 가는 연결 정보를 둔다. 단일 연결 리스트는 다음 방향을, 이중 연결 리스트는 이전과 다음 방향을 연결한다. 논리적으로 이웃한 노드가 메모리에서도 이웃할 필요는 없다. 인덱스로 특정 위치를 찾으려면 연결을 따라가야 한다.

“연결 리스트의 삭제는 O(1)이다”라고만 답하면 조건이 빠진다. 단일 연결 리스트에서 일반적인 노드 삭제는 이전 노드의 연결을 바꿔야 하므로 이전 노드 정보가 필요하다. 값으로 삭제 대상을 찾는 과정은 O(n)일 수 있다. 이중 연결 리스트도 대상 노드를 이미 알고 있는지부터 확인해야 한다.

배열의 중간 삽입과 삭제는 뒤쪽 원소를 이동시키므로 O(n)이다. 다만 끝에서 삭제하는 일까지 같은 비용이라고 묶어 말해서는 안 된다. 동적 배열의 끝 추가는 공간 확장 비용을 여러 연산에 나누어 보는 분할 상환 분석에서 O(1)이다. 확장이 발생하는 한 번의 연산은 O(n)이 될 수 있다.

같은 배열·연결 리스트 질문에 대한 답변의 차이

수준	답변	빠진 조건 또는 강점
나쁜 답	배열은 빠르고 연결 리스트는 삽입과 삭제가 빠르다.	어떤 연산인지, 위치를 알고 있는지 설명하지 않는다.
보통 답	배열의 인덱스 접근은 O(1), 연결 리스트의 접근은 O(n)이다. 배열 중간 삽입은 O(n)이다.	비용은 설명하지만 실제 선택과 연결하지 않는다.
좋은 답	상품 목록은 순회와 인덱스 접근이 많아 동적 배열을 선택하겠다. 중간 삭제가 잦다면 이동 비용을 확인하겠다. 연결 리스트는 노드 위치를 이미 알고 변경할 때 유리하지만, 대상을 찾는 비용과 연결 정보의 공간도 고려하겠다.	요구, 비용, 예시, 한계를 연결한다.

면접관: 상품 목록에 연결 리스트를 쓰면 삭제가 더 빠르지 않은가.

지원자: 상품 번호로 대상을 먼저 찾아야 한다면 연결 리스트만으로는 탐색이 O(n)이다. 제 예시에서는 목록 순회가 주된 작업이어서 동적 배열을 선택하겠다. 삭제가 병목으로 확인되고 노드 위치를 별도로 관리할 수 있다면 연결 리스트와 탐색용 구조의 조합도 검토하겠다. 다만 구조를 두 개 유지하는 비용이 추가된다.

면접관 반응: 삭제 연산 하나의 비용과 삭제 위치를 찾는 비용을 나누어 설명했다. 이제 실제 작업 비율을 물을 수 있다.

스택과 큐는 처리 순서의 약속이다

스택(stack)은 나중에 넣은 항목을 먼저 꺼낸다. 상품 설명 편집에서 최근 변경을 되돌리는 기록을 떠올릴 수 있다. 큐(queue)는 먼저 넣은 항목을 먼저 꺼낸다. 접수 순서대로 처리하는 작업 대기가 예다. 둘은 처리 규칙을 나타내며, 구현에는 배열이나 연결 구조 등을 사용할 수 있다.

Python에서는 list의 append와 끝 pop으로 스택을 만들 수 있다. 양 끝에서 넣고 빼는 큐에는 collections.deque가 적합하다. list.pop(0)은 뒤의 참조들을 앞으로 이동시키므로 O(n)이다. deque의 양 끝 추가와 제거는 O(1)이지만, 가운데 인덱스 접근까지 배열처럼 O(1)인 것은 아니다.

면접에서는 “큐를 쓴다”에서 멈추지 않는다. 접수 순서가 요구인지, 긴급도가 요구인지 확인한다. 긴급 신고를 먼저 처리해야 한다면 일반 큐보다 우선순위 큐가 맞을 수 있다. 자료구조 선택은 이름보다 처리 순서에서 시작한다.

해시 테이블의 평균 비용에는 조건이 붙는다

해시 테이블(hash table)은 키의 해시 값을 이용해 저장 위치의 후보를 정한다. 이 장의 구현은 정수 키를 버킷 수로 나눈 나머지를 사용한다. 서로 다른 키가 같은 버킷으로 갈 수 있는데 이를 충돌이라 한다. 해시 값이나 버킷 번호가 같다는 사실은 키가 같다는 뜻이 아니므로 마지막에는 키의 동등성을 확인해야 한다.

체이닝(chaining)은 각 버킷에 여러 항목을 보관한다. 개방 주소법(open addressing)은 테이블 내부에서 정해진 탐사 규칙으로 다른 슬롯을 찾는다. 체이닝에서는 해당 체인에서 항목을 지울 수 있지만, 개방 주소법에서는 탐사 경로를 끊지 않도록 삭제 표식 같은 처리가 필요할 수 있다. 이 장의 실험은 체이닝만 구현한다.

적재율(load factor)은 저장된 항목 수 n을 버킷 수 m으로 나눈 α = n/m이다. 체이닝에서는 한 버킷에 여러 항목을 저장하므로 적재율이 1을 넘을 수 있다. 키가 버킷에 고르게 분산된다는 가정 아래 탐색의 기대 비용은 O(1 + α)로 설명할 수 있다. 적재율을 일정한 범위로 유지하면 기대 O(1)이지만, 모든 키가 한 버킷에 모이면 최악 탐색은 O(n)이다.

모범 답안: 해시 테이블은 왜 빠른가

지원자: 상품 번호로 정보를 찾는 작업에는 해시 테이블이 적합하다. 해시로 후보 버킷을 좁히고 그 안에서만 키를 비교하기 때문이다. 예를 들어 상품 번호를 키로 저장하면 전체 상품 목록을 매번 순회하는 일을 줄일 수 있다. 다만 기대 상수 시간은 키 분산과 적재율 관리에 의존한다. 충돌이 몰리면 선형 탐색이 될 수 있고, 가격순 범위 조회처럼 순서가 필요한 작업에는 별도의 정렬 구조가 필요하다.

나쁜 답은 “해시는 O(1)이므로 가장 빠르다”이다. 보통 답은 “충돌 때문에 최악에는 O(n)이다”까지 말한다. 좋은 답은 어떤 조건에서 기대 O(1)인지 밝히고, 상품 번호 탐색이라는 요구에 연결한 뒤 순서 조회에는 다른 선택이 필요하다고 설명한다.

면접관: 버킷 수를 두 배로 늘리면 충돌이 없어지는가.

지원자: 평균 체인 길이를 줄일 가능성은 있지만 충돌 제거를 보장하지는 않는다. 키 분포와 해시 함수에 따라 특정 버킷에 계속 몰릴 수 있다. 버킷 수가 바뀌면 기존 항목도 새 버킷으로 재배치해야 하므로 그 작업은 O(n)이고 추가 공간도 필요하다.

면접관 반응: 확장의 효과와 비용을 함께 설명했다. 충돌이 많은 입력을 어떻게 만들고 확인할지도 물을 수 있다.

실무에서는 일반적으로 직접 만든 해시 테이블 대신 dict를 사용한다. 여기서는 동작을 관찰하려고 단순한 구현을 만든다. Python 문자열 해시의 실행별 차이를 실험에 끌어들이지 않도록 정수 키와 명시적인 나머지 연산만 사용한다. 키 해시를 계산하는 비용까지 언제나 상수라고 가정할 수 있는 것은 아니지만, 이 실험은 작은 정수 키의 비교 횟수에 집중한다.

트리의 순서와 힙의 순서는 다르다

트리(tree)는 부모와 자식 관계로 계층을 표현한다. 이진 트리는 한 노드의 자식이 최대 둘인 트리다. 이진 탐색 트리(binary search tree)는 여기에 순서 규칙을 더한다. 중복이 없는 경우 각 노드의 왼쪽 서브트리에는 더 작은 키를, 오른쪽 서브트리에는 더 큰 키를 둔다. 중복 키를 허용한다면 개수를 노드에 저장하는 등의 정책을 별도로 정해야 한다.

이진 탐색 트리의 탐색 비용은 높이 h에 따라 O(h)다. 오름차순 키를 단순 삽입하면 한쪽으로 긴 모양이 되어 높이가 O(n)이 될 수 있다. 균형 트리는 삽입과 삭제 뒤에도 정해진 균형 조건을 유지해 높이를 O(log n)으로 제한한다. 대표적인 방식은 AVL 트리와 레드 블랙 트리다.

모범 답안: 이진 탐색 트리는 항상 빠른가

지원자: 일반 이진 탐색 트리가 항상 O(log n) 탐색을 보장하지는 않는다. 탐색 비용은 높이에 비례하고, 정렬된 상품 번호를 차례로 삽입하면 높이가 n에 가까워질 수 있기 때문이다. 키 순서에 따른 조회가 필요하다면 균형을 유지하는 탐색 트리를 검토하겠다. 다만 균형 조건을 유지하는 회전과 정보 갱신이 추가되며, 순서가 필요 없는 단일 키 조회라면 해시 테이블도 비교하겠다.

나쁜 답은 “트리는 탐색이 O(log n)이다”이다. 보통 답은 “균형이 잡혀 있어야 한다”라고 조건을 붙인다. 좋은 답은 비용을 높이로 먼저 설명하고, 편향되는 입력과 균형 유지 비용까지 연결한다.

면접관: 균형 트리에서 가격 범위를 찾는 비용은 얼마인가.

지원자: 가격과 상품 번호를 함께 키로 정하고 하한을 찾은 뒤 순서대로 방문할 수 있다면, 결과가 k개일 때 O(log n + k)로 설명할 수 있다. 결과를 실제로 꺼내는 비용은 제외할 수 없다. 같은 가격의 상품을 구분하는 정책도 필요하다.

힙(heap)은 탐색 트리와 다른 순서를 보장한다. 최소 힙에서는 부모가 자식보다 작거나 같다. 루트에는 최솟값이 있지만, 형제 사이와 서로 다른 가지 전체의 정렬은 보장하지 않는다. 이진 힙은 마지막 층을 왼쪽부터 채우는 형태여서 배열로 표현하기 좋다. 인덱스 i의 자식은 2i+1과 2i+2에 놓인다.

우선순위 큐(priority queue)는 우선순위가 높은 항목부터 꺼내는 동작을 제공한다. 힙은 이를 구현하는 한 방법이다. Python의 heapq는 최소 힙을 다루므로 숫자가 작을수록 먼저 처리되도록 우선순위를 정할 수 있다. 최솟값 확인은 O(1), 삽입과 최솟값 제거는 O(log n), 기존 항목 전체로 힙을 만드는 heapify는 O(n)이다.

모범 답안: 신고 처리를 위해 왜 힙을 쓰는가

지원자: 신고 중 가장 긴급한 하나를 반복해서 꺼내고 새 신고도 계속 들어온다면 힙을 선택하겠다. 매번 전체를 정렬하지 않고 삽입과 우선 항목 제거를 O(log n)에 처리할 수 있기 때문이다. 예를 들어 긴급도와 접수 순번을 함께 저장하면 같은 긴급도에서는 먼저 접수된 신고를 꺼낼 수 있다. 다만 임의의 신고를 찾거나 우선순위를 바꾸는 기능은 단순 힙만으로 빠르게 처리하기 어렵다. 위치를 관리하는 보조 구조나 이전 항목을 무효화하는 방식이 필요하다.

나쁜 답은 “힙은 정렬되어 있어서 빠르다”이다. 보통 답은 삽입과 제거 비용을 설명한다. 좋은 답은 반복해서 필요한 연산을 짚고, 동률 처리와 우선순위 변경의 한계까지 말한다. 이미 고정된 모든 신고를 한 번에 순서대로 출력하는 요구라면 전체 정렬도 자연스러운 대안이다.

완성 코드

다음 내용을 main.py로 저장한다. 버킷 수는 8개로 고정하고 항목 수를 4, 8, 16, 24개로 늘린다. 키는 0부터 차례로 삽입한다. 난수와 시각을 사용하지 않으므로 실행할 때마다 같은 결과가 나온다. 자동 확장과 삭제는 구현하지 않아 적재율 변화만 관찰할 수 있게 했다.

이 실험에서 충돌 수는 “새 키를 비어 있지 않은 버킷에 삽입한 횟수”다. 같은 키를 갱신한 일은 세지 않는다. 탐색 횟수는 버킷 안에서 키를 비교한 횟수이며, 해시 계산과 버킷 접근은 포함하지 않는다. 빈 버킷에서 실패하면 비교 횟수는 0이다.

class ChainingHashTable:
    def __init__(self, bucket_count):
        if bucket_count <= 0:
            raise ValueError("bucket_count must be positive")
        self.buckets = [[] for _ in range(bucket_count)]
        self.size = 0
        self.collisions = 0

    def _bucket(self, key):
        return self.buckets[key % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for index, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[index] = (key, value)
                return
        if bucket:
            self.collisions += 1
        bucket.append((key, value))
        self.size += 1

    def find(self, key):
        comparisons = 0
        for stored_key, value in self._bucket(key):
            comparisons += 1
            if stored_key == key:
                return True, value, comparisons
        return False, None, comparisons


def run_case(item_count, bucket_count=8):
    table = ChainingHashTable(bucket_count)
    for key in range(item_count):
        table.put(key, f"item-{key}")

    success_total = 0
    for key in range(item_count):
        found, value, comparisons = table.find(key)
        if not found or value != f"item-{key}":
            raise RuntimeError("successful lookup failed")
        success_total += comparisons

    failure_total = 0
    for key in range(1000, 1000 + bucket_count):
        found, _, comparisons = table.find(key)
        if found:
            raise RuntimeError("missing key was found")
        failure_total += comparisons

    load = table.size / bucket_count
    longest = max(len(bucket) for bucket in table.buckets)
    success_average = success_total / item_count
    failure_average = failure_total / bucket_count
    return (
        table.size,
        load,
        table.collisions,
        longest,
        success_average,
        failure_average,
    )


def main():
    print("buckets=8; key comparison counts")
    print("n | load | collisions | max_chain | hit_avg | miss_avg")
    for item_count in (4, 8, 16, 24):
        n, load, collisions, longest, hit, miss = run_case(item_count)
        print(
            f"{n} | {load:.2f} | {collisions} | {longest}"
            f" | {hit:.2f} | {miss:.2f}"
        )


if __name__ == "__main__":
    main()

줄별 해설

빈 줄을 포함해 첫 class 줄을 1행으로 센다. 1~7행은 테이블의 상태를 만든다. 버킷 수가 0 이하이면 나머지 연산과 적재율 계산이 성립하지 않으므로 예외를 발생시킨다. 각 버킷은 독립적인 리스트이며 size는 서로 다른 키의 수, collisions는 실험에서 정의한 충돌 횟수다.

9~10행의 _bucket은 정수 키를 버킷 번호로 바꾼다. 키 0과 8은 모두 0번 버킷으로 간다. 이는 Python dict의 내부 구현을 재현하려는 코드가 아니다. 충돌 위치를 손으로 계산할 수 있는 작은 모델이다.

12~21행의 put은 먼저 해당 버킷에서 같은 키를 찾는다. 이미 있으면 값을 바꾸고 반환하므로 항목 수와 충돌 수가 늘지 않는다. 새 키이고 버킷에 기존 항목이 있으면 충돌 수를 하나 늘린다. 이어서 체인 끝에 항목을 추가한다. 이 구현의 체인은 Python list이므로 교과서의 연결 노드 대신 튜플을 담은 동적 배열을 사용한다.

23~29행의 find는 키를 하나 비교할 때마다 comparisons를 늘린다. 찾으면 성공 여부, 값, 비교 횟수를 반환하고, 끝까지 없으면 실패를 반환한다. 값을 None으로 저장한 경우와 키가 없는 경우를 구별하도록 성공 여부를 별도로 둔다.

32~35행은 실험마다 새 테이블을 만들고 연속된 정수 키를 삽입한다. 이전 실험의 상태를 재사용하지 않으므로 각 행은 독립적이다. 현재 키들은 버킷에 고르게 분산되므로 적재율의 효과를 보기 쉽다.

37~42행은 존재하는 모든 키를 정확히 한 번씩 찾는다. 따라서 성공 평균은 모든 저장 키를 같은 빈도로 조회한다는 조건의 평균이다. 실무의 인기 상품 편중까지 표현하는 수치는 아니다. 값 검증을 함께 하므로 잘못된 항목을 반환하면서 비교 횟수만 그럴듯하게 출력하는 경우도 잡는다.

44~49행은 없는 키 1000부터 1007까지를 찾는다. 이 키들은 8개 버킷을 한 번씩 방문한다. 따라서 실패 평균은 모든 버킷을 같은 빈도로 조회한 결과다. 현재 실험의 저장 키와는 겹치지 않는다.

51~62행은 적재율, 가장 긴 체인, 두 탐색 평균을 계산한다. 65~78행은 고정된 네 조건을 실행하고 소수 둘째 자리까지 표를 출력한다. 실행 시간 대신 비교 횟수를 사용하므로 장비 상태에 따른 출력 차이가 없다.

실행 결과

macOS와 Linux에서 Python 3.12 이상으로 다음 명령을 실행한다.

python3 main.py

예상 출력은 다음과 같다.

buckets=8; key comparison counts
n | load | collisions | max_chain | hit_avg | miss_avg
4 | 0.50 | 0 | 1 | 1.00 | 0.50
8 | 1.00 | 0 | 1 | 1.00 | 1.00
16 | 2.00 | 8 | 2 | 1.50 | 2.00
24 | 3.00 | 16 | 3 | 2.00 | 3.00

항목이 16개이면 각 버킷의 체인 길이는 2다. 각 체인에서 먼저 들어온 키는 한 번, 나중에 들어온 키는 두 번 비교하므로 성공 평균은 (1+2)/2인 1.50이다. 없는 키는 체인의 두 항목을 모두 확인하므로 실패 평균이 2.00이다.

항목이 4개인 조건에서 실패 평균이 0.50인 이유는 절반의 버킷이 비어 있기 때문이다. 전체 조회 비용이 반 번이라는 뜻은 아니다. 버킷 계산과 접근을 제외하고 키 비교만 세었기 때문에 가능한 값이다.

이 결과를 근거로 “적재율 1까지는 충돌이 없다”라고 일반화하면 안 된다. 연속 정수와 나머지 연산의 조합이 고르게 분산되었을 뿐이다. 같은 수의 키라도 8의 배수만 넣으면 한 버킷에 몰린다. 면접에서 수치를 말할 때에는 입력 분포와 측정 단위를 함께 밝혀야 한다.

실무에서 자주 틀리는 것

버킷 리스트를 곱셈으로 복제한다

다음 코드는 서로 다른 빈 리스트 8개를 만드는 것이 아니다. 같은 리스트를 가리키는 참조를 8번 저장한다. 한 버킷에 추가한 항목이 다른 버킷에서도 보인다.

buckets = [[]] * 8
buckets[0].append((0, "item-0"))

각 버킷을 별도로 생성해야 한다.

buckets = [[] for _ in range(8)]
buckets[0].append((0, "item-0"))

표면적으로는 해시 함수가 잘못된 것처럼 보일 수 있지만 원인은 변경 가능한 객체의 공유다. 빈 상태만 확인하면 발견하기 어려우므로 한 버킷만 변경했을 때 다른 버킷이 유지되는지 확인해야 한다.

큐를 list의 맨 앞 삭제로 구현한다

작업을 순서대로 꺼내는 다음 코드는 동작하지만, 매번 남은 참조를 앞으로 이동시킨다. 처음부터 n개를 모두 꺼내면 이동 비용의 합이 O(n²)이 된다.

pending = list(range(100))
while pending:
    item = pending.pop(0)

양 끝 연산을 제공하는 deque를 사용하면 전체 제거 비용을 O(n)으로 설명할 수 있다.

from collections import deque

pending = deque(range(100))
while pending:
    item = pending.popleft()

항목 수가 적을 때의 실행 시간만 보고 구조의 성질을 단정하지 않는다. 요구가 인덱스 접근인지 양 끝 제거인지 먼저 구분한다.

힙의 내부 배열을 정렬 결과로 사용한다

heapify 뒤의 배열을 그대로 표시하면 모든 항목이 우선순위순이라고 보장할 수 없다.

import heapq

priorities = [7, 2, 5, 1, 9, 3]
heapq.heapify(priorities)
ordered = priorities[:]

우선순위순으로 꺼내려면 힙에서 반복 제거한다. 원본을 유지해야 한다면 복사본에서 제거한다.

import heapq

priorities = [7, 2, 5, 1, 9, 3]
heapq.heapify(priorities)
work = priorities[:]
ordered = [heapq.heappop(work) for _ in range(len(work))]

모든 항목을 한 번에 정렬한 목록만 필요하면 sorted가 더 직접적이다. 힙의 장점은 삽입이 섞이는 상황에서 우선 항목을 계속 꺼낼 때 설명하기 쉽다.

변경 가능한 내용을 해시 키로 삼는다

일반적인 list는 변경 가능하므로 dict의 키로 사용할 수 없다. 다음 코드는 실행 시 TypeError를 발생시킨다.

product_key = [12, 34]
products = {product_key: "item"}

구성 요소가 정수처럼 해시 가능한 값이라면 튜플로 표현할 수 있다.

product_key = (12, 34)
products = {product_key: "item"}

튜플이라는 이름만으로 모든 값이 키가 되는 것은 아니다. 내부에 리스트가 있으면 그 튜플도 해시할 수 없다. 사용자 정의 객체는 동등성 비교와 해시가 일관되어야 하며, 키로 사용하는 동안 그 판단에 쓰이는 상태가 바뀌지 않도록 설계해야 한다.

한눈에 보기

자료구조를 고를 때 말해야 하는 연산과 조건

자료구조	주요 비용	중고 거래 서비스 예시	답변에 붙일 조건
동적 배열	인덱스 접근 O(1), 중간 삽입·삭제 O(n)	상품 목록 순회	끝 추가는 분할 상환 O(1)이다
연결 리스트	위치 탐색 O(n), 연결 변경 O(1)	노드를 이미 아는 순서 목록 변경	필요한 대상·이전 노드 정보를 알고 있어야 한다
체이닝 해시 테이블	기대 탐색 O(1+α), 최악 O(n)	상품 번호로 조회	키 분산과 적재율, 키 처리 비용을 확인한다
일반 이진 탐색 트리	탐색 O(h), 최악 O(n)	정렬된 키 탐색	높이가 작다는 보장이 없다
균형 탐색 트리	탐색·삽입·삭제 O(log n)	가격순 탐색과 범위 순회	균형 유지 비용과 결과 개수를 고려한다
이진 최소 힙	최솟값 확인 O(1), 삽입·제거 O(log n)	긴급 신고 우선 처리	임의 키 탐색과 전체 정렬은 보장하지 않는다
list로 만든 스택	끝 추가 분할 상환 O(1), 끝 제거 O(1)	최근 편집 되돌리기	어느 끝을 사용하는지 밝힌다
deque로 만든 큐	양 끝 추가·제거 O(1)	접수 순서 작업 처리	가운데 인덱스 접근은 별도로 판단한다

시간 복잡도는 입력이 커질 때 비용이 어떻게 증가하는지 설명한다. 같은 O(n)이라도 배열의 연속된 참조 순회와 연결 리스트의 노드 순회는 실제 시간이 다를 수 있다. 메모리 사용량, 할당 비용, 접근 지역성도 영향을 준다. 면접에서는 먼저 연산과 복잡도를 설명하고, 실제 성능 판단에는 대표 입력과 작업 비율을 정한 측정이 필요하다고 덧붙인다.

연습 문제

1. 완성 코드의 항목 수가 24개일 때 성공 탐색 비교 횟수의 총합을 계산하라. 실패 평균이 성공 평균보다 큰 이유도 설명하라.
2. 삽입 키를 0, 8, 16, 24로 바꾸고 버킷 수는 8개로 유지한다고 가정하라. 충돌 수, 최대 체인 길이, 모든 저장 키를 한 번씩 찾는 성공 평균을 구하라. 없는 키 1000부터 1007까지의 실패 평균도 구하라.
3. 완성 코드에서 새 테이블을 만들고 put(3, "old"), put(3, "new")를 차례로 호출한다. size, collisions, find(3)의 반환값을 예측하라. 키 갱신을 새 삽입과 구분해야 하는 이유를 설명하라.
4. 면접관이 “급한 신고부터 처리하고, 긴급도가 같으면 먼저 접수한 신고를 처리하라”라고 요구했다. 적합한 자료구조와 저장 항목을 제안하라. 처리 대기 중인 신고의 긴급도가 바뀌면 생기는 문제까지 답하라.

정답과 해설

1. 각 버킷에는 세 항목이 있고 비교 횟수는 1, 2, 3이다. 버킷 하나의 합은 6이며 버킷 8개의 총합은 48이다. 성공 평균은 48/24인 2.00이다. 실패 조회는 해당 체인을 끝까지 확인하므로 평균 3.00이다. 성공 조회는 키를 발견한 시점에서 멈춘다.
2. 네 키는 모두 0번 버킷에 들어간다. 첫 삽입 이후 세 번이 충돌이므로 충돌 수는 3, 최대 체인 길이는 4다. 성공 평균은 (1+2+3+4)/4인 2.50이다. 실패 키 여덟 개 중 1000만 0번 버킷으로 가서 네 번 비교하고 나머지는 빈 버킷을 방문한다. 실패 평균은 4/8인 0.50이다. 같은 적재율에서도 성공 비용과 최대 체인 길이는 달라질 수 있으며, 버킷 전체를 고르게 조회하는 실패 평균만으로 쏠림을 판단해서는 안 된다.
3. size는 1이고 collisions는 0이다. find(3)은 (True, "new", 1)을 반환한다. 두 번째 put은 기존 항목을 찾아 값만 바꾼다. 갱신 때 size를 늘리면 실제 키 수보다 적재율이 커지고, 불필요한 확장 판단이나 잘못된 통계로 이어진다.
4. 최소 힙으로 우선순위 큐를 만들고, 숫자가 작을수록 급하도록 정한 긴급도, 증가하는 접수 순번, 신고 번호를 함께 저장할 수 있다. 접수 순번은 동률 처리 기준이며 서로 다른 신고가 뒤쪽 값의 비교에 의존하지 않도록 한다. 힙 안의 항목을 임의로 수정하면 힙 조건이 깨질 수 있다. 이전 항목을 무효화하고 새 항목을 넣거나 위치를 추적해 재조정하는 방식을 검토한다. 무효 항목을 남기는 방식은 추가 메모리와 정리 비용을 함께 설명해야 한다.

자료구조 답변은 “무엇이 빠르다”보다 “어떤 입력에서 어떤 연산을 어느 비용으로 처리한다”에 가까워야 한다. 다음 장에서는 이 기준을 바탕으로 문제를 풀면서 선택과 검증 과정을 말하는 연습을 이어 간다.