최솟값 문제 보러가기

세그먼트 트리를 이용하면 쉽게 해결할 수 있는 문제로 백준 2042 구간 합 구하기 문제에서는 구하고자 하는게 구간 합이였다면, 이 문제에서는 최솟값을 구하면 되는 생각보다 쉬운 문제였다.

백준 2042 구간 합 구하기 풀이 보러가기

문제

---

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에 대한 답을 출력한다.

---

핵심 포인트 요약

• a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것
  👉 특정 구간에서의 최솟값을 찾으면 된다는 것을 알 수 있다. 따라서 여러 개의 데이터가 존재할 때 특정 구간(중간)의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조인 세그먼트 트리를 이용해서 문제를 풀면 된다.

---

코드 & 설명 주석 포함

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = sys.maxsize

# N개의 정수, 순서쌍 갯수 M개 (구간갯수)
N, M = map(int, input().split())
data = [0] + [int(input()) for _ in range(N)]
tree = [0] * (N*4)


# 세그먼트 트리 생성 & 초기화
def init(start, end, index):
    # 해당 구간이 리프노드라면 
    if start == end:
        tree[index] = data[start]
        return tree[index]
    
    # 리프노드가 아니라면 리프노드가 될 때까지 두개의 서브트리로 나눈다.
    mid = (start+end)//2
    tree[index] = min(init(start, mid, index*2), init(mid+1, end, index*2+1))
    return tree[index]


# 특정 구간의 최솟값을 구하는 함수 
def find(start, end, index, left, right):
    # 범위를 완전히 벗어난 경우(범위가 오른쪽으로 넘어갔거나, 왼쪽으로 넘어간 경우)
    if left > end or right < start:
        return INF
    
    # 범위 안에 있는 경우(left, right 사이에 start, end가 있는 경우)
    if left <= start and end <= right:
        return tree[index]
    
    # 그렇지 않는 경우 구간을 좀 더 좁혀서 확인한다. 
    mid = (start+end)//2
    return min(find(start, mid, index*2, left, right), find(mid+1, end, index*2+1, left, right))


# 트리 생성
init(1, N, 1)

for _ in range(M):
    # a번째 정수부터 b번째 정수까지
    a, b = map(int, input().split())
    
    # a~b사이에서 최솟값 찾기 
    print(find(1, N, 1, a, b))
    

코드 & 설명 주석 미포함

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = sys.maxsize


N, M = map(int, input().split())
data = [0] + [int(input()) for _ in range(N)]
tree = [0] * (N*4)


def init(start, end, index):
    if start == end:
        tree[index] = data[start]
        return tree[index]
    
    mid = (start+end)//2
    tree[index] = min(init(start, mid, index*2), init(mid+1, end, index*2+1))
    return tree[index]


def find(start, end, index, left, right):
    if left > end or right < start:
        return INF
    
    if left <= start and end <= right:
        return tree[index]
    
    mid = (start+end)//2
    return min(find(start, mid, index*2, left, right), find(mid+1, end, index*2+1, left, right))


init(1, N, 1)
for _ in range(M):
    a, b = map(int, input().split())
    print(find(1, N, 1, a, b))

---

혹시나 설명이 잘못된 부분이 있으면 댓글 부탁드립니다.