자료구조 및 알고리즘 면접 예상 문제 + 정리

Hyunjun Kim·2025년 6월 20일

Computer_Science

목록 보기

7/19

자료구조 및 알고리즘 핵심 개념 통합 정리 (데이터 엔지니어 관점)

1. B+Tree 인덱스 (MySQL InnoDB 기준)

구조:
- B+Tree는 균형 잡힌 다방향 트리이며, 모든 실제 데이터(키+레코드)는 Leaf Node에 저장된다.
- 내부 노드는 탐색용 키만 포함하고, Leaf 노드는 링크드 리스트로 연결되어 있어 범위 검색에 매우 효율적이다.
- InnoDB의 클러스터드 인덱스는 기본 키를 기준으로 정렬된 B+Tree이며, 보조 인덱스는 기본 키를 포함하는 B+Tree 구조이다.
시간복잡도:
- 탐색, 삽입, 삭제 모두 평균적으로 O(logₘ N) (m: 노드 분기수, N: 키 개수)
- 범위 검색은 O(logₘ N + K) (K: 반환된 결과 개수)
변경 비용 (INSERT/DELETE 시):
- Leaf 노드가 가득 차면 페이지 분할(Split) 발생, 이로 인해 부모 노드 및 상위 노드 갱신 필요
- 삭제 시 페이지가 너무 비면 병합(Merge) 또는 재분배(Redistribute) 발생
- 이 과정에서 디스크 I/O와 버퍼풀 갱신 부담이 증가하여 성능 저하를 유발함
트레이드오프:
- 읽기 및 범위 검색에 매우 효율적이나, 빈번한 쓰기 작업(INSERT/DELETE) 시 구조 재조정 비용 발생
- 높은 쓰기 부하에는 LSM-Tree 기반 스토리지(RocksDB, LevelDB 등) 고려
면접 질문 예시:

MySQL InnoDB에서 B+Tree 인덱스의 페이지 분할이 발생하는 상황과 그에 따른 성능 영향은 무엇인가?
답변 예시

페이지 분할은 B+Tree의 Leaf 노드가 꽉 찼을 때 발생합니다. 새로운 키를 삽입해야 하는데 기존 페이지에 공간이 부족하면, 그 페이지를 두 개로 나누고 키들을 재배치합니다. 이 과정에서 부모 노드에도 새로운 키가 삽입되거나 갱신되어야 하므로 상위 노드까지 영향을 미칩니다.
이로 인해 디스크 I/O가 증가하고, 버퍼 풀 내 페이지 갱신 비용이 커져 인덱스 삽입 성능 저하가 나타납니다.
특히 빈번한 삽입/삭제 작업이 많은 OLTP 환경에서는 이러한 분할과 병합이 잦아져 성능 저하가 심화됩니다.
따라서 높은 쓰기 부하가 예상되면 B+Tree 인덱스 외에 LSM-Tree 기반 스토리지(예: RocksDB)를 고려하는 것이 바람직합니다.

2. Array와 Linked List

구분	Array	Linked List
접근 방식	랜덤 액세스 (O(1))	순차 탐색 (O(n))
저장 방식	인접한 메모리 위치에 연속 저장	각 노드가 다음 노드 주소 저장
삽입/삭제	중간에 삽입/삭제 시 요소 이동 필요 (O(n))	포인터 조작만으로 삽입/삭제 가능 (O(1))
메모리 할당	정적 또는 동적 연속 메모리 할당	동적 메모리 할당 (비연속적)
메모리 위치	Stack 또는 Heap (언어/환경에 따라 다름)	Heap

Array 특징
- 인덱스 기반 직접 접근 가능 → 검색 빠름 (O(1))
- 중간 삽입/삭제 시 비용 큼 (O(n))
- 크기 변경이 어려움 (동적 배열 제외)
Linked List 특징
- 삽입/삭제 시 포인터 변경만으로 가능 → 빠름 (O(1))
- 특정 위치 접근 시 순차 탐색 필요 → 느림 (O(n))
- 크기 변경 유연, 메모리 분산적
면접 질문 예시:

데이터 엔지니어링 파이프라인에서 대용량 데이터 처리 시 Array 대신 Linked List를 선택하는 경우는 언제인가?
답변 예시

대용량 데이터 처리 시, 연속적인 메모리 할당과 랜덤 접근이 필요한 경우 Array가 적합합니다.
그러나 데이터가 동적으로 빈번하게 삽입·삭제되거나 크기를 미리 알기 어려운 상황이라면 Linked List가 유리합니다.
특히, 메모리 단편화가 심한 환경이나 리스트 중간에 삽입/삭제가 많을 때 Linked List는 포인터 조작만으로 연산이 가능해 효율적입니다.
단, 랜덤 접근이 불가능해 순차 탐색이 필요하므로 접근 속도는 느릴 수 있습니다.

3. List와 Set

List
- 순서 유지
- 중복 허용
Set
- 순서 보장 안 함 (언어별 구현 차이 있음)
- 중복 불허 (고유 데이터만 저장)
실무 활용
- 중복 데이터가 있을 수 있으나 결과 집합은 중복 제거가 필요할 때 Set 활용
- 예: 사용자 ID 중복 제거, 완료된 작업 집합 등
면접 질문 예시:

데이터 처리 중 중복 데이터 제거가 필요한 상황에서 List와 Set 중 어떤 자료구조를 선택하는 것이 효율적인가?
답변 예시

중복 제거가 목적이라면 Set을 사용하는 것이 일반적으로 효율적입니다.
Set은 내부적으로 해시 테이블이나 트리를 사용해 중복을 허용하지 않으므로, 데이터가 추가될 때 중복 검사 비용이 상대적으로 낮습니다.
반면, List는 중복을 허용하기 때문에 중복 제거를 위해 별도의 탐색이나 정렬, 집합 연산이 필요해 비용이 더 큽니다.
따라서, 대량 데이터에서 중복을 빠르게 제거할 때는 Set이 더 적합합니다.

4. Stack과 Queue

구분	Stack	Queue
자료구조 특성	후입선출 (LIFO)	선입선출 (FIFO)
삽입/삭제 위치	한쪽 끝 (top)	삽입: 한쪽 끝, 삭제: 반대쪽 끝
사용 예시	DFS, 함수 호출 스택, 역추적 알고리즘	BFS, 작업 스케줄링, 메시지 큐

Stack
- 가장 나중에 들어온 데이터가 가장 먼저 나감
- 구현: 배열, 연결 리스트 등
- 용도: 함수 호출 관리, 깊이 우선 탐색 등
Queue
- 가장 먼저 들어온 데이터가 가장 먼저 나감
- 구현: 배열, 연결 리스트 등
- 용도: 작업 처리 순서 관리, 너비 우선 탐색, 메시지 큐
면접 질문 예시:

데이터 스트림 처리 시 Stack과 Queue 중 어떤 자료구조를 사용하는 것이 적합한가? 그 이유는?
답변 예시

데이터 스트림 처리에서 처리 순서가 들어온 순서대로 유지되어야 한다면 Queue가 적합합니다. Queue는 선입선출(FIFO) 구조로, 먼저 들어온 데이터가 먼저 처리됩니다.
반면, Stack은 후입선출(LIFO)이므로 최근 데이터가 먼저 처리되어 순서 유지가 필요한 스트림 처리에는 부적합합니다.
예를 들어, 로그 처리, 메시지 큐, 이벤트 처리 등에서는 Queue를 주로 사용합니다.

5. Priority Queue (우선순위 큐)

우선순위가 높은 데이터를 먼저 처리하기 위한 자료구조
일반적으로 힙(Heap) 으로 구현 (최대힙 또는 최소힙)
삽입과 삭제 연산 모두 O(log n) 시간복잡도 보장
분산 시스템 작업 스케줄링, 이벤트 시뮬레이션 등에서 활용
면접 질문 예시:

데이터 파이프라인에서 작업 우선순위를 정할 때 Priority Queue를 어떻게 활용할 수 있나?
답변 예시

Priority Queue는 우선순위가 높은 작업을 먼저 처리하도록 보장하는 자료구조입니다.
데이터 파이프라인에서 긴급도, 중요도, 처리 비용 등을 기준으로 작업을 우선순위화하고, Priority Queue에 넣으면 높은 우선순위 작업이 먼저 처리됩니다.
이로써 처리 지연을 최소화하고 시스템 효율성을 높일 수 있습니다.
예를 들어, 스트림 처리에서 이벤트 중요도별 차등 처리, 작업 스케줄러에서 우선순위 기반 작업 분배 등에 활용됩니다.

6. 트리 구조

6.1 Binary Tree & Binary Search Tree (BST)

Binary Tree: 최대 두 개의 자식을 가지는 트리
BST: 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 큰 값을 가짐
탐색, 삽입, 삭제 시간복잡도는 트리 높이 h에 따라 O(h)
한쪽으로 치우친 경우 최악 O(n)까지 늘어날 수 있음

6.2 Red-Black Tree (RBT)

BST의 균형 문제를 해결한 자기 균형 이진 탐색 트리
각 노드는 빨강 또는 검정 색상을 가짐
삽입, 삭제 시 색 변경과 회전을 통해 균형 유지
탐색, 삽입, 삭제 모두 O(log n) 시간복잡도 보장
면접 질문 예시:

Red-Black Tree가 일반 BST에 비해 데이터 엔지니어링에서 왜 선호되는가?
답변 예시

Red-Black Tree는 삽입과 삭제 시 자동으로 균형을 유지해 트리 높이를 O(log n) 수준으로 보장합니다.
일반 BST는 한쪽으로 치우칠 경우 최악 O(n)까지 탐색 시간이 늘어나지만, Red-Black Tree는 항상 균형을 유지해 성능 저하를 방지합니다.
데이터 엔지니어링에서 대용량 인덱싱, 정렬, 검색 작업을 수행할 때 일관된 성능을 제공하는 것이 매우 중요하기 때문에 Red-Black Tree가 선호됩니다.

7. 해시 테이블 (Hash Table)

Key-Value 쌍으로 데이터를 저장하는 자료구조
해시 함수를 이용해 Key를 배열 인덱스로 변환
평균 조회, 삽입, 삭제 시간복잡도 O(1)
충돌 해결 방법: 체이닝(Chaining), 오픈 어드레싱(Open addressing)
최악 경우 시간복잡도는 O(n)까지 증가 가능

7.1 HashMap vs HashTable (Java 기준)

구분	HashMap	HashTable
동기화	비동기 (동기화 지원 안 함)	동기화 (Thread-safe)
null 허용	Key, Value 모두 null 허용	Key, Value 모두 null 불허

멀티스레드 환경에서는 동기화된 HashTable 사용 권장
단일 스레드 또는 동기화 불필요 시 HashMap 사용
면접 질문 예시:

대용량 로그 데이터 처리 시 해시 테이블 충돌이 성능에 미치는 영향과 이를 완화하는 방법은?
답변 예시

해시 테이블에서 충돌이 발생하면 같은 버킷에 여러 키가 저장되어 검색, 삽입, 삭제 시 추가 탐색 비용이 발생해 평균 O(1) 성능이 저하되고 최악 O(n)까지 늘어날 수 있습니다.
이를 완화하기 위해서는 좋은 해시 함수 선택으로 키 분포를 균등하게 하고, 체이닝(Linked List, 트리 구조 사용)이나 오픈 어드레싱(선형 탐사, 이중 해싱 등) 방법을 사용합니다.
또한, 적절한 버킷 크기 및 동적 리사이징으로 충돌 확률을 낮추는 전략도 중요합니다.
분산 환경에서는 해시 샤딩을 통해 부하를 분산하기도 합니다.

참고: 알고리즘 시간복잡도 (주요 예시)

자료구조/알고리즘	탐색	삽입/삭제
배열 (정렬 안 됨)	O(n)	O(1) / O(n)
배열 (정렬됨)	O(log n)	O(n)
해시 테이블	O(1) 평균, O(n) 최악	O(1) 평균
이진 탐색 트리 (BST)	O(log n) 평균	O(log n) 평균
AVL, Red-Black Tree	O(log n)	O(log n)
B-Tree / B+Tree	O(logₘ n)	O(logₘ n)
Trie	O(k) (문자열 길이)	O(k)