백준 10868 - 최솟값

10868번: 최솟값 (acmicpc.net)

 

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 출력한다.

예제 입력 1 복사

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

예제 출력 1 복사

5
38
20
5

 

 

최솟값 문제를 처음 보고 입력을 받은 후 각 인덱스를 저장해서 min 값을 더해주면 되는건가 생각했는데, 역시나 자료구조를 사용하지 않으니 통과가 되지 않았다. 이 문제는 세그먼트 트리를 사용해야하는 문제이다. 세그먼트 트리가 무엇인지조차 기억이 나지 않았기 때문에... 구글링을 해보고 문제를 풀게 되었다.

 

※ 세그먼트 트리란?

- 어떤 데이터가 존재할 때, 특정 구간의 값을 구할 때 사용하는 자료구조

- 구간합, 주어진 쿼리에 대해 빠르게 응답하기 위한 자료구조

- 기본적으로 Binary Tree 구조를 가지고 있음

- O(logN) 시간 복잡도를 가지며, 최악의 경우 O(NlogN)을 가짐

- 완전 탐색에 비해 더 많은 메모리를 필요로 하게 됨

 

[Algorithm] 세그먼트 트리(Segment Tree) with Python (tistory.com)

[Algorithm] 세그먼트 트리(Segment Tree) with Python

이 블로그 포스팅을 많이 참고 했다.

 

그렇다면 세그먼트 트리를 구현해보자.

def build_segment_tree(left, right, i):
    if left == right:
        segment_tree[i] = nums[left]
        return segment_tree[i]
    mid = (right + left) // 2
    segment_tree[i] = min(build_segment_tree(left, mid, i * 2), build_segment_tree(mid + 1, right, i * 2 + 1))
    return segment_tree[i]

 

- left와 right가 같다면 현재 구간이 단일 요소를 의미하기 때문에, nums 배열의 해당 값을 세그먼트 트리 현재 노드에 - 저장하고 반환.

- mid 값을 찾아서 이진 분류 형태 만들기

- segment_tree 리스트에 재귀적으로 좌측 노드와 우측 노드의 최솟값을 담기

 

def query_min(start, end, idx, left, right):
    if left > end or right < start:
        return float('inf')
    if left <= start and right >= end:
        return segment_tree[idx]
    mid = (start + end) // 2
    return min(query_min(start, mid, idx * 2, left, right), query_min(mid + 1, end, idx * 2 + 1, left, right))

 

- idx : 세그먼트 트리 현재 노드 인덱스

- left, right : 질의 구간의 시작, 끝 인덱스

- 질의 구간이 현재 노드 구간과 겹치지 않으면 무한대 반환

- 질의 구간이 현재 노드 구간과 겹치면 idx(현재 노드 인덱스)를 반환

- mid 값을 찾아서 이진 분류 형태 만들기

- 재귀적으로 좌측 노드와 우측 노드의 최솟값을 반환

 

def update(start, end, node, idx, val):
    if start > idx or idx > end:
        return segment_tree[node]
    if start == end:
        segment_tree[node] = val
        return segment_tree[node]
    mid = (start + end) // 2
    segment_tree[node] = min(update(start, mid, node * 2, idx, val), update(mid + 1, end, node * 2 + 1, idx, val))
    return segment_tree[node]

 

- node : 세그먼트 트리의 현재 노드 인덱스

- idx : 업데이트할 리스트의 인덱스

- val : 새로운 값

- 업데이트할 인덱스가 현재 노드 구간에 포함되지 않으면 현재 노드 값을 그대로 반환

- 현재 노드가 업데이트할 인덱스를 나타내면 val로 새로운 값 업데이트 시키고 반환

- segment_tree의 현재 노드 인덱스에 좌측노드, 우측노드의 최솟값을 재귀적으로 담아서 갱신 후 현재 노드가 담긴 segment_tree를 반환

 

이 방식으로 세그먼트 트리를 구현한 후 입력 형식을 맞춰서 세그먼트 트리를 빌드하고 구간을 쿼리 함수를 사용해서 질의하고 update 함수로 갱신시킨 후 담아서 출력해주면 된다.

 

최종 코드

import sys
input = sys.stdin.readline

def build_segment_tree(left, right, i):
    if left == right:
        segment_tree[i] = nums[left]
        return segment_tree[i]
    mid = (right + left) // 2
    segment_tree[i] = min(build_segment_tree(left, mid, i * 2), build_segment_tree(mid + 1, right, i * 2 + 1))
    return segment_tree[i]

def query_min(start, end, idx, left, right):
    if left > end or right < start:
        return float('inf')
    if left <= start and right >= end:
        return segment_tree[idx]
    mid = (start + end) // 2
    return min(query_min(start, mid, idx * 2, left, right), query_min(mid + 1, end, idx * 2 + 1, left, right))

def update(start, end, node, idx, val):
    if start > idx or idx > end:
        return segment_tree[node]
    if start == end:
        segment_tree[node] = val
        return segment_tree[node]
    mid = (start + end) // 2
    segment_tree[node] = min(update(start, mid, node * 2, idx, val), update(mid + 1, end, node * 2 + 1, idx, val))
    return segment_tree[node]

n, m = map(int, input().split())
nums = [int(input()) for _ in range(n)]
queries = [tuple(map(int, input().split())) for _ in range(m)]

segment_tree = [0] * (4*n)
build_segment_tree(0, n-1, 1)

results = []
for i, j in queries:
    result = query_min(0, n-1, 1, i-1, j-1)
    results.append(result)

for result in results:
    print(result)