CS 기초 · 중급
이진 탐색 트리(BST)에서 중위 순회(Inorder Traversal)가 어떤 특징을 가지며, 이를 활용하여 어떤 문제를 해결할 수 있는지 설명해주세요.
힌트 · 중위 순회는 정렬된 순서로 노드를 방문하는 특징이 있어, BST의 모든 요소를 정렬된 순서로 얻거나 특정 범위의 요소를 찾는 데 활용됩니다.
정렬된 순서재귀균형 이진 트리탐색범위 탐색
모범답안
면접관님, 이진 탐색 트리에서 중위 순회는 항상 노드를 정렬된 순서대로 방문한다는 특징이 있습니다. 왼쪽 서브트리, 루트 노드, 오른쪽 서브트리 순으로 방문하기 때문이죠.
이 특징을 활용해서 다양한 문제를 풀 수 있습니다. 예를 들어, BST에 저장된 모든 값을 정렬된 배열 형태로 얻고 싶을 때 중위 순회를 사용하면 간단하게 구현할 수 있습니다.
또 다른 예로는, 특정 범위 내에 있는 값을 찾는 문제가 있습니다. 중위 순회를 하면서 현재 노드의 값이 범위 안에 있는지 확인하고, 범위를 벗어나면 탐색을 중단하여 효율적으로 원하는 값들을 찾을 수 있습니다. 균형 잡힌 BST라면 시간 복잡도는 O(k + log n) 정도가 될 겁니다. (k는 범위 내의 노드 수, n은 전체 노드 수)
읽었다면, 이제 직접 답해볼 차례예요
패스잇 앱에서 이 질문에 말로 답하면 AI가 꼬리질문까지 이어가며 1:1 코칭합니다.
함께 보는 알고리즘 면접 질문
- 특정 네트워크에서 최단 경로를 찾아야 할 때 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) 중 어떤 알고리즘을 선택해야 하며, 그 이유는 무엇인지 설명해주세요.
- 동적 계획법(Dynamic Programming)이 그리디(Greedy) 알고리즘과 어떻게 다른지 설명하고, 두 알고리즘이 각각 어떤 문제 유형에 주로 적용되는지 구체적인 예시를 들어주세요.
- 해시 테이블(Hash Table)에서 해시 충돌(Hash Collision)이 발생했을 때 이를 해결하는 대표적인 방법 두 가지를 설명하고, 각각의 장단점을 비교해주세요.
- 우선순위 큐(Priority Queue)를 구현할 때 힙(Heap) 자료구조를 사용하는 주된 이유와, 힙의 삽입 및 삭제 연산이 어떻게 동작하는지 설명해주세요.
- 두 개의 포인터(Two Pointers) 기법이 어떤 문제들을 효과적으로 해결할 수 있는지 두 가지 예시를 들고, 각 예시에서 이 기법이 어떻게 적용되는지 설명해주세요.
- 대규모 데이터셋에서 동적 계획법(Dynamic Programming)을 적용할 때, DP 테이블의 크기가 너무 커지거나 상태 전이 비용이 높아져 발생하는 성능 문제를 해결하기 위한 고급 최적화 기법(예: Convex Hull Trick, Divide and Conquer Optimization, Monotonic Queue Optimization)들을 설명하고, 각 기법이 어떤 형태의 점화식에 적용될 수 있는지 구체적인 예시를 들어 설명하시오.