[Python] 백준 2357 : 최솟값과 최댓값 (세그먼트 트리)

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

머리말

solved 통계를 보니 자료구조 관련 데이터가 별로 없길레 관련 문제 중에 랜덤으로 하나를 골랐다.
문제 자체는 굉장히 평이해보였지만 n, m 범위가 1 이상 10만 이하 라는 점에서 아,, 이거 뭔가 트리 써야할 것 같은데? 라는 생각이 들었다.
어떤 트리 써야할 지 몰라 알고리즘 분류를 보니 세그먼트 트리 문제라고 한다.

세그먼트 트리

백준 블로그에 상세한 설명이 적혀있다.
세그먼트 트리는 어떠한 구간 내의 로직을 처리할 때 굉장히 효율적인 알고리즘이다.
트리의 노드에 범위라는 개념이 들어가고, 저장할 데이터는 로직에 따라 다르겠지만 이 문제에서는 해당 구간의 최솟값, 최댓값을 저장한다.

1. 리프 노드(idx)라면 idx ~ idx 사이에 있는 최솟값, 최댓값을 저장하니 해당 값이 들어갈 것이다.
2. 부모 노드는 '왼쪽 자식의 최솟값, 오른쪽 자식의 최솟값'의 최솟값과 '왼쪽 자식의 최대값, 오른쪽 자식의 최대값'의 최댓값을 저장한다.

이를 바탕으로 재귀적으로 로직을 구현하면 된다.

🐥 이건 얻어가자

• 재귀를 이용하는 문제라면 sys.setrecursionlimit(10 ** 6)를 선언해주자. 파이썬의 기본 재귀 깊이 제한으로 인해 원인을 모르고 문제를 틀릴 수 있다.
• 노드의 개수가 N개라고 할 때, 노드의 높이는 H = ceil(logN) 이고, 트리를 만드는데 필요한 배열의 크기는 2^(H+1) - 1개이다.
• 2의 제곱수를 계산할 때 쉬프트 연산 1 << H 를 사용하면 깔꼼
• arr = [int(input()) for _ in range(n)] 배열의 원소를 입력받을 때 다음과 같이 깔삼하게 받을 수 있다.
• 몫 구할 때는 //를 사용하면 된다.

코드

import math
import sys

sys.setrecursionlimit(10 ** 8) # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

def makeSegTree(idx, start, end):
    if start == end: # 리프 노드
        seg[idx] = (arr[start], arr[start]) # 최소값, 최대값은 동일
        return seg[idx]

    mid = (start + end) // 2 # 몫 구하기

    left = makeSegTree(idx * 2, start, mid)
    right = makeSegTree(idx * 2 + 1, mid + 1, end)

    # 왼쪽과 오른쪽 중 각각 min, max 계산
    seg[idx] = (min(left[0], right[0]), max(left[1], right[1]))

    return seg[idx]

def find(idx, start, end):
    # 찾으려는 범위가 전혀 겹치지 않을 때
    if range2 < start or range1 > end:
        return (10**9+1, 0) # 최대 min 값, 최소 max 값 반환

    # 찾으려는 범위가 트리 범위에 속할 때
    if range1 <= start and end <= range2:
        return seg[idx]

    mid = (start + end) // 2
    left =  find(idx * 2, start, mid)
    right = find(idx * 2 + 1, mid + 1, end)
    return (min(left[0], right[0]), max(left[1], right[1]))

n, m = map(int, input().split())
arr = [int(input()) for _ in range(n)] # 이런 방식으로 입력받을 수 있다니

h = math.ceil(math.log2(n)) + 1 # 노드 개수에 따른 트리의 높이 계산 공식
nodeNum = 1 << h ## 2^h 계산
seg = [0 for _ in range(nodeNum)]
makeSegTree(1, 0, len(arr) - 1)

for _ in range(m):
    range1, range2 = map(int, input().split())
    range1, range2 = range1 - 1, range2 - 1 # index이므로 -1 해주기
    answer = find(1, 0, len(arr) - 1)
    print(answer[0], answer[1])

참조

• https://www.acmicpc.net/blog/view/9
• https://velog.io/@sunkyuj/python-%EB%B0%B1%EC%A4%80-2357-%EC%B5%9C%EC%86%9F%EA%B0%92%EA%B3%BC-%EC%B5%9C%EB%8C%93%EA%B0%92