[백준] 2357. 최솟값과 최댓값 (파이썬/python)

문제 출처 : [2357.최솟값과 최댓값](https://www.acmicpc.net/problem/2357)

1. 문제 설명

정수가 차례대로 주어지고, 이후 범위가 차례대로 주어진다.
범위가 주어졌을 때, 해당 범위 내의 값 중 최솟값과 최댓값을 순서대로 출력하는 문제이다.

해당 문제는 세그먼트 트리 (Segment Tree) 자료형을 활용하는 문제이다.
세그먼트 트리는 바이너리 트리의 구조로 데이터를 저장하는 방식으로, 특정 범위 내의 통계값(최소, 최대, 합) 등을 파악하는 데 용이하다.

2. 코드

import sys
input = sys.stdin.readline

# 입력값 받기
num_nums, num_opers = map(int, input().split())
nums = [int(input()) for _ in range(num_nums)]
oprs = [list(map(int, input().split())) for _ in range(num_opers)]

# segment Tree class 작성

class SegmentTree():

    def __init__(self, nums):
        self.len_arr = len(nums)
        self.arr = nums
        self.tree = [[0, 0] for _ in range(self.len_arr * 4)]
        self.build_tree(1, 0, self.len_arr-1)

    def build_tree(self, node_idx, left_idx, right_idx):

        # escape condition
        if left_idx == right_idx:
            self.tree[node_idx] = [self.arr[left_idx]]*2
            return self.tree[node_idx]

        # make child nodes
        mid_idx = left_idx + (right_idx - left_idx)//2
        min_left, max_left = self.build_tree(node_idx << 1, left_idx, mid_idx)
        min_right, max_right = self.build_tree((node_idx << 1)+1, mid_idx+1, right_idx)
        self.tree[node_idx] = [min(min_right, min_left), max(max_right, max_left)]
        return self.tree[node_idx]

    def get_minmax(self, node_idx, left_idx, right_idx, start_idx, end_idx):

        # when target is out of range
        if end_idx < left_idx or start_idx > right_idx:
            return [10**9+1, -1]

        # when target is fully included in the range
        if start_idx <= left_idx and end_idx >= right_idx:
            return self.tree[node_idx]

        mid_idx = left_idx + (right_idx - left_idx)//2
        min_left, max_left = self.get_minmax(node_idx << 1, left_idx, mid_idx, start_idx, end_idx)
        min_right, max_right = self.get_minmax((node_idx<<1)+1, mid_idx+1, right_idx, start_idx, end_idx)
        return [min(min_left, min_right), max(max_left, max_right)]

s_tree = SegmentTree(nums)
# print(s_tree.tree)

for start_idx, end_idx in oprs:
    print(*s_tree.get_minmax(1, 0, num_nums-1, start_idx-1, end_idx-1))

3. 코드 설명

3.1. 세그먼트 트리 만들기

class SegmentTree():

    def __init__(self, nums):
        self.len_arr = len(nums)
        self.arr = nums
        self.tree = [[0, 0] for _ in range(self.len_arr * 4)]
        self.build_tree(1, 0, self.len_arr-1)

    def build_tree(self, node_idx, left_idx, right_idx):

        # escape condition
        if left_idx == right_idx:
            self.tree[node_idx] = [self.arr[left_idx]]*2
            return self.tree[node_idx]

        # make child nodes
        mid_idx = left_idx + (right_idx - left_idx)//2
        min_left, max_left = self.build_tree(node_idx << 1, left_idx, mid_idx)
        min_right, max_right = self.build_tree((node_idx << 1)+1, mid_idx+1, right_idx)
        self.tree[node_idx] = [min(min_right, min_left), max(max_right, max_left)]
        return self.tree[node_idx]

build_tree는 self를 제외한 3개의 인자 (node_idx, left_idx, right_idx)를 받는다.
node_idx는 세그먼트 트리 내의 노드의 인덱스이다. 각 노드별 인덱스는 다음과 같다.

• 출처 : 세그먼트 트리 (Segment Tree)

보통 최상위 노드의 인덱스는 1로 두는데, 이는 자식 노드와 부모 노드 간의 연산을 편하게 하기 위함이다.
가령, 부모 노드의 인덱스가 N이라고 가정한다면, 자식 노드의 인덱스는 2N과 2N+1이 된다.
마찬가지로, 자식노드에서 부모노드로 가기 위해서는 // 연산을 수행하면 된다.

left_idx는 서브트리를 생성하기 위해 참조할 배열의 가장 왼쪽 인덱스, right_idx는 가장 오른쪽 인덱스이다.

배열의 길이를 절반으로 나눌 기준 값 (mid_idx)를 기준으로 절반으로 나눠주며,
build_tree 재귀함수를 계속 실행해주면서 특정 노드가 단 하나의 값을 참조할 때까지 해당 과정을 반복한다.
이후, 노드를 타고 올라가면서 자식 노드 간의 최소, 최대값 비교를 통해 부모 노드를 갱신해준다.

3.2. 최소, 최대값 구하기

class SegmentTree():

    def __init__(self, nums):
        self.len_arr = len(nums)
        self.arr = nums
        self.tree = [[0, 0] for _ in range(self.len_arr * 4)]
        self.build_tree(1, 0, self.len_arr-1)

    #...중략...

    def get_minmax(self, node_idx, left_idx, right_idx, start_idx, end_idx):

        # when target is out of range
        if end_idx < left_idx or start_idx > right_idx:
            return [10**9+1, -1]

        # when target is fully included in the range
        if start_idx <= left_idx and end_idx >= right_idx:
            return self.tree[node_idx]

        mid_idx = left_idx + (right_idx - left_idx)//2
        min_left, max_left = self.get_minmax(node_idx << 1, left_idx, mid_idx, start_idx, end_idx)
        min_right, max_right = self.get_minmax((node_idx<<1)+1, mid_idx+1, right_idx, start_idx, end_idx)
        return [min(min_left, min_right), max(max_left, max_right)]

최소 최대값을 구하는 과정을 세그먼트 트리를 만드는 과정과 비슷하다.
start_idx는 구하고자 하는 범위의 최소값, end_idx는 구하고자 하는 범위의 최대값이다.
세그먼트 트리를 만드는 과정과 다른 부분이 있다면 재귀함수를 탈출하는 조건이다.

(1) 만약 구하고자 하는 범위가 노드가 저장하고 있는 값 바깥에 있다면 연산을 할 필요가 없기 때문에 탈출한다.
(2) 만약 구하고자 하는 범위가 온전히, 저장하고 있는 값 안쪽에 있다면 그 값을 그대로 반환한다.

만약 두 조건을 둘 다 만족하지 못한다면 트리를 만드는 과정과 마찬가지로 계속 아래로 가지를 뻗어나가면 된다.

• 참조 : 세그먼트 트리