[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 10868번 _ 최솟값

https://www.acmicpc.net/problem/10868

10868번: 최솟값

[문제]

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) 세그먼트 트리 자료구조를 활용해야 풀 수 있는 문제다.

2) 세그먼트 트리를 공부해본 적이 없어 다른 사람의 풀이를 따라가며 내용을 익히는 것을 목표로 하였다.

3) 가장 먼저 Init 함수로 트리를 생성한다. 재귀적으로 접근하는 것이 일반적이고, 문항에서 필요로 하는 정보를 노드에 담을 수 있도록 구현하는 것이 핵심이다. 이 문항에서는 특정 범위 내에서의 최소인 정수를 노드에 저장해 두어야한다.

4) Min 함수로 a,b가 주어졌을 때 해당 구간에서의 최솟값을 탐색한다. 이 역시 재귀적으로 구현하는데, 탈출 조건 설정에 대한 이해가 필요하다. 먼저 첫 조건문은 탐색 구간 외의 정보가 포함되는 경우 해당 노드를 최솟값 결정에 사용하지 않기 위해 임의의 가장 큰 값(조건 내에서 최댓값)을 리턴한다. 두 번째 조건문은 해당 노드의 정보가 탐색 구간 내의 정보만을 포함하면 노드의 값을 리턴한다. 이후 재귀적으로 노드를 펼쳐나가면서 탐색 구간 내의 모든 정수를 확인하도록 구현되어 있다.

 

import sys

def Init(node,start,end):
    if start == end:
        tree[node]=num[start]
        return tree[node]
    tree[node] = min(Init(node*2,start,(start + end)//2),Init(node*2+1,(start + end)//2+1,end))
    return tree[node]
    
def Min(node,start,end,left,right):
    if left > end or right < start:
        return 1000000001
    if left <= start and right >= end:
        return tree[node]
    k1 = Min(node*2,start,(start + end)//2,left,right) 
    k2 = Min(node*2+1,(start + end)//2+1,end,left,right)
    return min(k1,k2)

tree=[0 for i in range(3000000)]
num=[]
n,m=map(int,sys.stdin.readline().split())

for i in range(n):
    num.append(int(sys.stdin.readline()))

Init(1,0,n-1)

for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    print(Min(1,0,n-1,a-1,b-1))

오늘은 대략적인 흐름만 살펴보았고, 추가로 세그먼트 트리와 펜윅 트리에 대한 공부가 필요해보인다!