D-2: 면접에 나오는 자료구조·복잡도

안녕하세요, 홍순구 튜터입니다. CS 기초 열한 번째 시간, D 카테고리의 두 번째이자 면접 기초의 마지막 갈래 — 자료구조와 복잡도입니다.

지난 시간 우리는 데이터베이스 안으로 들어가 인덱스를 봤죠. 거기서 제가 두 가지를 슬쩍 흘렸습니다 — 인덱스는 B+트리라는 트리 구조로 만들고, 그 덕에 풀 스캔(O(n))이 O(log n) 으로 줄어든다고요. 그때 "이 O(log n)은 다음 시간 자료구조에서 다시 만난다"고 약속했어요. 오늘이 그날입니다. 그 트리와 그 빅오를, 데이터베이스 한 곳이 아니라 자료구조 전반으로 펼칩니다. 지난 시간 인덱스가 그 첫 다리였던 셈이에요.

왜 이게 면접에서 중요할까요? 신입 개발자 기술 면접에서 자료구조와 복잡도는 거의 빠지지 않습니다. "이 코드의 시간 복잡도가 어떻게 되나요?", "배열과 링크드 리스트의 차이가 뭐죠?", "해시 충돌이 나면 어떻게 되나요?" — 이런 질문에 원리와 트레이드오프로 답하는 사람과 외운 단어만 던지는 사람이 또렷이 갈립니다. 우리가 이 과목 내내 연습한 "왜 이렇게 동작하는가"를 자료구조에 적용하는 시간이에요.

한 가지 먼저 선을 그어둘게요. 자료구조와 알고리즘은 그 자체로 한 과목(data-structures-algorithms)을 꽉 채우는 큰 주제입니다. 자료구조를 직접 구현하고, 정렬을 코드로 짜고, 코딩 테스트 문제를 푸는 깊이는 그 과목의 몫이에요. 오늘 우리가 다루는 건 "면접관이 물으면 원리와 트레이드오프로 답할 수 있다"까지 — 빅오로 빠르기를 재고, 자료구조를 "언제 무엇으로" 고를지 설명하는 선까지입니다. 구현 코드는 거의 쓰지 않고 개념과 그림으로 갑니다.

오늘 우리가 걸을 길은 이렇습니다.

   오늘의 여정 — 면접에 나오는 자료구조·복잡도

   ① 복잡도란 — 빠르기를 입력 크기로 재는 법
   ② 빅오 표기 — O(1)부터 O(n²)까지 직관으로 (면접 빈출)
   ③ 배열 vs 연결 리스트 — 같은 목록, 다른 트레이드오프 (면접 1순위)
   ④ 스택과 큐 — LIFO·FIFO, 어디 쓰나 (면접 빈출)
   ⑤ 해시 테이블 — 평균 O(1)의 비결과 충돌 (면접 빈출)
   ⑥ 트리·BST·힙 — 정렬된 트리로 O(log n)
   ⑦ 그래프 — 정점과 간선으로 관계를 표현
   ⑧ 복잡도 표 총정리 — 자료구조·정렬을 한눈에

①에서 "빠르기를 어떻게 재는가"의 토대를 잡고, ②에서 그 측정 도구인 빅오를 손에 익힙니다. ③~⑦에서 면접 단골 자료구조를 하나씩 트레이드오프로 보고, ⑧에서 전부를 복잡도 표로 묶어 마무리합니다.

💡 오늘 수업의 핵심 — "자료구조의 빠르기는 빅오(입력이 커질 때의 증가율)로 재고, 자료구조는 우열이 아니라 연산별 트레이드오프로 고른다. 배열은 임의 접근이 O(1)이고 연결 리스트는 삽입·삭제가 O(1)이며, 해시는 평균 O(1)이지만 충돌이 나면 느려지고, 탐색 트리는 O(log n)이되 균형이 무너지면 O(n)이 된다" 🎯

🎯 학습 목표

• 시간/공간 복잡도와 빅오 5종(O(1)·O(log n)·O(n)·O(n log n)·O(n²))을 실제 연산에 매핑하고, 입력이 커질 때 무엇이 빠르고 느린지를 직관으로 설명합니다.
• 배열 vs 연결 리스트, 스택·큐, 해시 테이블(충돌 포함)을 각각 어떤 상황에 쓰는지 트레이드오프로 답합니다.
• 트리·BST·힙·그래프의 핵심 연산 복잡도를 정리하고, 자료구조·정렬 복잡도 표를 면접에서 한 호흡에 풀어냅니다.

Step 1: "복잡도란 — 빠르기를 어떻게 재는가"

면접관이 "이 코드의 시간 복잡도가 어떻게 되나요?"라고 물으면, 사실은 "이 코드가 얼마나 빠른가요?"를 묻는 겁니다. 그런데 빠르기를 그냥 "몇 초"로 재면 안 될까요? 여기서부터 출발합니다.

같은 코드라도 빠른 컴퓨터에서는 1초, 느린 노트북에서는 3초가 걸립니다. 데이터가 10개일 때와 1억 개일 때도 천지 차이고요. "몇 초"는 기계와 상황에 따라 춤을 춰서, 코드 자체의 빠르기를 비교하는 잣대로 못 씁니다. 그래서 컴퓨터 과학은 빠르기를 다르게 재요 — 입력 크기를 n이라 할 때, n이 커지면 연산 횟수가 어떤 속도로 늘어나는가로 잽니다. 기계가 무엇이든, 입력이 무엇이든 변하지 않는 잣대죠.

예를 들어 봅시다. 배열에서 "맨 앞 원소 하나"를 꺼내는 일은 데이터가 10개든 1억 개든 딱 한 번의 연산이면 끝납니다. 입력이 아무리 커져도 연산 횟수가 그대로예요. 반면 "배열을 처음부터 끝까지 훑어 특정 값을 찾는" 일은 데이터가 10개면 최대 10번, 1억 개면 최대 1억 번을 봐야 합니다. 입력에 비례해서 늘어나죠. 이 "늘어나는 속도"의 차이가 복잡도의 본질입니다.

복잡도는 두 종류로 잽니다.

• 시간 복잡도(time complexity): 입력이 커질 때 연산 횟수가 늘어나는 속도. 보통 "복잡도"라 하면 이걸 가리킵니다.
• 공간 복잡도(space complexity): 입력이 커질 때 추가로 쓰는 메모리가 늘어나는 속도.

그리고 같은 코드도 입력 데이터에 따라 빠를 수도 느릴 수도 있어요. 그래서 보통 최악의 경우(worst case)를 기준으로 잡습니다. 왜 최악이냐면, "이 코드는 아무리 운이 나빠도 이만큼은 보장한다"가 가장 쓸모 있는 약속이기 때문이에요. 면접에서 "복잡도가 어떻게 되냐"고 물으면 특별한 말이 없는 한 최악 기준으로 답하면 됩니다.

마지막으로 중요한 감각 하나 — 시간과 공간은 자주 맞바꿉니다.

   시간-공간 트레이드오프 — 하나를 줄이려면 다른 하나를 쓴다

   매번 다시 계산한다        →  시간 많이,  공간 적게
   미리 계산해 저장해 둔다    →  시간 적게,  공간 많이

   예) 자주 쓰는 결과를 메모리에 저장(메모이제이션·캐시)
       = 공간을 더 써서 시간을 아낀다

A-2에서 배운 캐시가 정확히 이 거래예요. 자주 쓰는 데이터를 빠른 메모리에 미리 담아두면(공간을 더 씀), 매번 느린 곳에서 가져오지 않아도 되죠(시간을 아낌). 복잡도를 본다는 건 결국 "이 코드가 시간을 쓰는가, 공간을 쓰는가, 그 균형이 맞는가"를 보는 일입니다.

🎯 면접에서는 이렇게 답하세요

"시간 복잡도는 입력 크기 n이 커질 때 연산 횟수가 늘어나는 속도를 나타낸 거예요. 실행 시간을 초로 재면 컴퓨터 성능과 입력에 따라 달라져서, 기계와 무관하게 증가율로 잽니다. 보통 최악의 경우를 기준으로 잡고요. 공간 복잡도는 같은 방식으로 추가 메모리 사용량을 재는데, 시간과 공간은 자주 트레이드오프 관계라 — 미리 계산해 저장하면 공간을 써서 시간을 아끼는 식입니다."

Step 2: "빅오 표기 — O(1)부터 O(n²)까지 직관으로"

이제 복잡도를 적는 표기법을 익힙니다. 면접에서 "빅오가 뭐예요?"는 그 자체로 단골 질문이에요. 빅오(Big-O)는 입력이 커질 때 연산 횟수가 늘어나는 속도의 상한을 적는 약속입니다. 핵심은 "정확한 횟수"가 아니라 "증가율"이라는 거예요.

규칙이 두 개 있습니다. 첫째, 상수와 계수는 버립니다. 연산이 2n + 3번이어도 빅오로는 O(n)이에요. 둘째, 가장 빠르게 자라는 항만 남깁니다. n² + 100n + 5는 O(n²)이고요. 왜 이렇게 거칠게 버릴까요? n이 충분히 커지면 최고차항이 나머지를 압도하기 때문입니다. n이 100만일 때 n²은 1조인데 100n은 1억이라, 100n은 있으나 마나죠. 빅오는 "데이터가 아주 커졌을 때 누가 지배하는가"만 봅니다.

자주 나오는 다섯 가지를 빠른 순서대로 보겠습니다.

• O(1) — 상수 시간. 입력 크기와 무관하게 항상 같은 횟수. 배열의 인덱스 접근(arr[5]), 해시 테이블 조회가 여기예요. 데이터가 1억 개여도 한 번에 끝납니다.
• O(log n) — 로그 시간. 한 번 처리할 때마다 후보가 절반씩 줄어듭니다. 정렬된 데이터의 이진 탐색, BST·B+트리(지난 시간 인덱스!) 가 여기예요. 1억 개여도 약 27단계면 닿습니다.
• O(n) — 선형 시간. 입력에 비례. 배열을 한 번 훑는 선형 탐색, 데이터베이스 풀 스캔(지난 시간!) 이 여기예요.
• O(n log n) — 선형 로그 시간. 좋은 정렬(병합·힙·퀵 평균)이 여기. O(n)보다 약간 무겁지만 실용적으로 빠른 정렬의 기준선입니다.
• O(n²) — 제곱 시간. 데이터를 이중으로 도는 경우. 단순한 정렬(버블·선택·삽입)이나 "모든 쌍을 비교"하는 코드가 여기예요. 데이터가 조금만 커져도 급격히 느려집니다.

곡선으로 그리면 그 차이가 한눈에 들어옵니다.

   빅오 곡선 — 입력 n 이 커질수록 연산 횟수가 얼마나 빨리 느는가

   많음
    ▲                          O(n^2)
    │                        /
    │                      /
    │                    /              O(n log n)
    │                  /             /
    │                /           /
    │              /         /            O(n)
    │            /       /            /
    │          /     /           /
    │        /   /          /
    │      /  /        /              ____ O(log n)
    │    / /      /        ______/
    │  ///   __/    ______/____________________ O(1)
    └────────────────────────────────────────▶
   적음              입력 크기 n →             많음

   완만할수록 빠르고, 가파를수록 느리다.
   순서:  O(1) < O(log n) < O(n) < O(n log n) < O(n^2)

숫자로 체감해 볼까요. 데이터 n이 100만 개일 때 대략 이렇습니다.

같은 100만 개인데 O(n log n)은 2천만 번, O(n²)은 1조 번이에요. 5만 배 차이가 납니다. 그래서 "데이터가 커질 서비스"에서는 O(n²)짜리 코드가 평소엔 멀쩡하다가 데이터가 늘면서 갑자기 죽어버려요. 빅오를 볼 줄 안다는 건 이 "터질 코드"를 미리 알아본다는 뜻입니다.

🎯 면접에서는 이렇게 답하세요

"빅오는 입력이 커질 때 연산 횟수가 늘어나는 증가율의 상한을 적은 표기예요. 상수와 계수를 버리고 최고차항만 남기는데, n이 커지면 최고차항이 나머지를 압도하기 때문입니다. 빠른 순서로 O(1) < O(log n) < O(n) < O(n log n) < O(n²) 이고, 각각 해시 조회·이진 탐색·선형 탐색·좋은 정렬·이중 루프가 대표예요. 핵심은 '데이터가 커졌을 때 누가 지배하느냐'를 보는 거라, n이 작을 땐 빅오가 큰 코드가 오히려 빠를 수도 있습니다."

Step 3: "배열 vs 연결 리스트 — 같은 목록, 다른 트레이드오프"

면접에서 자료구조 질문 1순위를 꼽으라면 단연 "배열과 링크드 리스트(연결 리스트)의 차이가 뭔가요?" 입니다. 둘 다 "값을 순서대로 담는 목록"인데, 메모리에 담기는 방식이 정반대라 잘하는 것과 못하는 것이 갈려요. 이 차이를 메모리 구조로 이해하면 면접 답이 저절로 나옵니다.

   배열 — 메모리에 연속으로 붙어 있다 (인덱스로 즉시 점프)

   주소:   100   104   108   112
         ┌─────┬─────┬─────┬─────┐
         │  a  │  b  │  c  │  d  │
         └─────┴─────┴─────┴─────┘
   인덱스:   0     1     2     3
         → arr[2] = 시작주소 + (2 × 칸크기) = 계산 한 번에 점프 → O(1)
         → 맨 앞(0번)에 끼우려면 뒤를 전부 밀어야 함 → O(n)


   연결 리스트 — 노드가 흩어져 있고 포인터로 이어진다

         [ a |·]──▶[ b |·]──▶[ c |·]──▶[ d |/]
           값 다음                        끝(null)
         → 3번째를 보려면 맨 앞부터 화살표를 따라가야 함 → O(n)
         → 중간에 끼우려면 화살표 두 개만 고치면 됨 → O(1)

배열은 연속된 메모리에 빈틈없이 붙어 있어요. 그래서 arr[2]를 찾을 때 "시작 주소 + 2칸"을 계산해 단번에 점프합니다. 이게 임의 접근(random access)이고 O(1)이에요. 대신 중간에 값을 끼우거나 빼려면, 뒤에 있는 원소를 전부 한 칸씩 밀어야 해서 O(n)입니다.

연결 리스트는 정반대예요. 값들이 메모리 여기저기 흩어져 있고, 각 노드가 "다음 노드의 주소(포인터)"를 들고 화살표처럼 이어집니다. 그래서 3번째 값을 보려면 맨 앞부터 화살표를 하나씩 따라가야 해서 접근이 O(n)이에요. 대신 중간에 끼울 때는 화살표 두 개만 고쳐 끼우면 끝이라 O(1)입니다(끼울 위치를 이미 알고 있을 때).

여기에 A-2에서 배운 캐시가 한 겹 더해집니다. 배열은 메모리에 연속이라, CPU가 한 번 읽을 때 근처 데이터까지 캐시로 끌어와 다음 접근이 빨라져요(공간 지역성). 연결 리스트는 흩어져 있어 이 이점을 못 누립니다. 그래서 빅오가 같아도 배열이 실제로는 더 빠른 경우가 많아요 — Step 2에서 말한 "빅오가 같다고 똑같지는 않다"의 좋은 예입니다.

정리하면 선택 기준은 명확합니다. 인덱스로 마구 접근하고 조회가 잦으면 배열, 중간 삽입·삭제가 잦고 크기가 자주 변하면 연결 리스트예요. 참고로 우리가 흔히 쓰는 "동적 배열"(자바의 ArrayList, 파이썬의 list)은 내부가 배열이고, 꽉 차면 더 큰 배열로 옮겨 담는 식으로 동작합니다. 구현을 직접 짜보는 건 data-structures-algorithms 과목에서 다루고, 여기서는 "왜 이 트레이드오프인가"까지만 잡으면 충분해요.

🎯 면접에서는 이렇게 답하세요

"배열은 메모리에 연속으로 붙어 있어서 인덱스로 즉시 접근(O(1)) 하지만, 중간 삽입·삭제는 뒤를 다 밀어야 해서 O(n) 이에요. 연결 리스트는 노드가 흩어져 포인터로 이어져서, 접근은 앞에서부터 따라가야 해 O(n) 이지만 중간 삽입·삭제는 포인터만 바꿔 O(1) 입니다. 그래서 임의 접근·조회가 잦으면 배열, 삽입·삭제가 잦으면 연결 리스트를 써요. 덧붙여 배열은 연속 메모리라 캐시 지역성도 좋아서, 빅오가 같아도 실제론 더 빠른 경우가 많습니다."

Step 4: "스택과 큐 — LIFO·FIFO, 어디 쓰나"

스택과 큐는 배열·연결 리스트 위에 "꺼내는 순서 규칙" 을 얹은 자료구조예요. 면접에서 "스택과 큐가 뭐고 어디에 쓰나요?"가 자주 나오는데, 핵심은 순서입니다.

   스택 (Stack) — LIFO, 나중에 넣은 게 먼저 나온다

        push ▼   ▲ pop
           ┌─────┐
           │  C  │  ← top (가장 최근에 넣음, 먼저 나감)
           ├─────┤
           │  B  │
           ├─────┤
           │  A  │  ← bottom (가장 먼저 넣음, 마지막에 나감)
           └─────┘


   큐 (Queue) — FIFO, 먼저 넣은 게 먼저 나온다

       ┌───┬───┬───┬───┐
       │ A │ B │ C │ D │
       └───┴───┴───┴───┘
         ▲front       ▲rear
       front 에서 꺼내고(dequeue, 먼저 나감), rear 로 넣는다(enqueue, 뒤로 들어옴)

스택(stack)은 LIFO(Last In, First Out) — 마지막에 넣은 게 먼저 나옵니다. 접시를 쌓았다가 위에서부터 빼는 모습이에요. 넣기(push)와 빼기(pop)가 모두 맨 위에서만 일어나 둘 다 O(1) 입니다.

스택이 어디 쓰이냐면, 사실 우리가 B-1에서 이미 만났어요 — 함수 호출 스택입니다. 함수가 다른 함수를 부르면 호출 정보가 스택에 쌓이고, 가장 최근에 불린 함수가 먼저 끝나며 빠지죠. 그 외에도 실행 취소(Ctrl+Z), 브라우저 뒤로 가기, 수식의 괄호 짝 맞추기가 전부 "가장 최근 것부터 되돌리는" 스택의 일이에요.

큐(queue)는 FIFO(First In, First Out) — 먼저 넣은 게 먼저 나옵니다. 매표소 줄과 똑같아요. 먼저 온 사람이 먼저 표를 받죠. 뒤로 넣고(enqueue) 앞에서 빼서(dequeue) 둘 다 O(1)입니다. 큐는 작업 대기열(프린터에 보낸 순서대로 인쇄), 서버의 요청 처리 순서, 그리고 그래프를 너비 우선으로 도는 BFS에 쓰여요.

한 가지 면접 포인트 — 스택과 큐는 배열로도, 연결 리스트로도 만들 수 있습니다. 자료구조 자체는 "순서 규칙"이지 "저장 방식"이 아니거든요. 어느 쪽으로 구현하든 핵심 연산(push/pop, enqueue/dequeue)은 O(1)로 맞춥니다. 구현 코드는 data-structures-algorithms에서 직접 짜보고, 여기서는 "LIFO냐 FIFO냐, 어디 쓰나"를 또렷이 답할 수 있으면 됩니다.

🎯 면접에서는 이렇게 답하세요

"스택은 LIFO(나중에 넣은 게 먼저 나옴)예요. 함수 호출 스택, 실행 취소, 뒤로 가기, 괄호 검사처럼 '가장 최근 것부터 되돌리는' 일에 씁니다. 큐는 FIFO(먼저 넣은 게 먼저 나옴)라 매표소 줄과 같고, 작업 대기열·요청 처리·BFS처럼 '온 순서대로 처리하는' 일에 써요. 둘 다 핵심 연산이 O(1) 이고, 배열이나 연결 리스트 위에 순서 규칙만 얹어 구현합니다."

Step 5: "해시 테이블 — 평균 O(1)의 비결과 충돌"

해시 테이블은 면접 단골 중의 단골이에요. "평균 O(1)에 찾는다" 는 마법 같은 성능 때문인데, 면접관은 꼭 한 발 더 들어가 "그럼 해시 충돌이 나면 어떻게 되죠?" 를 물어봅니다. 이 두 가지가 오늘의 핵심이에요.

해시 테이블(hash table)은 키(key)를 값(value)에 연결해 저장하는 자료구조예요. 자바의 HashMap, 파이썬의 dict가 전부 이거죠. 비결은 해시 함수(hash function)입니다. 키를 해시 함수에 넣으면 숫자 하나가 나오고, 그 숫자를 버킷(bucket, 칸)의 번호로 써요. 그래서 "키 → 번호 → 그 칸으로 바로 점프"라 계산 한 번에 찾습니다. 배열에서 인덱스로 점프하던 그 O(1)을, 숫자가 아닌 임의의 키(문자열 등)로도 할 수 있게 만든 셈이에요.

   해시 테이블 — 키를 해시 함수로 버킷 번호로 바꿔 바로 찾는다

   key "hong"  ──▶ hash() ──▶ 2
   key "kim"   ──▶ hash() ──▶ 4
   key "lee"   ──▶ hash() ──▶ 2   ← 충돌! ("hong" 과 같은 2번 버킷)

   버킷
    0 │
    1 │
    2 │──▶ [hong]──▶[lee]      체이닝: 같은 버킷을 리스트로 잇는다
    3 │
    4 │──▶ [kim]

그런데 문제가 있어요. 서로 다른 키가 같은 번호로 나올 수 있습니다. 위 그림에서 "hong"과 "lee"가 둘 다 2번 버킷으로 갔죠. 이게 해시 충돌(hash collision)이에요. 칸은 하나인데 들어갈 게 둘이라, 그냥 두면 하나가 덮여 사라집니다. 그래서 충돌을 해결하는 방법이 필요해요. 크게 두 가지입니다.

• 체이닝(chaining): 한 버킷에 연결 리스트를 달아 충돌한 키들을 줄줄이 잇습니다. 위 그림의 [hong]→[lee]가 이 방식이에요. 찾을 때는 그 버킷의 리스트를 훑습니다.
• 개방 주소법(open addressing): 충돌이 나면 다음 빈 칸을 찾아 들어갑니다. 칸이 꽉 차면 곤란하니 적당히 비워둬야 해요.

여기서 면접의 핵심이 나옵니다 — 그래서 최악의 경우는 O(n) 이에요. 운이 아주 나빠 모든 키가 같은 버킷에 몰리면, 결국 그 안의 리스트를 처음부터 끝까지 훑어야 해서 O(n)이 됩니다. 평균은 O(1)이지만 최악은 O(n)인 거죠. 그래서 실무에서는 충돌이 잘 안 나는 좋은 해시 함수를 쓰고, 버킷이 너무 차면(부하율이 높아지면) 버킷 수를 늘려 다시 배치(리해싱)해서 평균 O(1)을 유지합니다. "평균 O(1)인데 충돌이 몰리면 O(n), 그래서 좋은 해시와 부하율 관리가 중요하다" — 이 한 문장이 면접 정답이에요.

마지막으로 지난 시간과 잇는 포인트 하나. D-1에서 "DB 인덱스는 왜 해시가 아니라 B+트리를 쓰나?"가 살짝 나왔죠. 해시는 정확히 한 값 찾기(equality)엔 평균 O(1)로 최고지만, "30~60 사이" 같은 범위 검색엔 약해요 — 해시는 순서를 흩어버리니까요. 그래서 범위 질의가 중요한 DB 인덱스는 정렬을 유지하는 트리를 씁니다. 이건 다음 Step에서 트리를 보며 다시 짚을게요.

🎯 면접에서는 이렇게 답하세요

"해시 테이블은 키를 해시 함수로 버킷 번호로 바꿔 그 칸으로 바로 점프해서, 평균 O(1) 에 조회·삽입·삭제합니다. 문제는 서로 다른 키가 같은 번호로 가는 충돌인데, 한 버킷에 리스트를 다는 체이닝이나 다음 빈 칸을 찾는 개방 주소법으로 해결해요. 다만 충돌이 한 버킷에 몰리면 그 리스트를 다 훑어야 해서 최악은 O(n) 이라, 좋은 해시 함수와 부하율 관리(리해싱) 로 평균 O(1)을 유지합니다. 대신 범위 검색은 약해서, 그게 중요하면 정렬 트리를 써요."

Step 6: "트리·BST·힙 — 정렬된 트리로 O(log n)"

지난 시간 인덱스에서 만난 트리를 이제 정면으로 봅니다. 트리(tree)는 데이터를 계층 구조로 담는 자료구조예요. 맨 위 하나(루트)에서 가지가 갈라져 내려가는 모습이라, 나무를 거꾸로 세운 그림이에요.

용어부터 짧게 잡고 갈게요. 맨 위 노드가 루트(root), 가지로 이어진 아래 노드가 자식(child), 위가 부모(parent), 더 이상 자식이 없는 끝이 잎(leaf)입니다. 루트에서 잎까지의 단계 수가 높이(height)예요. 이 높이가 곧 복잡도를 좌우합니다.

트리 중에서 면접에 가장 많이 나오는 게 이진 탐색 트리(BST) 예요. 규칙이 딱 하나입니다 — 왼쪽 자식 < 부모 < 오른쪽 자식. 모든 노드가 이 규칙을 지켜요.

   이진 탐색 트리 (BST) — 왼쪽 < 부모 < 오른쪽

             ( 30 )
            /      \
        ( 20 )    ( 60 )
         /  \         \
     ( 10 )( 25 )    ( 90 )

   25 를 찾는 길:
     30 과 비교 → 작다 → 왼쪽으로
     20 과 비교 → 크다 → 오른쪽으로
     25 발견! (비교 3번)
   → 한 번 비교할 때마다 후보가 절반으로 줄어든다 → O(log n)

이 규칙 덕분에 값을 찾을 때 한 번 비교할 때마다 후보가 절반씩 날아갑니다. 찾는 값이 부모보다 작으면 오른쪽은 통째로 버리고 왼쪽만 보면 되니까요. 그래서 탐색·삽입·삭제가 전부 트리 높이에 비례하는 O(log n) 이에요. 1억 개여도 약 27단계면 닿습니다. Step 2에서 본 그 O(log n)의 정체가 바로 이 "절반씩 좁히기"입니다.

그런데 함정이 있어요. 데이터가 이미 정렬된 순서로 들어오면, BST가 한쪽으로만 주르륵 자라 일자(직선) 가 돼버립니다. 그러면 사실상 연결 리스트라 탐색이 O(n) 으로 무너져요. 그래서 실무의 트리는 균형을 자동으로 맞추는 버전을 씁니다 — AVL 트리, 레드-블랙 트리, 그리고 지난 시간 DB 인덱스의 B+트리가 전부 "높이가 한쪽으로 쏠리지 않게" 균형을 잡는 트리예요. "BST는 O(log n)이되 균형이 무너지면 O(n), 그래서 균형 트리를 쓴다"가 면접의 핵심 포인트입니다.

마지막으로 힙(heap)을 한 입만 보겠습니다. 힙은 "부모가 자식보다 항상 크다(또는 작다)"는 규칙만 지키는 트리예요. 최대 힙이면 루트가 항상 최댓값이라, "가장 큰 값을 꺼내는" 일이 빠릅니다. 그래서 우선순위 큐(priority queue) — "먼저 온 순서가 아니라 우선순위가 높은 것부터 처리"하는 대기열 — 를 만들 때 써요. 작업 스케줄러, 다익스트라 길찾기 등에 쓰이고, 삽입·삭제가 O(log n)입니다. BST와 달리 힙은 전체 정렬은 아니고 "맨 위가 최댓값/최솟값"만 보장한다는 점이 차이예요. 힙으로 정렬하는 힙 정렬은 다음 Step 표에서 다시 만납니다.

🎯 면접에서는 이렇게 답하세요

"이진 탐색 트리(BST)는 왼쪽 < 부모 < 오른쪽 규칙이라, 한 번 비교할 때마다 후보가 절반으로 줄어 탐색·삽입·삭제가 O(log n) 이에요. 다만 데이터가 정렬된 순서로 들어오면 한쪽으로 쏠려 일자가 되며 O(n) 으로 무너지기 때문에, 실무에선 균형을 자동으로 맞추는 AVL·레드블랙·B+트리를 씁니다. 힙은 '부모가 자식보다 항상 큰(또는 작은)' 트리라 루트가 최댓값/최솟값이고, 우선순위 큐를 O(log n)으로 구현할 때 써요."

Step 7: "그래프 — 정점과 간선으로 관계를 표현"

마지막 자료구조는 그래프(graph)예요. 트리가 "위에서 아래로 갈라지는 계층"이라면, 그래프는 자유롭게 서로 연결된 관계를 표현합니다. 친구 관계, 지하철 노선도, 웹페이지 사이의 링크 — 이런 "누가 누구와 이어져 있나"가 전부 그래프예요.

그래프는 두 가지로 이뤄집니다 — 정점(vertex, 노드)과 간선(edge, 연결선)이에요. 정점은 대상(사람·역·페이지), 간선은 그 사이의 관계(친구·노선·링크)죠.

   그래프 — 정점과 간선으로 관계를 표현

       (A)───(B)
        │     │
        │     │
       (C)───(D)

   간선:  A-B,  A-C,  B-D,  C-D

그래프에는 종류가 몇 가지 있어요. 방향이 있으면(팔로우: 내가 너를 팔로우해도 너는 아닐 수 있음) 방향 그래프, 없으면(친구: 서로) 무방향 그래프예요. 간선에 가중치가 있으면(역 사이 거리·요금) 가중 그래프고요.

면접 포인트는 "그래프를 메모리에 어떻게 저장하나" 입니다. 두 방식이 트레이드오프예요.

• 인접 행렬(adjacency matrix): n×n 표를 만들어 "i와 j가 연결됐나"를 0/1로 적습니다. 두 정점의 연결 여부를 O(1) 에 확인하지만, 정점이 많아지면 공간을 O(n²) 으로 잡아먹어요. 연결이 빽빽한(밀집) 그래프에 어울립니다.
• 인접 리스트(adjacency list): 각 정점이 "내 이웃 목록"만 들고 있습니다. 공간을 실제 간선 수만큼만 써서 효율적이지만, 두 정점의 연결 확인은 목록을 훑어야 해요. 연결이 듬성듬성한(희소) 그래프에 어울립니다.

   인접 리스트로 위 그래프를 저장하면 (각 정점이 이웃 목록을 든다)

     A → B, C
     B → A, D
     C → A, D
     D → B, C

대부분의 현실 그래프(친구 관계, 도로망)는 정점에 비해 간선이 듬성듬성해서, 실무에서는 인접 리스트를 더 많이 씁니다. 그래프를 따라 도는 방법(너비 우선 BFS·깊이 우선 DFS)이나 최단 경로(다익스트라) 같은 알고리즘은 data-structures-algorithms 과목에서 직접 구현하며 깊게 다뤄요. 여기서는 "그래프는 정점과 간선이고, 저장은 행렬과 리스트의 트레이드오프"까지 답할 수 있으면 면접에서는 충분합니다.

🎯 면접에서는 이렇게 답하세요

"그래프는 정점(대상)과 간선(관계)으로 '누가 누구와 이어져 있나'를 표현해요. 친구 관계, 지하철 노선, 페이지 링크가 대표적이죠. 방향·가중치 유무로 종류가 갈리고요. 저장은 두 가지 트레이드오프인데 — 인접 행렬은 연결 확인이 O(1)이지만 공간을 O(n²) 쓰고, 인접 리스트는 공간을 간선 수만큼만 쓰지만 확인은 목록을 훑어야 해요. 그래서 빽빽하면 행렬, 듬성듬성하면 리스트를 쓰고, 현실 그래프는 대개 희소해서 인접 리스트를 많이 씁니다."

Step 8: "복잡도 표 총정리 — 자료구조·정렬을 한눈에"

오늘 본 자료구조를 연산 복잡도 표 하나로 묶겠습니다. 면접에서 "이 자료구조의 조회는 몇이고 삽입은 몇이냐"를 물으면 이 표가 머릿속에 있어야 해요. 외우라는 게 아니라, 지금까지 본 "왜 이 복잡도인가" 의 결론을 한 판에 정리하는 겁니다.

(* 해시는 평균 기준. 충돌이 몰리면 최악 O(n).)

이 표를 읽는 법은 "무슨 연산이 잦은가"로 자료구조를 고르는 거예요. 인덱스 접근이 잦으면 배열, 중간 삽입·삭제가 잦으면 연결 리스트, 정확한 키 조회가 잦으면 해시, 정렬·범위가 필요하면 트리 — 이게 면접에서 "왜 이 자료구조를 썼냐"에 답하는 틀입니다.

이제 정렬 복잡도 표를 봅니다. 정렬은 코딩 테스트와 면접에 자주 나오는데, 우리는 구현하지 않고 "어떤 정렬이 왜 이 복잡도인가"만 표로 잡을게요. 구현과 손으로 풀기는 data-structures-algorithms의 몫입니다.

표에서 두 가지만 읽어내면 됩니다. 첫째, 단순한 정렬(버블·선택·삽입)은 O(n²) 이고 분할정복 정렬(병합·힙·퀵 평균)은 O(n log n) 이에요. Step 2에서 본 그 5만 배 차이가 여기서 갈립니다. 데이터가 크면 반드시 O(n log n)짜리를 써야 해요. 둘째, 퀵 정렬은 평균은 가장 빠르지만 최악이 O(n²) 라는 함정이 있어요(피벗 선택이 나쁠 때). 그래서 "평균 빠른 퀵 vs 최악도 보장되는 병합·힙"의 트레이드오프가 면접 포인트입니다.

여기 두 단어를 짚고 갈게요. 안정성(stability)은 "같은 값의 원래 순서가 정렬 후에도 유지되는가"예요(이름순 정렬 후 점수순 정렬에서 중요). 제자리 정렬(in-place)은 "추가 메모리를 거의 안 쓰고 정렬하는가"고요. 병합 정렬은 안정적이지만 추가 공간 O(n)이 들고, 힙 정렬은 제자리지만 불안정한 — 여기도 트레이드오프죠. 결국 정렬조차 "무조건 좋은 하나"는 없고 상황에 맞는 선택입니다.

🎯 면접에서는 이렇게 답하세요

"자료구조는 잦은 연산으로 고릅니다 — 인덱스 접근이면 배열(O(1)), 중간 삽입·삭제면 연결 리스트(O(1)), 정확한 키 조회면 해시(평균 O(1)), 정렬·범위면 트리(O(log n))예요. 정렬은 단순한 버블·선택·삽입이 O(n²), 분할정복인 병합·힙·퀵 평균이 O(n log n) 이라, 데이터가 크면 후자를 씁니다. 다만 퀵은 평균 최고지만 최악이 O(n²), 병합은 안정적이나 추가 공간이 들고, 힙은 제자리지만 불안정해요. 정렬도 우열이 아니라 안정성·공간·최악 보장의 트레이드오프로 고르는 겁니다."

마무리

오늘은 "빠르기를 어떻게 재고, 자료구조를 어떻게 고르는가"를 면접 앵글로 훑었습니다. 지난 시간 인덱스에서 만난 트리와 O(log n)이, 오늘 자료구조 전반으로 펼쳐졌어요. 세 가지만 또렷이 들고 가세요.

오늘 배운 핵심 세 가지

🎯 하나 — 빠르기는 빅오(증가율)로 잰다. 실행 시간을 초로 재면 기계와 입력에 휘둘리니, 입력 n이 커질 때 연산이 늘어나는 속도로 잽니다. 상수·계수를 버리고 최고차항만 남겨 O(1) < O(log n) < O(n) < O(n log n) < O(n²) 로 비교하고, 보통 최악을 기준으로 잡아요. n이 100만일 때 O(n log n)과 O(n²)은 5만 배 차이라, 데이터가 커질 코드일수록 빅오를 봐야 합니다.

🎯 둘 — 자료구조는 연산별 트레이드오프로 고른다. 배열은 임의 접근 O(1)·중간 변경 O(n), 연결 리스트는 그 반대예요. 스택(LIFO)은 호출 스택·되돌리기, 큐(FIFO)는 대기열·BFS에 씁니다. 해시는 평균 O(1)이지만 충돌이 몰리면 O(n)이고 순서가 없어요. BST는 O(log n)이되 균형이 무너지면 O(n)이라 균형 트리(B+트리 등)를 쓰고, 힙은 최대/최소만 빠른 우선순위 큐죠. "무조건 좋은 하나"는 없습니다.

🎯 셋 — 정렬도 우열이 아니라 선택이다. 단순한 버블·선택·삽입은 O(n²), 분할정복 병합·힙·퀵 평균은 O(n log n) 이에요. 퀵은 평균 최고지만 최악 O(n²), 병합은 안정적이나 추가 공간, 힙은 제자리지만 불안정 — 안정성·공간·최악 보장의 트레이드오프로 고릅니다. 면접에서 "왜 이걸 썼냐"에 우열이 아니라 트레이드오프로 답하면 한 수 위로 보여요.

다음 시간 예고

다음 시간(E-1)은 이 과목의 마지막, CS 기술 면접 종합입니다. 우리는 그동안 네 기둥을 세웠어요. 컴퓨터 구조(A)·운영체제(B)·네트워크(C), 그리고 오늘로 완성된 데이터와 자료구조(D)죠. 다음 시간엔 이 넷을 따로가 아니라 한 줄기로 엮습니다. "URL을 치면 일어나는 일" 하나의 시나리오 안에 네 기둥이 전부 들어 있거든요. DNS·TCP(네트워크), 서버 프로세스·스레드(운영체제), CPU·캐시(컴퓨터 구조), DB 조회·인덱스(데이터)처럼요. 면접관이 "왜?"를 세 번 파고드는 꼬리 질문을 던질 때, 기둥을 넘나들며 답하는 법을 연습합니다. 모르는 질문을 만났을 때의 대처법, 내 프로젝트와 CS 지식을 잇는 법까지 — 면접장에 들고 들어갈 마지막 정리예요.

과제

[기초] 빅오 5종을 실제 연산에 매핑하고 체감하기

O(1)·O(log n)·O(n)·O(n log n)·O(n²) 다섯 가지를 각각 오늘 배운 실제 연산 하나씩에 연결해 보세요(예: O(1)은 배열 인덱스 접근). 그런 다음, 입력이 n=1,000개일 때와 n=100만 개일 때 각 복잡도의 연산 횟수가 대략 얼마인지 적고, "데이터가 1,000배 늘면 O(n²)는 몇 배가 되는가"를 계산해 보세요. 마지막으로 "빅오가 같으면 항상 같은 속도인가"에 한두 문장으로 답해 보세요(상수·계수·캐시를 떠올리면서).

[응용] 자료구조를 시나리오로 고르기

다음 세 상황에 어떤 자료구조를 쓸지 이유(트레이드오프)와 함께 고르세요. (1) 사용자 ID로 프로필을 즉시 조회하는 일이 대부분인 캐시. (2) 실행 취소(Ctrl+Z)를 구현해야 하는 에디터. (3) 응급실에서 위급도가 높은 환자부터 진료하는 대기 시스템. 각각에 대해 "왜 이 자료구조이고, 다른 후보는 왜 아닌지"를 한 문단으로 적어 보세요. (구현 코드는 쓰지 말고 개념으로만 답하세요.)

[심화] 해시 충돌을 진단하고, "왜 해시가 아니라 트리인가"에 답하기

(1) "사용자 데이터를 해시 테이블에 넣었는데, 어느 순간부터 조회가 O(n)처럼 느려졌다"는 상황입니다. 무엇이 원인일 수 있고(충돌·나쁜 해시·높은 부하율), 어떻게 진단·해결할지 적어 보세요. (2) 지난 시간 데이터베이스 인덱스는 해시가 아니라 B+트리를 쓴다고 했습니다. "정확히 한 값 찾기" 와 "범위 검색·정렬" 의 관점에서, 왜 DB 인덱스가 평균 O(1)인 해시 대신 O(log n)인 트리를 택하는지 트레이드오프로 설명해 보세요. (3) 그럼에도 해시가 트리보다 나은 상황은 무엇인지 한 가지 적어 보세요.

생각해볼 주제

1. 빅오가 작다고 항상 빠른 걸까

빅오는 "데이터가 아주 커졌을 때"의 증가율을 봅니다. 그런데 실무 데이터가 항상 큰 건 아니에요. n이 10개뿐인 목록을 다룰 때, O(n²)짜리 단순한 코드가 O(n log n)짜리 복잡한 코드보다 빠를 수 있습니다(상수와 계수가 작으니까). 또 같은 O(n)이라도 캐시 지역성이 좋은 배열이 연결 리스트보다 훨씬 빠르고요. "빅오가 작은 게 무조건 정답"이라는 판단의 함정을, 입력 크기·상수·캐시를 함께 놓고 생각해 보세요. "큰 그림을 보는 빅오"와 "실제로 재보는 벤치마크"가 어떻게 역할을 나누는지도요.

2. "더 복잡하고 똑똑한 자료구조가 더 좋다"는 함정

해시 테이블은 평균 O(1)이고, 균형 트리는 O(log n)을 보장하며, 둘 다 단순한 배열(O(n) 탐색)보다 "똑똑"합니다. 그렇다면 "이왕이면 늘 똑똑한 자료구조를 쓰자"는 판단은 옳을까요? 데이터가 작을 때의 오버헤드, 구현·유지보수의 복잡도, 순서가 사라지는 해시의 약점을 함께 생각해 보세요. 지난 시간 SQL과 NoSQL에서 했던 "더 새것·더 복잡한 게 더 나은 선택과 같은 말은 아니다"라는 사고가, 자료구조 선택에도 똑같이 적용됩니다. 도구는 우열이 아니라 트레이드오프라는 관점에서요.

3. 면접에서 "이 자료구조 왜 썼어요?"에 어떻게 답할까

면접관이 여러분의 프로젝트 코드를 보며 "여기서 왜 HashMap을 썼어요?", "왜 리스트를 썼죠?"라고 묻는다면, 어떻게 답하는 게 좋을까요? "그냥 익숙해서요"와 "정확한 키로 즉시 조회하는 일이 대부분이라 평균 O(1)인 해시가 맞다고 봤어요"는 천지 차이입니다. 후자처럼 답하려면, 내가 쓴 자료구조의 연산 복잡도와 트레이드오프를 알고 있어야 해요. 여러분이 최근에 작성한 코드에서 자료구조를 하나 골라, "왜 그걸 썼는지, 다른 후보는 왜 아니었는지"를 트레이드오프로 설명하는 연습을 해 보세요. 이게 오늘 배운 모든 것을 면접장에서 쓰는 방법입니다.