[백준 10868] 구간 최소값 구하기 (Python)

[백준 10868] 구간 최소값 구하기 (Python)

📌 문제 분석

• 주어진 수열에서 특정 구간의 최소값을 빠르게 구해야 하는 문제입니다.
• 단순히 탐색하면 O(n)이지만, 세그먼트 트리를 사용하면 O(log n)으로 해결할 수 있습니다.

🚨 시행착오

처음 코드의 문제점

1. start_idx = 2**n으로 설정되어 있는데, 이는 올바른 트리 크기를 보장하지 못합니다.
2. 세그먼트 트리의 크기는 2^k >= n을 만족하는 최소 k를 찾아야 하므로 start_idx = 2**math.ceil(math.log2(n))로 수정해야 합니다.
3. set_tree_min 함수에서 부모 노드를 갱신할 때, min(tree[i//2], tree[i])가 아니라 tree[i//2] = min(tree[i], tree[i^1]) 방식으로 수정해야 합니다.

어떻게 고쳤나요?

• start_idx를 올바르게 설정하여 공간 낭비를 줄였습니다.
• 부모 노드 업데이트 방식을 올바르게 수정했습니다.

💡 해결 방안

import math
import sys

input = sys.stdin.readline

def set_tree_min(tree, start_idx):
    for i in range(start_idx - 1, 0, -1):
        tree[i] = min(tree[i * 2], tree[i * 2 + 1])

def min_tree(tree, start, end):
    result = float('inf')
    while start <= end:
        if start % 2 == 1:
            result = min(result, tree[start])
            start += 1
        if end % 2 == 0:
            result = min(result, tree[end])
            end -= 1
        start //= 2
        end //= 2
    print(result)

n, m = map(int, input().split())
a = [int(input()) for _ in range(n)]
reqs = [list(map(int, input().split())) for _ in range(m)]

start_idx = 2**math.ceil(math.log2(n))
tree_size = start_idx * 2
tree = [float('inf')] * tree_size

# 리프 노드 채우기
tree[start_idx:start_idx + n] = a

# 세그먼트 트리 초기화
set_tree_min(tree, start_idx)

# 쿼리 수행
for req in reqs:
    min_tree(tree, req[0] + start_idx - 1, req[1] + start_idx - 1)

🎯 이 문제의 핵심 포인트

1. 세그먼트 트리의 구조: 완전 이진 트리로 구성됨.
2. 효율적인 최소값 구하기: O(log n) 시간 복잡도로 쿼리 가능.
3. 공간 최적화: 필요한 만큼의 트리 크기를 설정하는 것이 중요.
4. 업데이트 방식: 부모 노드를 정확히 갱신해야 함.

📝 예제로 이해하기

입력:
5 3
1
3
2
7
5
1 3
2 5
3 4

출력:
1
2
2

✨ 이번 문제를 통해 배운 점

1. 2^k >= n을 만족하는 최소 k를 찾는 것이 중요하다는 점.
2. 세그먼트 트리에서 부모 노드 갱신 시, 자식 노드 2개를 모두 고려해야 한다는 점.
3. Python에서 입력이 많을 경우 sys.stdin.readline()을 사용하면 빠르다는 점.

🔍 코드 설명

• set_tree_min: 세그먼트 트리를 초기화하는 함수.
• min_tree: 특정 구간의 최소값을 구하는 함수.
• start_idx 설정: 2^k >= n을 만족하는 최소 k를 찾음.
• 쿼리 수행: 주어진 구간의 최소값을 O(log n)으로 구함.