자료구조/알고리즘 리드·아키텍트 기술면접
새 면접Q. B-Tree와 B+Tree는 데이터베이스 인덱스 구조로 널리 사용됩니다. 두 자료구조의 핵심 차이점과 각각의 성능 특성을 설명하고, OLTP와 OLAP 워크로드에서 어떤 구조가 더 적합한지 이유와 함께 설명해주세요. 또한 실제 프로덕션 환경에서 B+Tree의 노드 크기를 결정할 때 고려해야 할 요소들을 제시해주세요.
리프 노드의 데이터 저장 방식과 범위 스캔 성능, 디스크 I/O 특성을 중심으로 생각해보세요.
B-Tree는 모든 노드에 데이터를 저장하지만, B+Tree는 리프 노드에만 데이터를 저장하고 내부 노드는 키만 가집니다. B+Tree의 리프 노드는 연결 리스트로 연결되어 있어 범위 스캔(range scan)이 매우 효율적입니다. OLTP 환경에서는 포인트 쿼리와 범위 쿼리가 혼재되므로 B+Tree가 적합하며, OLAP의 대량 스캔에서도 순차 접근이 유리한 B+Tree가 선호됩니다. 노드 크기는 디스크 페이지 크기(보통 4KB~16KB), 캐시 효율성, 트리 높이와 I/O 횟수의 트레이드오프를 고려해 결정해야 합니다. 일반적으로 SSD 환경에서는 작은 노드, HDD 환경에서는 큰 노드가 유리하며, 메모리 버퍼 풀 크기와 워킹셋도 함께 고려해야 합니다.
- • B+Tree는 리프 노드에만 데이터 저장, 내부 노드는 키만 보유
- • 리프 노드 간 연결 리스트로 범위 스캔 최적화
- • 노드 크기는 디스크 페이지, 캐시, I/O 특성을 고려해 결정
- • OLTP/OLAP 모두 B+Tree가 범위 쿼리에 유리
RDBMS 인덱스 설계 시 테이블 크기와 쿼리 패턴에 따라 인덱스 구조와 페이지 크기를 조정할 때 활용됩니다.
MySQL InnoDB의 클러스터드 인덱스와 세컨더리 인덱스에서 B+Tree가 어떻게 다르게 활용되는지 설명해주세요.
Q. 수백 GB 규모의 외부 정렬(External Sort)을 수행해야 하는데, 메모리는 수 GB로 제한되어 있습니다. External Merge Sort의 동작 원리와 K-way Merge 단계에서 최적의 K 값을 결정하는 방법을 설명해주세요. 또한 디스크 I/O를 최소화하기 위한 버퍼링 전략과, SSD와 HDD 환경에서 전략이 어떻게 달라져야 하는지 설명해주세요.
Run 생성 단계와 병합 단계를 나누어 생각하고, 디스크 seek time과 sequential I/O의 차이를 고려해보세요.
External Merge Sort는 먼저 메모리에 적재 가능한 크기로 데이터를 나누어 정렬한 Run을 생성하고, 이를 K-way Merge로 병합합니다. 최적의 K는 메모리 크기와 I/O 비용의 균형으로 결정되며, K가 클수록 병합 패스 수는 줄지만 각 Run당 버퍼가 작아져 I/O 횟수가 증가합니다. 일반적으로 K = M/B (M은 메모리, B는 블록 크기)로 설정하되, 힙 자료구조로 K개 원소 중 최소값을 찾는 오버헤드도 고려해야 합니다. HDD 환경에서는 seek time이 크므로 큰 버퍼로 sequential I/O를 최대화하고, SSD에서는 random I/O 비용이 낮아 더 작은 버퍼와 큰 K 값이 효율적입니다. Double buffering이나 async I/O를 활용해 CPU와 I/O를 오버랩하는 것도 중요합니다.
- • Run 생성 후 K-way Merge로 병합하는 2단계 구조
- • 최적 K는 메모리 크기, 블록 크기, I/O 패턴의 균형
- • HDD는 sequential I/O 중심, SSD는 더 큰 K 값 가능
- • Double buffering과 async I/O로 CPU-I/O 오버랩
대용량 로그 분석이나 데이터 웨어하우스 ETL 과정에서 메모리보다 큰 데이터를 정렬할 때 사용됩니다.
Hadoop MapReduce의 Shuffle 단계에서 External Sort가 어떻게 분산 환경에 적용되는지 설명해주세요.
Q. HyperLogLog는 대규모 카디널리티 추정에 사용되는 확률적 자료구조입니다. Count-Min Sketch, Bloom Filter와 비교하여 HyperLogLog의 작동 원리와 오차율 특성을 설명하고, 각 자료구조가 적합한 사용 사례를 구분해주세요. 또한 Redis에서 HyperLogLog를 사용할 때 메모리 효율성과 정확도의 트레이드오프를 어떻게 조정할 수 있는지 설명해주세요.
각 자료구조가 해결하는 문제(존재 여부, 빈도 추정, 카디널리티 추정)와 공간 복잡도를 중심으로 비교해보세요.
Bloom Filter는 집합 멤버십 테스트(false positive 허용), Count-Min Sketch는 빈도 추정, HyperLogLog는 카디널리티(고유 원소 수) 추정에 특화되어 있습니다. HyperLogLog는 해시값의 leading zero 패턴을 이용해 확률적으로 카디널리티를 추정하며, 표준 오차는 1.04/√m (m은 버킷 수)입니다. 12KB 메모리로 10억 개 원소의 카디널리티를 약 0.81% 오차로 추정할 수 있어 매우 효율적입니다. Redis의 HyperLogLog는 기본 12KB를 사용하며, 정확도를 높이려면 더 많은 레지스터를 사용해야 하지만 실무에서는 기본값이 대부분 충분합니다. 실시간 UV 집계, 고유 IP 카운팅, A/B 테스트 사용자 수 추정 등에 활용되며, 정확한 값이 필요하면 기존 Set 자료구조를 사용해야 합니다.
- • HyperLogLog는 카디널리티 추정 전용, 오차 1.04/√m
- • Bloom Filter는 멤버십, Count-Min Sketch는 빈도 추정
- • 12KB로 10억 원소를 0.81% 오차로 추정 가능
- • 정확도-메모리 트레이드오프는 레지스터 수로 조정
실시간 대시보드에서 일간 순 방문자 수(DAU)를 메모리 효율적으로 집계할 때 사용됩니다.
여러 서버에 분산된 HyperLogLog 데이터를 병합하여 전체 카디널리티를 구하는 방법을 설명해주세요.
Q. Trie, Suffix Tree, Suffix Array는 모두 문자열 검색에 사용되는 자료구조입니다. 각각의 공간 복잡도와 시간 복잡도를 비교하고, 자동완성 기능, 부분 문자열 검색, DNA 서열 분석과 같은 실무 시나리오에서 어떤 자료구조를 선택해야 하는지 이유와 함께 설명해주세요. 또한 대용량 텍스트에서 메모리 제약이 있을 때의 최적화 전략도 제시해주세요.
각 자료구조의 구축 시간과 검색 시간, 그리고 메모리 사용량의 차이를 중심으로 생각해보세요.
Trie는 공통 접두사를 공유하여 O(m) 시간에 검색하지만 포인터 오버헤드로 메모리 사용량이 크며, 자동완성처럼 접두사 검색이 주된 경우에 적합합니다. Suffix Tree는 모든 부분 문자열을 O(m) 시간에 찾을 수 있지만 구축에 O(n) 시간과 공간이 필요해 메모리 집약적이며, DNA 서열의 최장 공통 부분 문자열 찾기 등에 사용됩니다. Suffix Array는 Suffix Tree의 공간 효율적 대안으로 O(n log n) 구축 후 이진 탐색으로 O(m log n) 검색이 가능하며, LCP 배열과 함께 사용하면 많은 문자열 문제를 해결할 수 있습니다. 대용량 텍스트에서는 Compressed Suffix Array나 FM-Index 같은 압축 자료구조를 사용하거나, Trie의 경우 Double-Array Trie로 메모리를 절약할 수 있습니다.
- • Trie는 접두사 검색에 최적, 메모리 오버헤드 큼
- • Suffix Tree는 모든 부분 문자열 검색 가능, 메모리 집약적
- • Suffix Array는 공간 효율적, LCP 배열과 조합
- • 압축 자료구조나 Double-Array로 메모리 최적화
검색 자동완성, 코드 에디터의 심볼 검색, 생물정보학의 게놈 분석 등에서 문자열 매칭 성능을 최적화할 때 사용됩니다.
검색 엔진에서 와일드카드 쿼리(예: *abc*def)를 효율적으로 처리하기 위한 자료구조 전략을 설명해주세요.
Q. 우선순위 큐를 구현하는 여러 힙 구조(Binary Heap, Binomial Heap, Fibonacci Heap, Pairing Heap) 중에서 실무 선택 기준을 설명해주세요. 특히 Decrease-Key 연산이 빈번한 Dijkstra 알고리즘 구현과, 실시간 스케줄링 시스템에서 각 힙의 성능 특성과 실용성을 비교하고, 이론적 복잡도와 실제 성능의 차이가 발생하는 이유를 설명해주세요.
Amortized 분석과 상수 계수, 캐시 지역성, 구현 복잡도를 함께 고려해보세요.
Binary Heap은 구현이 간단하고 캐시 친화적이어서 실무에서 가장 널리 사용되며, Insert와 Delete-Min이 O(log n)입니다. Fibonacci Heap은 Decrease-Key가 O(1) amortized로 이론적으로 우수하지만, 복잡한 포인터 구조로 상수 계수가 크고 캐시 미스가 많아 실제로는 느릴 수 있습니다. Dijkstra 알고리즘에서는 그래프가 매우 클 때만 Fibonacci Heap이 유리하며, 일반적 규모에서는 Binary Heap이나 4-ary Heap이 더 빠릅니다. Pairing Heap은 Fibonacci Heap보다 구현이 단순하면서 실무 성능이 좋아 절충안으로 선택됩니다. 실시간 스케줄링에서는 예측 가능한 worst-case 성능이 중요하므로 Binary Heap이나 Red-Black Tree 기반 우선순위 큐가 선호됩니다. 이론적 복잡도와 실제 성능 차이는 캐시 지역성, 분기 예측, 메모리 할당 오버헤드 등 하드웨어 특성 때문입니다.
- • Binary Heap이 구현 단순성과 캐시 지역성으로 실무 표준
- • Fibonacci Heap은 이론적 우수성에도 상수 계수와 캐시 미스 문제
- • Pairing Heap은 단순성과 성능의 절충안
- • 실시간 시스템은 worst-case 성능과 예측 가능성 중요
작업 스케줄러, 이벤트 시뮬레이션, 최단 경로 알고리즘 등에서 우선순위 큐 구현체를 선택할 때 성능 특성을 고려합니다.
Java의 PriorityQueue와 C++ STL의 priority_queue가 어떤 힙 구조를 사용하며, 커스텀 비교자를 사용할 때 주의할 점은 무엇인가요?
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!