자료구조·알고리즘 — 백엔드 면접 (실제 기출 기반·심화)

네카라쿠배당토 백엔드 면접에서 자료구조는 코딩테스트와 별개로 구술로 묻는다. "배열과 링크드리스트 차이", "해시 충돌 처리", "BST 최악의 경우", "퀵소트가 O(N²)이 되는 경우", "LRU를 어떻게 구현하나" — 단골이고, 면접관은 정의 → 왜 → 트레이드오프 → 구현으로 계단식으로 파고든다(VSFe 패턴).

"스택과 큐를 설명해주세요"에서 끝나지 않고 "언제 큐를 쓰고 언제 스택을 쓰나요?"(실사용 맥락)로 간다. 정의 암기로는 못 막는다.

---

1. 복잡도 — Big-O와 함정 (★ 단골)

실제 질문: "Big-O, Big-Θ, Big-Ω를 설명하고 왜 보통 Big-O만 쓰나요?" · "O(1)이 O(N²)보다 항상 빠른가요?" (VSFe·ksundong)

• Big-O(상한·최악), Big-Ω(하한·최선), Big-Θ(상하한 일치). 실무는 최악 보장이 중요해 Big-O를 쓴다.
• ⚠️ 함정 — "O(1) < O(N²) 항상?": 거짓. Big-O는 상수 인자와 작은 N을 무시한 점근적 표현 → 상수가 크거나 N이 작으면 역전된다.

꼬리질문: "이 코드의 시간복잡도는?" → 중첩 루프·재귀 점화식으로 계산. / "공간복잡도도 보나?" → 재귀 깊이·추가 배열 고려.

함정: ❌ "Big-O가 실제 실행시간이다" → 증가율이지 절대 속도가 아니다.

---

2. 배열 vs 링크드리스트 (★★ 최다 단골)

실제 질문: "배열과 링크드리스트의 차이를 설명해주세요." · "링크드리스트로 구현 가능한 자료구조는?"(스택/큐/덱) (gyoogle·ksundong)

깊이: "삽입/삭제 O(1)"은 그 위치의 노드를 이미 가리킬 때다. 탐색 포함이면 O(N). 실무에선 캐시 지역성 때문에 배열(ArrayList)이 링크드리스트보다 빠른 경우가 많다.

꼬리질문: "언제 링크드리스트?" → 중간 삽입/삭제가 빈번하고 임의 접근이 드물 때(큐·LRU). / "Java ArrayList vs LinkedList 실무 선택?" → 대부분 ArrayList(지역성). / "배열의 중복 제거는?" → Set/해시 O(N).

함정: ❌ "링크드리스트가 항상 삽입이 빠르다" → 위치 탐색이 O(N)이면 무의미.

---

3. 해시 — 충돌과 해결 (★★ 단골)

실제 질문: "Hash Function, HashTable을 설명해주세요." · "해시 충돌을 어떻게 처리하나요?" · "Load Factor가 무엇인가요?" · "멀티스레드 환경에서 해시의 Race Condition을 어떻게 해결하나요?" (gyoogle·VSFe·ksundong)

해시 함수로 키를 버킷 인덱스에 매핑 → 평균 O(1) 조회. 서로 다른 키가 같은 버킷이면 충돌:

• Load Factor = 저장 수 / 버킷 수. 임계(보통 0.75) 초과 시 rehashing(버킷 2배 확장 + 재배치) → 일시적 O(N).
• Race Condition: 여러 스레드가 동시에 put/resize → 손상·무한루프(Java7 이전) → ConcurrentHashMap(Java7=Segment 분할 락 기본 16, Java8+=버킷 head synchronized + CAS 무락 삽입).

꼬리질문: "체이닝 vs 개방주소법 트레이드오프?" → 체이닝은 포인터 메모리·캐시 미스, 개방주소법은 클러스터링·삭제 시 tombstone. / "HashMap이 최악 O(N)인 경우?" → 충돌이 한 버킷에 몰림(Java8은 트리화로 O(log N)). / "double hashing 장점?" → 2차 해시로 클러스터링 완화.

함정: ❌ "HashMap은 항상 O(1)" → 충돌 누적·rehashing 무시. ❌ "해시 = 암호화" → 단방향 인덱싱.

---

4. 스택·큐·덱 (★ 단골·구현)

실제 질문: "Stack, Queue를 설명하고 언제 각각 쓰나요?" · "스택 2개로 큐 만들기 / 큐 2개로 스택 만들기" (VSFe·yukina 후기)

• 스택(LIFO): 함수 호출(콜스택)·DFS·되돌리기(undo)·괄호 검사·수식 파싱.
• 큐(FIFO): BFS·작업 큐·요청 버퍼·메시지 큐.
• 덱(Deque): 양끝 삽입/삭제(슬라이딩 윈도우·LRU).

깊이 — 스택 2개로 큐: in 스택에 push, dequeue할 때 out이 비면 in을 전부 옮겨 뒤집음 → amortized O(1). "재귀(스택)를 큐로 바꾸면 DFS→BFS"가 핵심 통찰.

꼬리질문: "재귀와 스택의 관계?" → 재귀는 콜스택을 쓰는 것 → 깊으면 StackOverflow → 명시적 스택으로 변환. / "BFS에 스택을 쓰면?" → DFS가 된다.

---

5. 트리·BST·균형 트리·힙 (★★ 단골)

실제 질문: "Tree, Binary Tree, BST, AVL Tree를 설명하라." · "BST의 최악의 경우 예시와 시간복잡도는?" · "Red-Black Tree는 어떻게 균형을 유지하나요?" (ksundong·VSFe)

• BST: 왼쪽 < 루트 < 오른쪽 → 탐색/삽입/삭제 평균 O(log N).
• ⚠️ BST 최악 = O(N)(★ 단골 꼬리): 정렬된 데이터를 순서대로 넣으면 *한쪽으로 편향(skewed)*돼 연결리스트가 됨 → 자가 균형 트리(AVL·Red-Black)로 해결.
• AVL vs Red-Black: AVL은 엄격한 균형(높이 차 ≤1·조회 빠름·회전 잦음), RB는 느슨한 균형(색칠 규칙·삽입/삭제 빠름) → Java TreeMap·HashMap 트리화는 RB.
• 힙(Heap): 완전 이진 트리·부모 ≥(또는 ≤) 자식 → 우선순위 큐·배열로 구현(1-기반: 부모 i/2, 자식 2i/2i+1 / 0-기반(코테 기본): 부모 (i-1)/2, 자식 2i+1/2i+2). 삽입/삭제 O(log N), 루트(최대/최소) O(1).

꼬리질문: "BST 최악을 어떻게 막나?" → 자가 균형(AVL/RB). / "RB 트리의 성질은?" → 루트/리프 검정·빨강 연속 금지·모든 경로 검정 수 동일 → 높이 균형. / "힙 정렬은 안정적인가?" → 불안정(O(N log N)·제자리).

함정: ❌ "BST는 항상 O(log N)" → 편향 시 O(N). ❌ "힙은 정렬된 자료구조" → 부분 순서(루트만 최대/최소).

---

6. 그래프 (★ 단골)

실제 질문: "그래프 구현 두 가지 방법과 각각의 시간복잡도는?" · "정점 N개, 간선이 많을 때 효율적인 구현은?" · "DFS, BFS를 설명하라." (VSFe·ksundong)

• 간선이 매우 많은(밀집) 그래프면 인접 행렬이 유리(존재 확인 O(1)).
• DFS(스택/재귀·경로·사이클·위상정렬)·BFS(큐·최단거리(무가중)·레벨 탐색).

꼬리질문: "최단경로는?" → 무가중 BFS·가중 다익스트라(음수 없음)·벨만포드(음수)·전체쌍 플로이드워셜. / "다익스트라가 음수 간선에서 깨지는 이유?" → 최단 확정한 노드를 음수 간선이 뒤늦게 더 줄일 수 있어 그리디 선택 속성이 깨짐 → 벨만포드. / "BFS가 무가중에서만 최단인 이유?" → 모든 간선 비용 1 가정 → 레벨 순서 = 거리 순서. / "DFS로 사이클 검출?" → 방문 중 노드를 다시 만나면 사이클.

---

7. 정렬 (★★ 단골)

실제 질문: "Quick Sort vs Merge Sort. Quick Sort가 O(N²)이 되는 경우는?" · "Stable Sort란?" · "언어 표준 정렬은 내부적으로 어떻게 구현돼 있나요?" (VSFe·ksundong)

• ⚠️ 퀵소트 O(N²): 피벗이 항상 최소/최대면(이미 정렬된 데이터에 첫/끝 피벗) 분할이 1:N-1로 편향 → O(N²). → 랜덤/중앙값 피벗으로 완화.
• Stable Sort: 같은 값의 원래 순서 유지. 다중 키 정렬(이름→나이)에 필요.
• 언어 표준(★ 꼬리): Java 원시타입=Dual-Pivot QuickSort, 객체=TimSort(머지+삽입·안정·실데이터 최적). C++ sort=Introsort(퀵+힙+삽입).

꼬리질문: "메모리 제약 시?" → 제자리 정렬(힙)·외부정렬(머지 기반). / "왜 Java 객체 정렬은 TimSort?" → 안정성 보장 + 실데이터의 부분 정렬 활용.

함정: ❌ "퀵소트가 항상 가장 빠르다" → 최악 O(N²)·불안정. ❌ "머지소트는 제자리 정렬" → O(N) 추가 메모리.

---

8. DP·그리디 (★ 단골)

실제 질문: "피보나치를 구현하고 설명하라." · "그리디와 동적계획법의 차이는?" (ksundong·VSFe)

재귀 fib(n) = fib(n-1)+fib(n-2)  → 중복 계산 O(2^N)
메모이제이션(top-down) / 타뷸레이션(bottom-up) → O(N)

• DP: 부분 문제 결과를 저장해 재사용(중복 부분 문제 + 최적 부분 구조). 메모이제이션(하향식) vs 타뷸레이션(상향식).
• 그리디: 매 단계 지역 최적을 선택. 그리디 선택 속성 + 최적 부분 구조가 성립할 때만 전역 최적(예: 다익스트라·MST). 동전·배낭은 조건에 따라 그리디 실패 → DP.

꼬리질문: "그리디가 틀리는 예?" → 동전 {1,3,4}로 6 만들기(그리디 4+1+1=3개, 최적 3+3=2개). / "LRU 캐시 구현?"(★ 단골) → 해시맵 + 이중 연결 리스트로 get/put O(1)(코딩테스트 직결).

---

흔한 오답·함정 정리 (면접관이 노리는 곳)

• O(1) > O(N²) 항상 → 상수·작은 N에서 역전.
• HashMap 항상 O(1) → 충돌·rehashing 시 저하.
• BST 항상 O(log N) → 편향 시 O(N) → 자가 균형 트리.
• 퀵소트가 항상 최고 → 최악 O(N²)·불안정.
• 해시 = 암호화 → 단방향 인덱싱(암호화 아님).

한국 면접 단골 Q&A (답변 골격)

꼬리질문 대비 (상 난이도)

• "왜 DB 인덱스는 해시가 아니라 B+트리?" → 해시는 등호만, 범위·정렬·부등호 불가 → B+트리(DB 편).
• "HashMap이 멀티스레드에서 깨진다?" → resize 중 race → ConcurrentHashMap.
• "퀵소트를 안정 정렬로?" → 기본 불가·인덱스를 보조 키로.
• "LRU vs LFU?" → 최근성(이중 연결 리스트) vs 빈도(카운트) — 캐시 편.
• "재귀가 깊으면?" → StackOverflow → 명시적 스택/반복으로.

한 줄 요약 — 복잡도는 Big-O(최악·O(1)>O(N²) 항상 아님). 배열(연속·O(1) 접근·캐시 지역성)↔링크드리스트(O(1) 삽입·위치 알 때). 해시는 충돌(체이닝/개방주소·load factor·rehashing·동시성). 스택(LIFO·DFS)↔큐(FIFO·BFS). BST 최악 O(N)(편향)→AVL/RB. 그래프 인접행렬(밀집)/리스트(희소)·DFS/BFS. 정렬 퀵(최악 O(N²)·불안정)↔머지(안정·O(N))·표준은 TimSort/Dual-Pivot. DP(중복 저장)↔그리디(지역 최적)·LRU=해시맵+이중 연결 리스트.

(출처 — 한국 면접 기출·교차검증 2026-06: VSFe/Tech-Interview — 자료구조·알고리즘·ksundong/backend-interview-question·gyoogle — Hash · CLRS(정렬·트리)·Java Arrays/TimSort 소스 교차검증.)