자료구조/알고리즘 미드레벨 기술면접
새 면접Q. 해시 테이블에서 충돌(Collision)이 발생했을 때 해결하는 주요 방법들과 각각의 장단점을 설명해주세요. 실무에서 어떤 상황에 어떤 방법을 선택하시겠습니까?
체이닝과 개방 주소법의 차이를 생각해보고, 각각의 메모리 사용 패턴과 성능 특성을 고려해보세요.
해시 충돌 해결 방법은 크게 체이닝(Chaining)과 개방 주소법(Open Addressing)으로 나뉩니다. 체이닝은 같은 해시값을 가진 항목들을 연결 리스트로 관리하며, 구현이 간단하고 테이블이 가득 차도 동작하지만 추가 메모리가 필요합니다. 개방 주소법은 충돌 시 다른 빈 슬롯을 찾아 저장하며(선형 탐사, 이차 탐사, 이중 해싱 등), 메모리 효율적이고 캐시 친화적이지만 클러스터링 문제가 발생할 수 있습니다. 실무에서는 데이터 크기를 예측하기 어렵고 삭제가 빈번한 경우 체이닝을, 메모리가 제한적이고 로드 팩터를 낮게 유지할 수 있다면 개방 주소법을 선택합니다. Java의 HashMap은 체이닝을 사용하며, 버킷당 항목이 많아지면 Red-Black Tree로 전환하여 최악의 경우를 O(log n)으로 개선합니다.
- • 체이닝은 연결 리스트로 충돌 관리, 구현 간단하나 추가 메모리 필요
- • 개방 주소법은 빈 슬롯 탐색, 메모리 효율적이나 클러스터링 발생 가능
- • 실무에서는 데이터 특성과 메모리 제약에 따라 선택
대용량 캐시 시스템이나 데이터베이스 인덱스 설계 시 충돌 해결 전략 선택이 전체 시스템 성능에 직접적인 영향을 미칩니다.
로드 팩터(Load Factor)가 0.75를 넘어가면 리해싱(Rehashing)을 하는 이유와, 리해싱 과정에서 발생할 수 있는 성능 이슈를 어떻게 해결할 수 있을까요?
Q. B-Tree와 B+Tree의 구조적 차이를 설명하고, 왜 대부분의 데이터베이스 인덱스는 B-Tree보다 B+Tree를 사용하는지 설명해주세요. 특히 범위 검색과 디스크 I/O 관점에서 설명해주시기 바랍니다.
내부 노드와 리프 노드가 각각 어떤 데이터를 저장하는지, 그리고 리프 노드들이 어떻게 연결되어 있는지를 비교해보세요.
B-Tree는 모든 노드(내부/리프)에 키와 데이터를 함께 저장하지만, B+Tree는 내부 노드에는 키만 저장하고 실제 데이터는 모두 리프 노드에만 저장합니다. B+Tree의 리프 노드들은 연결 리스트로 연결되어 있어 순차 접근이 효율적입니다. 데이터베이스가 B+Tree를 선호하는 이유는 첫째, 내부 노드가 키만 저장하므로 더 많은 키를 메모리에 캐싱할 수 있어 트리 높이가 낮아지고 디스크 I/O가 감소합니다. 둘째, 모든 데이터가 리프 노드에 있고 연결 리스트로 연결되어 있어 범위 검색(range query) 시 리프 노드만 순회하면 되므로 매우 효율적입니다. 셋째, 풀 스캔이 필요한 경우 리프 노드만 순회하면 되어 일관된 성능을 보장합니다. MySQL InnoDB, PostgreSQL 등 대부분의 RDBMS가 이러한 이유로 B+Tree를 인덱스 구조로 채택했습니다.
- • B+Tree는 내부 노드에 키만 저장하여 더 많은 키를 메모리에 캐싱 가능
- • 리프 노드가 연결 리스트로 연결되어 범위 검색과 순차 접근에 최적화
- • 디스크 I/O 감소와 일관된 검색 성능 제공
수백만 건 이상의 데이터를 다루는 데이터베이스에서 인덱스 설계 시 B+Tree의 특성을 이해해야 효율적인 쿼리 성능을 달성할 수 있습니다.
B+Tree의 차수(order)를 결정할 때 고려해야 할 요소들은 무엇이며, 디스크 블록 크기와 어떤 관계가 있나요?
Q. 최단 경로 알고리즘인 Dijkstra와 Bellman-Ford의 차이점을 설명하고, 각각 어떤 상황에서 사용해야 하는지 설명해주세요. 시간 복잡도와 음수 가중치 처리 관점에서 비교해주시기 바랍니다.
음수 가중치와 음수 사이클을 각 알고리즘이 어떻게 처리하는지, 그리고 우선순위 큐 사용 여부를 생각해보세요.
Dijkstra 알고리즘은 우선순위 큐를 사용하여 현재까지 발견한 최단 거리 노드부터 탐색하며, 시간 복잡도는 O((V+E)log V)입니다. 하지만 음수 가중치가 있으면 그리디 방식의 특성상 최적해를 보장할 수 없어 사용할 수 없습니다. Bellman-Ford 알고리즘은 모든 간선을 V-1번 반복하며 완화(relaxation)하는 방식으로, 시간 복잡도는 O(VE)로 느리지만 음수 가중치를 처리할 수 있고 음수 사이클 존재 여부도 감지할 수 있습니다. 실무에서는 일반적인 경로 탐색(네비게이션, 네트워크 라우팅 등)에서는 Dijkstra를 사용하고, 금융 시스템의 차익거래 탐지나 음수 비용이 존재하는 최적화 문제에서는 Bellman-Ford를 사용합니다. 모든 쌍의 최단 경로가 필요하다면 Floyd-Warshall 알고리즘도 고려할 수 있습니다.
- • Dijkstra는 빠르지만(O((V+E)log V)) 음수 가중치 처리 불가
- • Bellman-Ford는 느리지만(O(VE)) 음수 가중치와 음수 사이클 감지 가능
- • 문제의 특성(음수 가중치 존재 여부)에 따라 알고리즘 선택
지도 서비스의 경로 탐색, 네트워크 라우팅 프로토콜, 물류 최적화 시스템에서 최단 경로 알고리즘의 선택이 성능과 정확도에 직접적인 영향을 미칩니다.
실시간 내비게이션 시스템에서 교통 상황에 따라 동적으로 변하는 도로 가중치를 처리하려면 Dijkstra 알고리즘을 어떻게 개선할 수 있을까요?
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!