자료구조 선택과 복잡도 면접 준비

“무엇을 쓰시겠습니까”는 사실 접근 패턴을 묻는 질문입니다

자료구조를 고르라는 질문에 지원자가 가장 많이 하는 실수는 자료구조부터 말하는 것입니다. “해시 맵을 쓰겠습니다”라고 답하면 면접관은 바로 “왜요”라고 묻고, 그때 나오는 답이 “빠르니까요”면 대화가 거기서 끝납니다.

이 질문의 실제 구조는 이렇습니다. 면접관은 데이터에 어떤 연산이 얼마나 자주 일어나는지를 묻고 싶은데, 그것을 자료구조 이름으로 포장해서 물은 것입니다. 그래서 좋은 답은 자료구조가 아니라 연산의 목록에서 시작합니다. 무엇을 넣고, 무엇으로 찾고, 순서가 필요한지, 데이터가 얼마나 커지는지, 읽기와 쓰기 비율이 어떤지를 먼저 세운 다음 그 목록을 만족하는 것을 고르면 됩니다.

연산 목록을 세울 때 반드시 확인할 축은 다섯 가지입니다. 조회 키가 무엇인가, 순서 보장이 필요한가, 삽입과 삭제가 어디에서 일어나는가, 전체 순회가 얼마나 잦은가, 규모가 어디까지 커지는가. 이 다섯 가지에 답하고 나면 선택지는 대개 하나나 둘로 줄어듭니다. 그리고 그 축을 소리 내어 말하는 과정 자체가 점수입니다.

네 가지 기본형을 접근 패턴으로 세우기

동적 배열은 원소가 메모리에 연속으로 놓입니다. 인덱스로 접근하는 것이 상수 시간이고, 끝에 추가하는 것도 상환 상수 시간입니다. 반면 중간에 삽입하거나 삭제하면 뒤쪽을 전부 밀어야 하므로 선형입니다. 값으로 찾으려면 전체를 훑어야 하니 이것도 선형입니다. 순서를 유지하면서 끝에서 자라고, 주로 인덱스로 접근하거나 통째로 순회하는 데이터에 맞습니다.

연결 리스트는 각 원소가 다음 원소의 위치를 들고 있습니다. 노드를 이미 손에 쥐고 있다면 그 자리에서 삽입과 삭제가 상수 시간입니다. 그러나 n번째 원소를 찾으려면 처음부터 따라가야 하므로 인덱스 접근이 선형입니다. 여기서 오해가 자주 생깁니다. “중간 삽입이 O(1)이니까 삽입이 잦으면 연결 리스트”라는 말은 자리를 찾는 비용을 빼고 세는 것입니다. 자리를 찾아야 한다면 총비용은 선형이고, 그러면 배열과 다를 것이 없습니다. 실무에서 연결 리스트가 진짜로 유리한 경우는 노드 참조를 다른 자료구조가 이미 들고 있는 구조, 예를 들어 최근 사용 캐시에서 항목을 맨 앞으로 옮기는 연산 같은 곳입니다.

해시 맵은 키를 해시 함수로 정수로 바꾸고 그 값으로 저장 위치를 정합니다. 삽입, 조회, 삭제가 모두 평균 상수 시간입니다. 대신 순서가 없고, 키 범위로 훑는 질의를 지원하지 않으며, 최악의 경우가 선형이라는 조건이 붙습니다. 키가 무엇인지 명확하고 그 키로만 찾으면 되는 경우의 기본 선택지입니다.

트리 맵은 키를 정렬 상태로 유지합니다. 조회와 삽입이 로그 시간으로 해시보다 느리지만, 정렬 순회와 범위 질의를 제공합니다. “A 이상 B 미만인 키를 순서대로 주세요”가 필요하면 해시로는 전체를 훑어야 하고 트리로는 바로 됩니다. 상한과 하한을 찾는 연산도 마찬가지입니다.

언어별로 이 네 가지가 어떤 이름으로 제공되는지는 언어별 리스트 비교와 언어별 맵 비교에서 나란히 확인할 수 있습니다.

선형 스캔과 해시 조회를 코드로 세워 보기

import random, time

def build(n):
    ids = [random.randrange(0, 10_000_000) for _ in range(n)]
    rows = [{"id": i, "name": f"user-{i}"} for i in ids]
    index = {row["id"]: row for row in rows}     # 한 번만 만든다
    return rows, index, ids

def scan_lookup(rows, key):                       # O(n): 최악에 전부 훑는다
    for row in rows:
        if row["id"] == key:
            return row
    return None

def hash_lookup(index, key):                      # 평균 O(1)
    return index.get(key)

def measure(fn, arg, keys):
    start = time.perf_counter()
    for k in keys:
        fn(arg, k)
    return time.perf_counter() - start

for n in (1_000, 10_000, 100_000):
    rows, index, ids = build(n)
    keys = random.sample(ids, 200)                # 조회는 항상 200번
    t_scan = measure(scan_lookup, rows, keys)
    t_hash = measure(hash_lookup, index, keys)
    print(n, round(t_scan / t_hash, 1))

# 관찰되는 경향 (구체적인 값은 환경마다 다릅니다)
#   n =   1,000 -> 스캔이 해시보다 수십 배 느림
#   n =  10,000 -> 격차가 대략 n에 비례해 커짐
#   n = 100,000 -> 다시 약 10배 더 벌어짐
#
# 읽는 법: 조회 횟수를 고정했는데 n을 10배로 키울 때마다
#          스캔 시간은 대략 10배가 되고 해시 시간은 거의 그대로다.
#          이 "기울기"가 O(n)과 O(1)의 실제 의미다.

# 주의: 인덱스를 만드는 비용은 O(n)이다.
#   조회를 딱 한 번만 한다면 인덱스를 만드는 편이 오히려 손해다.
#   조회 횟수를 q라고 하면 대략 이렇게 비교한다.
#     스캔 총비용   = q * n
#     해시 총비용   = n (인덱스 구축) + q * 1
#   즉 q가 1보다 충분히 크면 해시가 이긴다. q = 1이면 비긴다.

이 코드에서 면접용으로 가져갈 것은 숫자가 아니라 두 가지 사고입니다. 첫째, 복잡도는 절대 시간이 아니라 입력이 커질 때의 기울기라는 점입니다. 조회 횟수를 고정하고 n만 키웠을 때 한쪽은 비례해서 늘고 다른 쪽은 그대로라는 관찰이 곧 O(n)과 O(1)의 정의입니다. 둘째, 구축 비용을 총비용에 포함해야 한다는 점입니다. 인덱스를 만드는 데 O(n)이 들므로, 조회를 몇 번 할 것인지가 답을 바꿉니다. 이 두 문장을 말할 수 있으면 “해시가 빠릅니다”보다 훨씬 앞선 답이 됩니다.

동적 배열은 왜 상환 상수 시간인가

동적 배열은 고정 크기 저장 공간을 잡아 두고 쓰다가, 다 차면 더 큰 공간을 새로 잡아 전부 복사합니다. 그 복사는 명백히 O(n)입니다. 그런데도 추가 연산의 비용을 상환 O(1)이라고 부르는 이유는 얼마나 자주 복사하는가에 있습니다.

용량을 늘릴 때 일정 배수로 늘린다는 점이 핵심입니다. 예를 들어 두 배로 늘리면 용량이 1, 2, 4, 8, 16처럼 커집니다. 원소를 n개 넣는 동안 복사한 원소의 총합은 1 + 2 + 4 + … 로 n보다 작은 등비수열의 합이고, 이는 n의 상수배를 넘지 않습니다. 총비용을 삽입 횟수 n으로 나누면 한 번당 상수입니다. 이것이 상환 분석입니다.

반대로 용량을 고정된 양만큼, 예를 들어 열 칸씩 늘린다면 이야기가 완전히 달라집니다. 복사가 n/10번 일어나고 각 복사가 평균 n/2 규모이므로 총비용이 n의 제곱에 비례합니다. 배수 증가와 고정량 증가의 차이를 설명할 수 있으면 상환이라는 개념을 진짜로 이해했다는 신호가 됩니다.

여기에 실무적인 단서를 하나 더 붙이면 좋습니다. 상환 상수라는 말은 평균적으로 상수라는 뜻이지 모든 삽입이 빠르다는 뜻이 아닙니다. 확장이 일어나는 그 한 번의 삽입은 여전히 O(n)이고, 지연 시간의 상한이 중요한 시스템에서는 이 튐이 문제가 됩니다. 최종 크기를 미리 알 수 있다면 용량을 미리 잡아 두어 확장을 아예 없애는 것이 정답입니다.

해시가 평균 O(1)이고 최악 O(n)인 이유

해시 맵은 키를 정수로 바꾸고 그 정수로 버킷을 고릅니다. 키가 버킷에 고르게 흩어지면 한 버킷에 들어가는 원소 수가 대략 상수로 유지되고, 조회는 버킷 하나를 확인하는 것으로 끝나니 상수 시간입니다. 이 “고르게 흩어진다”가 성립하지 않으면 전부 무너집니다.

모든 키가 같은 버킷으로 몰리면 그 버킷은 사실상 하나의 목록이 되고, 조회는 그 목록 전체를 훑는 선형 탐색이 됩니다. 그래서 최악이 O(n)입니다. 이런 몰림이 생기는 원인은 세 가지입니다. 해시 함수가 나쁘거나, 키의 분포가 해시 함수의 약점과 맞아떨어지거나, 누군가 의도적으로 충돌하는 키를 만들어 넣는 경우입니다. 마지막 경우는 실제 공격 기법이며, 그래서 현대적인 해시 맵 구현은 프로세스마다 다른 무작위 씨앗을 쓰거나 한 버킷이 커지면 그 버킷을 트리로 바꾸는 식으로 대비합니다.

면접에서 자주 이어지는 질문이 “그럼 최악이 O(n)인데 왜 씁니까”입니다. 좋은 답은 확률과 조건을 분리하는 것입니다. 균등한 해시 함수와 적절한 적재율에서는 최악 사례가 사실상 나타나지 않으며, 나타난다면 그것은 자료구조의 문제가 아니라 키의 성질이나 해시 함수의 문제라고 답합니다. 그리고 최악 사례가 실제 위험이 되는 상황, 즉 키를 외부 사용자가 정하는 경우에는 무작위 씨앗이 있는 구현을 쓰거나 트리 맵으로 바꾸겠다고 덧붙이면 완결됩니다.

적재율이라는 단어도 알아 두면 좋습니다. 원소 수를 버킷 수로 나눈 값이고, 이 값이 커지면 충돌이 늘어나므로 구현은 일정 기준을 넘으면 버킷 수를 늘리고 전부 재배치합니다. 이 재배치도 동적 배열의 확장과 같은 상환 논리로 분석되며, 마찬가지로 그 순간의 지연이 튄다는 특성을 공유합니다. 키를 직접 정의할 때는 동등성 판단과 해시 값이 반드시 일관되어야 한다는 점도 함께 기억하십시오. 같다고 판단되는 두 키의 해시가 다르면 넣은 값을 영원히 찾지 못합니다.

순서 보장이 결정적인 순간

순서라는 말은 세 가지를 뜻할 수 있고, 면접에서는 이 셋을 구분해 말하는 것이 유용합니다. 삽입 순서는 넣은 차례를 그대로 유지하는 것이고, 정렬 순서는 키의 대소로 정렬된 상태를 유지하는 것이며, 순서 없음은 순회 순서를 아무것도 약속하지 않는 것입니다.

이 구분이 실무에서 문제를 만드는 지점은 “지금 마침 순서대로 나온다”를 보장으로 착각할 때입니다. 순서를 약속하지 않는 자료구조가 우연히 정렬된 결과를 내는 일은 흔하고, 원소가 늘거나 구현이 바뀌면 그 우연은 사라집니다. 테스트가 통과하다가 데이터가 늘어난 뒤에 깨지는 전형적인 이유가 이것입니다.

정렬 순서가 필요한 대표적인 요구는 범위 질의, 상한·하한 탐색, 페이지 이어 보기, 우선순위가 낮은 것부터 처리하기입니다. 이 요구가 하나라도 있으면 트리 계열을 검토해야 합니다. 반대로 “결과를 화면에 정렬해서 보여 준다”는 요구뿐이라면 해시로 담고 마지막에 한 번 정렬하는 편이 대개 낫습니다. 매번 정렬 상태를 유지하는 비용보다 한 번 정렬하는 비용이 작기 때문입니다. 이 판단, 즉 정렬을 항상 유지할 것인가 필요할 때 한 번 할 것인가를 언급하면 답의 밀도가 올라갑니다.

작은 n에서는 지역성이 빅오를 이깁니다

복잡도는 n이 충분히 클 때의 성질을 말합니다. 상수 계수를 버리기 때문에, 상수가 크게 차이 나는 두 자료구조를 작은 n에서 비교하면 이론이 뒤집히는 일이 자주 있습니다.

가장 흔한 사례가 배열과 연결 리스트의 순회입니다. 둘 다 O(n)이지만 배열은 원소가 메모리에 연속으로 놓여 있어 캐시가 한 번에 여러 원소를 가져옵니다. 연결 리스트는 원소가 흩어져 있고 매번 다음 주소를 따라가야 하므로 캐시가 거의 도움이 되지 않습니다. 같은 복잡도에서 실제 속도가 크게 벌어지는 이유입니다.

원소가 열 개뿐인 목록에서 값을 찾는 경우도 마찬가지입니다. 이론상 해시 조회가 유리하지만, 해시 값을 계산하고 버킷을 찾아가는 비용이 열 번의 비교보다 클 수 있습니다. 그래서 작은 컬렉션을 다루는 라이브러리들이 일정 크기 이하에서는 단순 배열로 유지하다가 커지면 해시로 전환하는 전략을 쓰기도 합니다.

면접에서 이 이야기를 꺼낼 때는 반드시 방향을 지켜야 합니다. “복잡도는 의미 없습니다”가 아니라 “복잡도가 선택의 1순위이되, 규모가 작고 이 코드가 뜨거운 경로라면 측정해서 확인하겠습니다”입니다. 앞의 문장은 위험 신호로 읽히고 뒤의 문장은 성숙함으로 읽힙니다.

실전 문제: 자료구조 하나를 고르는 대화

질문: “주문 처리 서비스가 있습니다. 하루에 수백만 건의 주문 이벤트가 들어오고, 각 이벤트가 올 때마다 해당 주문의 현재 상태를 찾아 갱신해야 합니다. 그리고 30분마다 ‘최근 한 시간 안에 생성됐고 아직 완료되지 않은 주문’ 목록을 뽑아야 합니다. 메모리에 어떤 자료구조를 두시겠습니까?”

약한 답

“주문 아이디로 찾아야 하니까 해시 맵을 쓰겠습니다. 조회가 O(1)이라 수백만 건도 빠릅니다. 목록을 뽑을 때는 전체를 순회하면서 조건에 맞는 것만 필터링하면 됩니다. 필요하면 정렬해서 반환하겠습니다.”

강한 답

“접근 패턴이 두 종류라서 하나로는 안 될 것 같습니다. 먼저 나눠 보겠습니다.

첫 번째는 이벤트마다 일어나는 주문 아이디 단건 조회이고, 빈도가 압도적으로 높습니다. 하루 수백만 건이면 초당 수십 건 이상이고 피크에는 그보다 훨씬 몰릴 것입니다. 두 번째는 30분마다 한 번인 시간 범위 질의입니다. 빈도는 낮지만 대상이 전체 주문이라 한 번의 비용이 큽니다.

첫 번째만 보면 해시 맵이 맞습니다. 키가 주문 아이디로 명확하고, 순서가 필요 없고, 조회가 평균 상수입니다.

문제는 두 번째입니다. 해시 맵만 두면 범위 질의를 전체 순회로 처리해야 하고, 그러면 비용이 맞는 항목 수가 아니라 전체 주문 수에 비례합니다. 미완료 주문이 전체의 아주 작은 비율이라면 이건 낭비가 큽니다. 게다가 이 순회가 도는 동안 조회 경로와 같은 자료구조를 붙잡게 되면 지연에도 영향을 줍니다.

그래서 저는 두 구조를 함께 두겠습니다. 주문 아이디를 키로 하는 해시 맵이 주 저장소이고, 여기에 (생성시각, 주문아이디)를 키로 하는 정렬된 인덱스를 미완료 주문에 대해서만 유지하겠습니다. 정렬 인덱스가 있으면 ‘한 시간 전 시각’으로 시작 위치를 찾아 거기서부터 순회하면 되므로, 비용이 전체 주문 수가 아니라 결과 개수에 비례합니다. 주문이 완료되면 인덱스에서 제거하므로 인덱스 크기 자체도 미완료 건수만큼으로 유지됩니다.

대가는 두 가지입니다. 하나는 쓰기 비용입니다. 상태를 갱신할 때 두 구조를 함께 갱신해야 하고, 완료 처리 시 인덱스에서 지우는 것을 빠뜨리면 유령 항목이 남습니다. 그래서 두 구조의 갱신을 한 함수 안에 묶어 두고 그 함수 밖에서는 직접 건드리지 못하게 캡슐화하겠습니다. 다른 하나는 메모리입니다. 인덱스가 참조만 들고 있게 하면 중복 저장은 피할 수 있습니다.

마지막으로 규모를 확인하고 싶습니다. 하루 수백만 건이 메모리에 계속 쌓이는지, 완료된 주문은 얼마나 빨리 빠지는지를 알아야 이 설계가 유지 가능한지 판단할 수 있습니다. 완료 주문이 계속 남는 구조라면 메모리 자료구조를 고를 문제가 아니라 만료 정책이나 외부 저장소를 먼저 정해야 하는 문제라고 보겠습니다.”

강한 답이 이긴 이유

약한 답도 해시 맵을 골랐고, 그 선택 자체는 틀리지 않았습니다. 그런데 답의 순서를 보면 문제가 드러납니다. 약한 답은 첫 문장에서 자료구조를 정해 버린 뒤, 두 번째 요구가 그 자료구조와 맞지 않는다는 사실을 “전체를 순회하면 됩니다”로 덮었습니다. 순회 비용이 결과 수가 아니라 전체 수에 비례한다는 점은 언급되지 않았고, 그래서 30분마다 전체를 훑는다는 결정이 얼마나 비싼지 스스로도 모릅니다.

강한 답은 자료구조를 고르기 전에 접근 패턴을 두 개로 나누고, 각각의 빈도와 한 번의 비용을 따로 셌습니다. 그러고 나서야 “하나로는 두 패턴을 다 만족할 수 없다”는 결론이 나왔고, 그 결론이 두 구조를 함께 두는 선택을 정당화했습니다. 이어서 그 선택이 무엇을 대가로 지불하는지를 스스로 꺼내 놓았습니다. 쓰기 경로가 복잡해지고 두 구조의 일관성을 지켜야 한다는 것입니다. 마지막에는 이 설계의 전제가 성립하는 조건, 즉 미완료 주문의 규모를 되물었습니다.

차이는 단어 선택이 아니라 결정을 내리는 지점의 위치입니다. 약한 답은 정보를 다 모으기 전에 결정하고 나머지를 그 결정에 끼워 맞췄습니다. 강한 답은 결정을 뒤로 미루고 그 앞에 판단 근거를 쌓았습니다. 그래서 면접관이 조건을 바꿔 되물어도, 예를 들어 “범위 질의가 30분이 아니라 1초마다 필요하다면요”라고 물어도 강한 답은 이미 만들어 둔 빈도와 비용의 표에서 답을 다시 계산하면 됩니다.

흔히 무너지는 지점

인덱스 구축 비용을 빼고 세는 것입니다. 반복문 안에서 매번 사전을 새로 만들면서 “해시라 O(1)입니다”라고 말하는 코드가 실제로 자주 나옵니다. 구축이 반복문 안에 있으면 총비용은 전혀 개선되지 않습니다.

연결 리스트의 삽입 비용을 탐색과 분리하지 않는 것입니다. 위치를 알고 있을 때만 상수 시간이라는 조건을 빼면 잘못된 선택으로 이어집니다.

순회 순서를 보장으로 착각하는 것입니다. 지금 정렬되어 보인다는 관찰은 약속이 아닙니다. 순서가 필요하면 순서를 보장하는 자료구조를 쓰거나 명시적으로 정렬해야 합니다.

가변 객체를 해시 키로 쓰는 것입니다. 키로 넣은 뒤 그 객체의 필드를 바꾸면 해시 값이 달라져 원래 버킷에서 찾을 수 없게 됩니다. 값은 안에 남아 있는데 조회는 실패하고 순회로는 보이는 기묘한 상태가 됩니다. 키는 불변으로 두는 것이 원칙입니다.

중복 제거를 배열로 하는 것입니다. 이미 있는지 확인하려고 매번 목록을 훑으면 전체가 제곱 시간이 됩니다. 집합 자료구조로 바꾸는 것만으로 선형이 되며, 이것이 코드 리뷰에서 가장 자주 지적되는 복잡도 문제입니다.

규모를 확인하지 않고 답하는 것입니다. 원소가 항상 열 개 이하라면 무엇을 써도 상관없고, 그때는 읽기 쉬운 코드가 답입니다. 반대로 메모리에 다 올라가지 않는 규모라면 자료구조 선택이 아니라 저장소 선택 문제로 넘어가야 합니다.

꼬리 질문에 대비하기

답하기 전 점검표

• 자료구조 이름보다 연산 목록을 먼저 말하는가
• 조회 키, 순서 요구, 삽입 위치, 순회 빈도, 규모의 다섯 축을 확인하는가
• 평균·최악·상환 중 어느 것을 말하는지 매번 밝히는가
• 인덱스 구축 비용을 총비용에 포함해 계산하는가
• 배수 증가와 고정량 증가의 차이로 상환 상수를 설명할 수 있는가
• 해시 최악 사례가 언제 실제 위험이 되는지 말할 수 있는가
• 순서 요구를 삽입 순서와 정렬 순서로 구분하는가
• 정렬을 항상 유지할지 필요할 때 한 번 할지 비교하는가
• 지역성 이야기를 “복잡도는 무의미하다”가 아닌 방향으로 말하는가
• 선택의 대가를 스스로 먼저 꺼내 놓는가

연습 방법

익숙한 코드에서 중첩 반복문을 하나 찾아 총 연산 횟수를 손으로 계산해 보십시오. 바깥이 n번, 안쪽이 평균 m번이면 곱이 총비용입니다. 그다음 안쪽을 사전 조회로 바꾸면 총비용이 어떻게 바뀌는지 다시 계산하고, 실제로 바꿔서 시간을 재 보십시오. 계산한 기울기와 관찰한 기울기가 맞는지 확인하는 과정이 이 주제에서 가장 확실한 훈련입니다.

다음으로는 위의 주문 문제를 변형해 보십시오. 범위 질의가 1초마다 필요하다면, 주문이 완료되지 않고 계속 쌓인다면, 서버가 여러 대여서 상태가 한 곳에 없다면 답이 어떻게 달라지는지 말로 설명해 보는 것입니다. 이어서 볼 주제로는 메모리와 참조가 잘 맞습니다. 자료구조가 메모리에 어떻게 놓이는가가 여기서 말한 지역성의 근거이기 때문입니다. 공유 컬렉션을 여러 흐름이 함께 만질 때의 문제는 공유 상태 동시성에서 다룹니다.

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