Ch.11 고급 자료구조

면접 실전 — Trie, Two Heaps, Intervals 코딩

Implement Trie (LeetCode 208)를 완전 구현한다Find Median from Data Stream (LeetCode 295)을 Two Heaps로 풀다Meeting Rooms II (LeetCode 253)를 Heap으로 구현한다

이론은 끝. 이제 실전 코딩입니다

오늘 배운 Trie, Two Heaps, Interval 패턴으로 면접에서 가장 빈출되는 3문제를 풀어봅니다.

알고리즘은 아는데 막상 코딩하면 막히는 이유 — 구현 디테일을 놓치기 때문

ATSO 프레임워크로 접근하고, 코드를 한 줄씩 작성하며 구현 감각을 익힙니다.

article

핵심 내용

Trie 클래스를 구현하세요. insert, search, startsWith 메서드를 포함합니다

A (접근법) • 각 노드: children 딕셔너리 + is_end 불리언 • insert: 글자마다 노드 따라감, 없으면 생성 • search: 글자마다 따라가고 is_end 확인 • startsWith: 글자마다 따라가고 존재만 확인

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, s: str):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

T (복잡도) • insert: O(m), search: O(m), startsWith: O(m) • 공간: O(N × m) — N개 단어 S (개선): _find 헬퍼로 search와 startsWith의 중복 코드 제거

_find 헬퍼 메서드로 코드를 DRY하게! 면접관이 좋아하는 패턴입니다

숫자를 하나씩 추가하며 현재까지의 중간값을 반환하세요

A (접근법): Two Heaps • max-heap(lo): 작은 절반 (부호 반전) • min-heap(hi): 큰 절반 • 규칙: len(lo) == len(hi) 또는 len(lo) == len(hi) + 1

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (부호 반전)
        self.hi = []  # min-heap

    def addNum(self, num: int) -> None:
        # 항상 lo에 먼저 넣고, lo의 최대를 hi로
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        # lo가 더 크거나 같도록 균형
        if len(self.lo) < len(self.hi):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

T: addNum O(log n), findMedian O(1) S: O(n) 공간 O: 정렬 유지 없이 O(log n)에 중간값 추적 가능!

회의 목록이 주어졌을 때 필요한 최소 회의실 수를 구하세요

A (접근법): 정렬 + Min-Heap • start 기준 정렬 • heap에 종료 시간 저장 • 새 회의 start >= heap[0] → 기존 방 재사용 • 아니면 새 방 추가

import heapq

def minMeetingRooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[0])
    heap = [intervals[0][1]]  # 첫 회의 종료 시간
    
    for i in range(1, len(intervals)):
        if intervals[i][0] >= heap[0]:
            heapq.heapreplace(heap, intervals[i][1])
        else:
            heapq.heappush(heap, intervals[i][1])
    
    return len(heap)

T: O(n log n) — 정렬 + heap 연산 S: O(n) — 최악 모든 회의가 겹침 O: heapreplace = pop + push를 한 번에!

0,30],[5,10],[15,20],[10,25를 추적합니다

[5,10] 회의실을 [10,25]가 이어받고, [0,30]과 [15,20]은 별도 회의실. 총 3개!

오늘 배운 3문제의 면접 포인트를 정리합니다

세 문제 모두 FAANG 빈출! 구현 코드를 외우지 말고 패턴을 이해하세요

Trie 구현에서 _find 헬퍼를 만드는 이유는?

Python에서 max-heap을 구현하는 방법은?

heapreplace(heap, val)은 어떤 두 연산을 합친 것인가?

heapreplace = heappop + heap___

key

핵심 용어

✅

Trie

_find 헬퍼로 DRY. is_end와 경로 존재의 차이 설명

✅

Two Heaps

부호 반전 트릭. 크기 균형 유지 로직 설명

✅

Meeting Rooms

heapreplace 사용. 정렬 기준(start) 명확히

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작