자료구조 선택 면접·코딩테스트 체크리스트

자료구조 질문은 암기 확인이 아닙니다

면접에서 자료구조를 묻는 이유는 해시 테이블의 내부 구현을 아는지 확인하려는 것이 아닙니다. 문제가 요구하는 연산을 정확히 뽑아내고, 그 연산의 비용을 근거로 선택할 수 있는지를 봅니다. 그래서 “해시맵을 쓰겠습니다”라고 먼저 말한 뒤 이유를 붙이는 답과, “이 문제에서 반복되는 연산은 삽입과 최솟값 제거 두 가지입니다”라고 연산을 먼저 나열한 뒤 자료구조를 고르는 답은 같은 결론에 도달해도 평가가 다릅니다.

이 페이지는 개념 목록을 다시 늘어놓는 대신 문제 하나를 끝까지 따라갑니다. 연산을 뽑는 법, 후보를 비교하는 법, 고르지 않은 쪽을 왜 버렸는지 말하는 법을 차례로 봅니다. 컬렉션 API 자체가 아직 손에 익지 않았다면 파이썬 컬렉션 가이드나 자바 컬렉션 가이드를 먼저 훑고 오는 편이 낫습니다.

연습 문제: 최근 5분 동안 가장 많이 호출된 엔드포인트 10개

서버 요청 로그가 시간순으로 들어옵니다. 각 로그는 타임스탬프와 엔드포인트 이름을 가집니다. 아무 시점에서나 “지금 기준 최근 5분 동안 호출 수가 가장 많은 엔드포인트 10개”를 물으면 답해야 합니다. 로그는 계속 들어오고, 전체 로그를 다시 읽을 수는 없습니다.

이 문제를 고른 이유는 한 가지 자료구조로 끝나지 않기 때문입니다. 시간 창을 관리하는 구조와 순위를 뽑는 구조가 따로 필요하고, 그 둘을 어떻게 연결할지가 논점이 됩니다. 실제 면접에서 나오는 문제도 대부분 이런 조합형입니다.

먼저 연산을 문장으로 적습니다

코드를 쓰기 전에 이 문제가 반복적으로 요구하는 연산을 적어 봅니다. 첫째, 새 로그를 끝에 추가합니다. 둘째, 5분보다 오래된 로그를 앞에서 제거합니다. 셋째, 엔드포인트별 현재 개수를 갱신합니다. 넷째, 개수 기준 상위 10개를 뽑습니다. 이 네 줄을 적고 나면 선택지가 저절로 좁혀집니다. 양쪽 끝에서 넣고 빼는 연산이 있으니 덱이 필요하고, 이름으로 개수를 찾아야 하니 해시가 필요하며, 상위 K개만 필요하니 전체 정렬은 과합니다.

약한 답과 강한 답

약한 답 — “로그를 리스트에 다 저장해 두고, 질의가 오면 최근 5분치를 필터링해서 엔드포인트별로 세고 정렬해서 상위 10개를 반환하겠습니다. 정렬이니까 O(n log n)입니다.”

강한 답 — “반복되는 연산이 네 가지입니다. 뒤에 추가, 앞에서 만료 제거, 이름별 카운트 갱신, 상위 10개 추출입니다. 앞뒤 삽입·삭제가 모두 O(1)이어야 하므로 창은 덱으로 관리하겠습니다. 로그가 시간순으로 들어오니 덱 앞쪽만 확인하면 만료 대상을 찾을 수 있고, 각 로그는 한 번 들어와서 한 번만 나가므로 만료 처리 전체 비용은 상환 분석으로 O(1)입니다. 카운트는 엔드포인트 이름을 키로 하는 해시맵에 두고, 추가할 때 +1, 만료할 때 −1, 0이 되면 키를 지웁니다. 상위 10개는 전체를 정렬할 필요가 없으므로 크기 10짜리 최소 힙으로 뽑겠습니다. 서로 다른 엔드포인트 수를 m이라 하면 질의 비용이 O(m log 10)이라 m이 클수록 정렬보다 유리합니다. 대신 상위 10개의 정확한 순서만 얻고 11위 이하 정보는 버린다는 점, 그리고 창 안의 모든 로그를 메모리에 들고 있어야 한다는 점이 이 선택이 지불하는 비용입니다.”

강한 답이 나은 이유는 어려운 자료구조를 써서가 아닙니다. 세 가지가 다릅니다. 첫째, 연산 목록을 먼저 말해서 이후 선택마다 근거가 붙었습니다. 둘째, 상환 분석을 언급해 “만료 루프가 while문이니 최악에 O(n) 아닌가”라는 반박을 미리 막았습니다. 셋째, 버린 것을 명시했습니다. 11위 이하를 못 본다는 사실과 메모리를 창 크기만큼 쓴다는 사실을 스스로 말하면, 면접관은 그 트레이드오프를 알고 고른 사람으로 읽습니다. 약한 답은 정렬 비용만 말했을 뿐 무엇을 포기했는지 말하지 않았고, 매 질의마다 전체를 다시 훑는다는 구조적 문제도 짚지 못했습니다.

from collections import deque, defaultdict
import heapq

WINDOW = 300  # 초

class TopEndpoints:
    def __init__(self):
        self.window = deque()              # (ts, name) 시간 오름차순
        self.count = defaultdict(int)      # name -> 창 안의 호출 수

    def add(self, ts, name):
        self.window.append((ts, name))
        self.count[name] += 1
        self._expire(ts)

    def _expire(self, now):
        # 각 로그는 정확히 한 번 들어오고 한 번 나가므로
        # 만료 처리 총비용은 상환 O(1)
        while self.window and self.window[0][0] <= now - WINDOW:
            _, old = self.window.popleft()
            self.count[old] -= 1
            if self.count[old] == 0:
                del self.count[old]

    def top(self, now, k=10):
        self._expire(now)
        # 전체 정렬 O(m log m) 대신 크기 k 힙으로 O(m log k)
        return heapq.nlargest(k, self.count.items(), key=lambda kv: kv[1])

복잡도를 다시 정리하면 이렇습니다. add는 덱 push와 해시 갱신이므로 상환 O(1)입니다. top은 서로 다른 엔드포인트 수 m에 대해 O(m log k)입니다. 공간은 창 안 로그 수에 비례합니다. 여기서 “m이 아주 크면요?”라는 질문이 자연스럽게 따라오는데, 그때는 카운트를 정확히 유지하는 대신 근사 집계로 바꾸는 이야기가 됩니다. 정확도를 얼마나 포기할 수 있는지 되물어야 하는 지점입니다.

이어지는 질문들

이 영역에서 실제로 자주 나오는 실수

첫째, 자료구조 이름부터 말하고 문제를 거기에 끼워 맞추는 경우입니다. “트라이를 쓰면 될 것 같습니다”로 시작하면 이후 대화가 그 선택을 방어하는 데 소모됩니다. 연산을 먼저 적으면 이런 일이 생기지 않습니다.

둘째, 평균 복잡도만 말하고 전제를 빼는 경우입니다. 해시는 평균 O(1)이지만 이는 해시 함수가 잘 분산된다는 가정 위에 있고, 순회 순서를 보장하지 않으며, 리사이즈가 일어나는 순간의 지연은 균등하지 않습니다. 이 전제를 스스로 말하지 않으면 면접관이 대신 물어보게 되고, 그때부터는 방어하는 대화가 됩니다.

셋째, 공간 복잡도를 통째로 빠뜨리는 경우입니다. 시간만 말하고 끝내면 “메모리는 얼마나 쓰나요”라는 질문이 반드시 옵니다. 창 안 로그 수만큼 쓴다고 먼저 말해 두는 편이 낫습니다.

넷째, 언어 표준 라이브러리의 실제 성격을 모르는 경우입니다. 리스트 앞에서 원소를 빼는 연산이 O(n)인 언어에서 큐를 리스트로 구현해 놓고 O(1)이라고 말하는 실수가 대표적입니다. 자신이 쓰는 언어의 컬렉션이 내부적으로 무엇인지는 확인해 두어야 합니다. 언어별 리스트 비교와 언어별 맵 비교가 이 확인에 도움이 됩니다.

말하기 전 확인할 것

• 반복되는 연산을 문장으로 세 개 이상 적었는가
• 연산마다 필요한 비용을 정하고 그 비용을 만족하는 후보를 골랐는가
• 고르지 않은 후보를 왜 버렸는지 한 줄로 말할 수 있는가
• 복잡도에 쓰는 문자가 무엇을 세는 값인지 정의했는가
• 평균과 최악이 다른 자료구조라면 그 차이를 먼저 말했는가
• 시간과 함께 공간 비용도 말했는가
• 쓰려는 언어의 표준 컬렉션이 그 연산을 실제로 그 비용에 하는지 확인했는가

혼자 연습하는 방법

같은 문제를 조건만 바꿔 가며 다시 답해 보는 것이 가장 빠릅니다. 창을 5분이 아니라 “최근 1000건”으로 바꾸면 무엇이 달라지는지, 상위 10개가 아니라 “호출 수 중앙값”을 물으면 어떤 자료구조가 추가로 필요한지, 엔드포인트 이름 대신 접두사별 집계를 요구하면 무엇이 바뀌는지 스스로 답해 보십시오. 조건 하나를 바꿨을 때 어떤 선택이 무너지는지 알면 그 자료구조를 이해한 것입니다.

말로 답한 뒤에는 반드시 코드로 옮겨 보시기 바랍니다. 머릿속에서는 자연스러웠던 만료 조건이 실제로는 등호 하나 때문에 어긋나는 경우가 흔합니다. 이어서 볼 주제는 문제 해결 과정 설명과 DP와 탐색이며, 언어별 기초를 다시 다지고 싶다면 심층 가이드와 파이썬 학습 라이브러리를 참고하십시오.

관련 언어 학습으로 복습하기