DSA Interview Prep · 강의

k번째 최솟값, 구간 합, BST를 정렬 배열로 변환

Q: “k번째 최솟값, 구간 합, BST를 정렬 배열로 변환” 강의는 무료인가요?

네 — “k번째 최솟값, 구간 합, BST를 정렬 배열로 변환” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

Q: “k번째 최솟값, 구간 합, BST를 정렬 배열로 변환” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

정렬된 중위 순회를 활용해 O(k)에 k번째 최솟값을 찾고 O(log n + k)에 구간 내 값의 합을 계산합니다.

레슨 4/413개 단계

k번째 최솟값, 구간 합, BST를 정렬 배열로 변환은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

BST에서 k번째로 작은 값

BST에서 k번째로 작은 원소(LeetCode #230)는 정렬된 중위 순회를 직접 활용하는 고전적인 문제입니다. 중위 순회는 노드를 오름차순으로 방문하므로, 순회하면서 노드 개수를 세고 개수가 k가 되는 노드의 값을 반환하면 됩니다. 시간 복잡도는 O(h + k)이며, h는 높이(가장 왼쪽 노드에 도달하는 데 필요한 높이), k는 중위 순회에서 이동하는 단계 수입니다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_smallest(root, k):
    count = [0]
    result = [None]

    def inorder(node):
        if not node or result[0] is not None:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1))  # 1
print(kth_smallest(root, 2))  # 2

k번째로 작은 값: 스택을 사용한 반복형 구현

반복형 버전은 명시적 스택을 사용하는 중위 순회 패턴을 따릅니다. 널에 도달할 때까지 왼쪽 노드를 스택에 넣은 다음 꺼내며 개수를 셉니다. 개수가 k에 도달하면 현재 노드의 값을 반환합니다. 이 방법은 매우 깊은 트리에서 파이썬의 재귀 제한을 피하면서도 O(h + k) 시간과 O(h) 공간을 사용합니다. 면접관은 재귀형 구현 다음에 반복형 구현을 자주 요청합니다.

def kth_smallest_iterative(root, k):
    stack = []
    curr = root
    count = 0
    while curr or stack:
        while curr:             # go as far left as possible
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()      # process node
        count += 1
        if count == k:
            return curr.val
        curr = curr.right       # move to right subtree
    return -1  # k out of range

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3))  # 3

BST에서 k번째로 큰 값

k번째로 큰 값은 역중위 순회(오른쪽 → 루트 → 왼쪽)를 사용하며, 이 순회는 노드를 내림차순으로 방문합니다. k번 이동한 뒤 현재 노드의 값을 반환합니다. 이는 k번째로 작은 값과 대칭적이며 O(h + k) 시간에 실행됩니다. 트리의 크기를 알고 있다면 kth_smallest(root, total_count - k + 1)를 계산하는 방법도 있지만, 역중위 순회 방식이 더 우아합니다.

def kth_largest(root, k):
    count = [0]
    result = [None]

    def reverse_inorder(node):
        if not node or result[0] is not None:
            return
        reverse_inorder(node.right)   # visit LARGER values first
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        reverse_inorder(node.left)

    reverse_inorder(root)
    return result[0]

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_largest(root, 1))  # 4 (largest)
print(kth_largest(root, 2))  # 3 (2nd largest)

BST의 범위 합

BST의 범위 합(LeetCode #938)은 [low, high] 범위에 속하는 모든 값의 합을 구하는 문제입니다. 가지를 잘라내는 방식으로 BST 속성을 활용합니다. 현재 노드의 값이 low보다 작으면 왼쪽 부분 트리 전체도 low보다 작으므로 건너뜁니다. 현재 값이 high보다 크면 오른쪽 부분 트리를 건너뜁니다. 이렇게 하면 많은 가지를 잘라낼 수 있어 전체 중위 순회보다 효율적입니다.

def range_sum_bst(root, low, high):
    if not root:
        return 0
    total = 0
    if low <= root.val <= high:
        total += root.val
    if root.val > low:    # left subtree might have values >= low
        total += range_sum_bst(root.left, low, high)
    if root.val < high:   # right subtree might have values <= high
        total += range_sum_bst(root.right, low, high)
    return total

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15))  # 7+10+15 = 32

범위 내 노드 개수 세기

[low, high] 범위의 노드 개수 세기에도 같은 가지치기 논리를 적용합니다. 또 다른 방법은 중위 순회 배열에 bisect_left/bisect_right를 사용하는 것입니다. 하지만 직접 BST를 순회하면 O(log n + k)인 반면, 먼저 배열로 변환하면 항상 O(n)입니다. 많은 범위 질의를 처리해야 하는 경우가 아니라면 직접 순회를 선택하십시오. 많은 질의가 필요하다면 부분 트리의 개수를 저장하는 확장 BST를 구축하여 질의마다 O(log n)에 처리할 수 있습니다.

def count_range(root, low, high):
    if not root:
        return 0
    count = 0
    if low <= root.val <= high:
        count += 1
    if root.val > low:
        count += count_range(root.left, low, high)
    if root.val < high:
        count += count_range(root.right, low, high)
    return count

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(count_range(root, 6, 15))  # 7, 10, 15 = 3

BST를 정렬 배열로 변환(전체 알고리즘)

BST를 정렬 배열로 변환하는 데는 O(n) 시간과 O(n) 공간이 필요합니다. 중위 순회를 사용하여 각 값을 append합니다. 이는 여러 단계로 이루어진 문제의 출발점입니다. 예를 들어 ‘두 BST 병합’, ‘BST의 중앙값 찾기’, ‘두 BST의 중위 순회 순서가 같은지 확인하기’ 등이 있습니다. 결과 배열은 인덱스로 O(1) 시간에 접근할 수 있고, 이진 탐색과 두 포인터 기법을 지원하므로 BST 자체에서는 직접 제공하기 어려운 기능을 사용할 수 있습니다.

def bst_to_sorted(root):
    result = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)
    inorder(root)
    return result

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(bst_to_sorted(root))  # [1, 3, 4, 5, 6, 8, 9]

# Binary search on the resulting sorted array:
import bisect
arr = bst_to_sorted(root)
print(bisect.bisect_left(arr, 6))   # 4 (index of 6)

증강 BST: 서브트리 크기

증강 BST는 각 노드에 해당 서브트리의 크기와 같은 추가 정보를 저장합니다. 서브트리 크기를 사용하면 kth-smallest를 O(log n)에 구할 수 있습니다. 각 노드에서 왼쪽 서브트리의 크기가 k-1이면 현재 노드가 답이고, 왼쪽 서브트리의 크기가 k 이상이면 왼쪽으로 재귀 호출하며, 그렇지 않으면 k에서 왼쪽 크기를 빼고 오른쪽으로 재귀 호출합니다. 이는 경쟁 프로그래밍에서 사용하는 순서 통계 트리의 기반이 되는 자료 구조입니다.

class AugNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.size = 1  # subtree size

def get_size(node):
    return node.size if node else 0

def update_size(node):
    if node:
        node.size = 1 + get_size(node.left) + get_size(node.right)

def kth_smallest_aug(root, k):
    left_size = get_size(root.left)
    if k == left_size + 1:
        return root.val      # current node is kth
    elif k <= left_size:
        return kth_smallest_aug(root.left, k)
    else:
        return kth_smallest_aug(root.right, k - left_size - 1)

print('Augmented BST: O(log n) kth smallest with subtree sizes')

BST에서 두 노드 사이의 모든 값 찾기

두 노드 p와 q 사이에 있는 모든 값(p.val < q.val)을 반환하려면 중위 순회와 범위 가지치기를 결합합니다. p.val을 지나면 값 수집을 시작하고 q.val을 지난 후 중지합니다. 이는 범위 합을 일반화한 방법으로, 두 검색 값 사이의 정렬된 수열을 O(h + k) time에 제공합니다.

def values_between(root, low, high):
    result = []
    def inorder(node):
        if not node:
            return
        if node.val > low:    # might be values > low on left
            inorder(node.left)
        if low < node.val < high:  # strictly between
            result.append(node.val)
        if node.val < high:   # might be values < high on right
            inorder(node.right)
    inorder(root)
    return result

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
print(values_between(root, 6, 15))  # [7, 10, 12]

BST의 중앙값

BST의 중앙값은 중위 순회에서 가운데에 위치한 값입니다. 노드가 n개라면 중앙값은 n // 2 인덱스(0부터 시작)에 있습니다. 정렬된 전체 배열을 수집한 다음 해당 인덱스의 값을 가져오거나, 두 번의 순회를 사용할 수 있습니다. 먼저 노드 n개의 개수를 센 다음 두 번째 중위 순회에서 n // 2번째 노드에서 중지합니다. 또는 k = n // 2 + 1로 kth-smallest를 사용할 수도 있습니다.

def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

def median_of_bst(root):
    n = count_nodes(root)
    if n == 0:
        return None
    k = n // 2 + 1  # (n+1)/2-th element for odd, n/2+1-th for even
    return kth_smallest(root, k)

def kth_smallest(root, k):
    count = [0]; result = [None]
    def inorder(node):
        if not node or result[0] is not None: return
        inorder(node.left)
        count[0] += 1
        if count[0] == k: result[0] = node.val; return
        inorder(node.right)
    inorder(root); return result[0]

root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
print(median_of_bst(root))  # 4 (middle of [1,3,4,5,8])

대상에 가장 가까운 K개 값

BST에서 대상에 가장 가까운 k개의 값을 찾습니다. 한 가지 방법은 BST를 정렬된 배열로 변환한 다음 크기가 k인 슬라이딩 윈도우를 사용하는 투 포인터 접근법입니다. 또는 크기가 k인 최대 힙을 사용해 거리를 삽입하고 크기가 k를 초과하면 값을 꺼낼 수 있습니다. 정렬된 배열을 사용하는 방법은 O(n) time에 동작하며 간단합니다. 힙을 사용하는 방법은 O(n log k)이지만 데이터를 연속적으로 받는 환경에서 작동합니다.

import heapq

def closest_k_values(root, target, k):
    # Collect sorted values
    arr = []
    def inorder(node):
        if not node: return
        inorder(node.left)
        arr.append(node.val)
        inorder(node.right)
    inorder(root)

    # Two-pointer sliding window of size k
    left, right = 0, k - 1
    while right < len(arr) - 1:
        if abs(arr[left] - target) <= abs(arr[right + 1] - target):
            break  # left is closer, don't advance
        left += 1
        right += 1
    return arr[left:right + 1]

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_k_values(root, 3.7, 2))  # [3, 4]

후속 원소 순서 속성 활용

많은 BST 문제는 정렬된 순서에서 다음 원소 또는 이전 원소를 찾는 문제로 환원됩니다. BST를 탐색하면 이러한 연산을 O(log n)에 수행할 수 있습니다. 앞에서 만든 반복자는 다음 원소를 분할 상환 O(1)에 제공합니다. kth-smallest, 범위 합, 가장 가까운 값에 대한 지식을 결합하면 대부분의 BST 면접 문제를 다음과 같은 질문으로 해결할 수 있습니다. "중위 순회의 정렬 순서를 이용하면 이 문제를 어떻게 단순화할 수 있을까요?" 이러한 메타 패턴은 BST 문제 해결을 위한 나침반입니다.

# Meta-pattern for BST problems:
# Step 1: What sorted-order property does this exploit?
# Step 2: Is in-order (ascending) or reverse in-order (descending) needed?
# Step 3: Can I prune using BST ordering to avoid O(n) scan?

# Quick reference:
# kth smallest  -> in-order, stop at kth node
# kth largest   -> reverse in-order, stop at kth node
# range sum     -> in-order + BST pruning
# closest value -> walk toward target, track best
# median        -> kth with k = n//2+1
# sorted array  -> full in-order
# validate      -> in-order prev check or min/max bounds
print('Sorted in-order is the universal BST problem tool')

빠른 확인

이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보세요.

인터랙티브 레슨에서 답해보세요

단원 복습

이 단원에서는 중위 순회와 역중위 순회를 사용해 O(h+k)에 kth smallest와 largest를 구하는 방법, 효율적인 범위 검색을 위한 BST 가지치기를 이용한 범위 합, 배열 기반 알고리즘의 기반으로 BST를 정렬된 배열로 변환하는 방법을 배웠습니다. 다음으로 힙과 우선순위 큐를 살펴보겠습니다.

무료로 시작

AI 튜터와 함께 Python을(를) 배우세요 — 무료

브라우저에서 실제 코드를 작성하고 실행하며, 24/7 AI 튜터로부터 즉각적인 도움을 받고, 웹이나 앱에서 중단한 부분부터 계속 학습하세요.

코스: 30
레슨: 120

무료로 학습 시작 전체 코스 보기

자주 묻는 질문