[백준10868번] 최솟값 / Python3

문제

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

나의 풀이

이 문제는 세그먼트 트리를 사용하여 풀어야한다. 그런데 처음에 세그먼트 트리에 대하여 잘 몰라서 검색을 통해 세그먼트 트리를 먼저 공부하였다. 세그먼트 트리란 이진 탐색과 비슷하게 구간을 반으로 쪼개어가면서 그 구간에서의 특정 값을 저장해놓는 자료구이다. 위의 최솟값을 구하는 문제를 풀 때 구간이 정해지고 그때마다 구간을 모두 검색해서 최솟값을 찾을수도 있다. 이러면 최솟값을 찾는데 O(n)이고 총 m번의 입력에 따른 최솟값을 구해줘야하니 O(n*m) 즉, 시간복잡도를 O(n^2)이라고 볼 수 있다. 그러나 세그먼트 트리를 사용한다면 최솟값을 구하는데 O(logN)의 시간복잡도로 시간복잡도를 O(NlogN)으로 준다. 이 방법은 시간복잡도는 줄지만 공간복잡도는 위의 방법보다는 크다는 특징이 있기는하다.

이 문제를 푸는 큰 틀을 설명하자면 우선, 주어지는 배열에 대하여 세그먼트 트리를 만들어주는데 여기서 세그먼트 트리의 각각의 값에는 그 구간의 최솟값을 저장하여준다. 이렇게 트리를 다 만들어놓고나서 a, b를 입력 받으면 트리를 탐색하면서 a~b구간의 최솟값을 구해준다.

일단, 세그먼트 트리를 만들어주어야 한다. 위에서 세그먼트 트리는 이진 탐색과 비슷하게 반으로 쪼개어간다고 했다. 그렇다면 이진트리를 만들면된다. 따라서 미리 트리의 사이즈를 지정해주어야하는데 트리의 사이즈는 쉽게 배열의 모든 원소개수를 가지고 만들 수 있는 이진트리의 높이를 구하고 그 높이에 대한 완전 이진 트리의 크기만큼 지정을 해주면 될 것이다. 완전 이진 트리의 높이는 h = log2(n)이다. 그렇다면 높이 h에 대한 완전 이진 트리의 노드 개수는 2^(h+1)-1이 될 것이다. 아래 그림으로 보면 이해하는데 도움이 될 것이다.

이렇게 완전 이진 트리의 노드 개수를 알아냈다면 이 개수만큼의 tree배열을 선언해준다. 배열을 tree로 사용이 가능한 이유는 index를 노드의 번호로 접근이 가능하기 때문이다. 위에 root노드를 1번으로 지정하고 번호를 메겨놓았다. 저걸 참고로 보면, 부모에 대한 왼쪽 노드의 번호는 node * 2이고 오른쪽 노드의 번호는 node * 2 + 1이라는 것을 확인할 수 있다. 따라서 tree가 배열이라면 tree[1]은 루트노드 그 왼쪽 자식의 인덱스는 2로 tree[2]가 된다. 그럼 오른쪽 자식은 tree[3] ... tree[3] 의 왼쪽 자식은 tree[6]가 된다. 그럼 이제 tree는 다 만들었고 세그먼트 트리로 초기화를 해보겠다.

세그먼트 트리를 초기화할때는 루트 노드부터 재귀적으로 자식으로 접근하며 구간의 최솟값들을 저장해주면 된다. 우선, 0~9의 범위를 0~4와 5~9로 나누고 0~4를 0~2와 2~4로 나누면서 0과 같이 하나가 남는다면 배열의 0번 인덱스의 값을 저장한다. 이렇게 저장을 하면 재귀로 구현을 하였기때문에 이 값들을 사용하여 상위 노드에서 이 값들만 비교하여 최솟값을 저장하면 된다. 따라서 그때마다 범위의 모든 값을 탐색하지 않아도 된다는 것이다. 아래 그림을 참고하면 좋을 것이다.

이제 세그먼트 트리를 만들었으니 구간을 입력받으면 그 구간에서의 최솟값을 검색해서 반환만 해주면 문제는 해결이다. 쉽게 생각하면 검색도 초기화와 비슷하게 구간을 반씩 나누어 가면서 그에 해당되는 곳에서 최솟값들을 비교해서 반환을 해주면 된다. 가령 3 ~ 6구간의 값을 구하고 싶다면

• 09에서 04와 5~9로 접근한다.

• 04에서는 02, 34로 접근하는데 02는 구간에 포함이 되지않으므로 끝내고 3~4모두 범위에 속하니 38을 반환한다.

• 59에서는 57, 89로 접근하는데 89는 속하지 않으니 끝내고 57에서 다시 56으로 접근 여기서의 최솟값 51을 반환한다.

• 그럼 이제 38과 51중 최솟값인 38을 반환한다. 38이 곧 3~6구간에서의 최솟값이 된다.

  
  

파이썬으로 아래 코드와 같이 짰는데 시간초과가 나왔었다. 검색을 통해서 input()을 사용하지 않고 sys.stdin.readline()을 사용하니 해결할 수 있었다.

설명이 살짝 두서가 없는 것 같지만 필자도 처음에 공부를 할때 아무리봐도 잘 이해가 안갔었지만, 그림을 직접 그려보면서 하나하나 따져보고 코드를 보면서 감탄을 하면서 문제를 풀어보았다. 역시 새로 무언가를 깨달아가는 재미는 아주 쏠쏠한 재미인 것 같았다.ㅎㅎ

코드

# 10868번 최솟값
from math import *
import sys

# 세그먼트 트리 초기화
def init(node, start, end):
    if start == end:
        tree_min[node] = arr[start]
        return tree_min[node]

    mid = (start + end) // 2
    tree_min[node] = min(init(node*2, start, mid), init(node*2+1, mid+1, end))
    return tree_min[node]

# 최솟값 쿼리
def query(node, start, end, left, right):
    if start > right or end < left:
        return 1000000001

    if left <= start and end <= right:
        return tree_min[node]

    mid = (start + end) // 2
    return min(query(node*2, start, mid, left, right), query(node*2+1, mid+1, end, left, right))

# main
n, m = [int(x) for x in sys.stdin.readline().split()]

# 세그먼트 트리 사이즈 계산
h = int(ceil(log2(n)))       # 트리의 높이
t_size = 1 << (h+1)     # 대략의 트리 총 노드 개수

arr = []
tree_min = [0] * t_size     # 최솟값 저장

for _ in range(n):
    arr.append(int(sys.stdin.readline()))

init(1,0,n-1)

for _ in range(m):
    a, b = [int(x) for x in sys.stdin.readline().split()]

    # 주어지는 a, b는 index가 아니라 번째수임을 주의해야함.
    print(query(1, 0, n-1, a-1, b-1))