문제 링크
분류
세그먼트 트리(segtree), 자료 구조(data_structures)
설명
세그먼트 트리에 처음 입문하는 사람들이 가장 많이 접하는 세그먼트 트리 유형의 문제라고 생각한다.
구간합, 구간곱, 구간 내 최대값 등 다양한 값들에 대해 선형 리스트를 기준으로 O(NlogN)이라는 시간에 구축하여 각 구간에 대한 정보를 O(logN)이라는 빠른 속도로 접근할 수 있다는 장점이 존재한다.
이 문제는 크게 세그먼트 트리를 구축하는 함수, 구간 정보를 찾는 함수, 변경된 값을 반영하는 함수로 나눌 수 있다.
생성 함수
세그먼트 트리를 생성하는 함수를 먼저 보면
def make_segtree(target_list: list, result_list: list, start: int, end:int, now_node: int) -> int:
'''
최소 숫자 정보를 담는 세그먼트 트리를 생성하는 함수
'''
# 포인터가 한 곳으로 모인 경우
if start == end:
# 해당 노드는 포인터가 가리키는 인덱스의 값과 동일
result_list[now_node] = target_list[start]
# 포인터가 범위를 나타내는 경우
else:
# Devide and Conquer Algorithm
# 중간 지점 선언
mid = (start + end) // 2
# 중간 지점을 기준으로 구간을 분할하여 최소값으로 갱신
val_1 = make_segtree(target_list, result_list, start, mid, 2 * now_node)
val_2 = make_segtree(target_list, result_list, mid + 1, end, 2 * now_node + 1)
# 두 구간의 최소값을 비교하여 둘 중 최소값을 현재 노드에 기록
result_list[now_node] = min(val_1, val_2)
# 현재 노드의 값을 반환
return result_list[now_node]기본적으로 전체 리스트를 구간별로 쪼개면서 각 구간에 대한 정보를 세그먼트 트리의 각 노드에 담는 과정을 보여주고 있다.
재귀 방식을 사용했기 때문에 구간 길이가 1이 될 때까지 재귀가 진행될 때까지 재귀 스택을 쌓게 되며, 도달한다면 해당 주소에 리스트 1개 값에 대한 정보를 입력한다.
이후 반환된 값들을 통해 리프 노드가 아닌 노드들은 조건에 맞는 값을 취사선택하면서 루트에 마지막으로 도달하게 된다.
따라서 루트 노드에 들어 있는 값은 전 구간에서 문제에서 요구한 조건에 가장 걸맞는 값이 되는 것이다.
탐색 함수
다음으로 구간 내 최소값을 찾는 함수에 대해 확인하면
def find_min_number(target_tree: list, start: int, end: int, left: int, right: int, now_node: int) -> int:
'''
해당 구간의 최소값을 찾는 함수
'''
# 범위 내로 포인터가 좁혀진 경우
if left <= start and right >= end:
# 현재 노드값을 반환
return target_tree[now_node]
# 범위를 아예 벗어난 경우
elif left > end or right < start:
# None 값을 반환
return None
# 범위가 걸친 경우
else:
# Devide and Conquer Algorithm
# 중간 지점 선언
mid = (start + end) // 2
# 중간 지점을 기준으로 구간을 분할하여 값을 확인
val_1 = find_min_number(target_tree, start, mid, left, right, 2 * now_node)
val_2 = find_min_number(target_tree, mid + 1, end, left, right, 2 * now_node + 1)
# 반환된 값들 중 None이 존재하는 경우
if val_1 is None and val_2 is None:
return None
elif val_1 is None:
return val_2
elif val_2 is None:
return val_1
# None이 없다면
else:
# 두 구간의 최소값 중에서 더 작은 값을 반환
return min(val_1, val_2)기본적으로 내가 찾는 구간이 포함된 곳이라면 세부적으로 진행해서 완벽하게 내가 찾는 구간만 포함할 때까지 진행하고 해당 값을 반환하여 상위 함수에서 확인할 수 있도록 코드를 구성했다.
만약 범위를 벗어난 경우는 None을 반환하도록 하여 조건을 통해 Pruning만 해주면 완벽하게 범위에 있는 구간만 선택하여 비교할 수 있다.
수정 함수
마지막으로 값의 수정이 이루어진 경우 반영하는 함수를 보자
def change_segtree(target_tree: list, start: int, end: int, target_idx: int, target_val: int, now_node: int) -> None:
'''
리스트에 생긴 변경점을 트리에 반영하는 함수
'''
# 포인터가 한 곳으로 모인 경우
if start == end:
# 목표로 하는 인덱스랑 동일하다면 변경값을 반영
if start == target_idx:
target_tree[now_node] = target_val
# 포인터가 범위로 주어진 경우
else:
# 목표 인덱스가 범위 내에 존재할 경우에만 갱신 가능성 존재
if start <= target_idx <= end:
# Devide and Conquer Algorithm
# 중간 지점 선언
mid = (start + end) // 2
# 중간 지점을 기준으로 변경될 수 있는 인덱스를 재조사
change_segtree(target_tree, start, mid, target_idx, target_val, 2 * now_node)
change_segtree(target_tree, mid + 1, end, target_idx, target_val, 2 * now_node + 1)
# 하위 노드들의 갱신이 진행된 이후 현재 노드의 갱신 진행
target_tree[now_node] = min(target_tree[2 * now_node], target_tree[2 * now_node + 1])
현재 변경된 값의 인덱스가 포함된 구간이라면 전부 바꿔줘야 하기 때문에 해당 인덱스를 포함한 구간이냐 아니냐를 기준으로 변별을 진행한다.
생성 함수와 마찬가지로 한 개의 인덱스로 조여질 때까지 재귀 스택을 쌓게 되며 해당 인덱스 1개만을 포함하는 노드값의 변경을 시작으로 반환을 진행하면서 수정된 값을 반영하고 최종적으로 루트 노드까지 체크하여 마무리하게 될 것이다.
풀이 코드
위 과정을 통해 문제에서 요구한 동작을 전부 모듈화 할 수 있으며 이하 전체 코드를 확인할 수 있다.
# 수열과 쿼리 17
import sys
from math import ceil, log2
input = sys.stdin.readline
def make_segtree(target_list: list, result_list: list, start: int, end:int, now_node: int) -> int:
'''
최소 숫자 정보를 담는 세그먼트 트리를 생성하는 함수
'''
# 포인터가 한 곳으로 모인 경우
if start == end:
# 해당 노드는 포인터가 가리키는 인덱스의 값과 동일
result_list[now_node] = target_list[start]
# 포인터가 범위를 나타내는 경우
else:
# Devide and Conquer Algorithm
# 중간 지점 선언
mid = (start + end) // 2
# 중간 지점을 기준으로 구간을 분할하여 최소값으로 갱신
val_1 = make_segtree(target_list, result_list, start, mid, 2 * now_node)
val_2 = make_segtree(target_list, result_list, mid + 1, end, 2 * now_node + 1)
# 두 구간의 최소값을 비교하여 둘 중 최소값을 현재 노드에 기록
result_list[now_node] = min(val_1, val_2)
# 현재 노드의 값을 반환
return result_list[now_node]
def find_min_number(target_tree: list, start: int, end: int, left: int, right: int, now_node: int) -> int:
'''
해당 구간의 최소값을 찾는 함수
'''
# 범위 내로 포인터가 좁혀진 경우
if left <= start and right >= end:
# 현재 노드값을 반환
return target_tree[now_node]
# 범위를 아예 벗어난 경우
elif left > end or right < start:
# None 값을 반환
return None
# 범위가 걸친 경우
else:
# Devide and Conquer Algorithm
# 중간 지점 선언
mid = (start + end) // 2
# 중간 지점을 기준으로 구간을 분할하여 값을 확인
val_1 = find_min_number(target_tree, start, mid, left, right, 2 * now_node)
val_2 = find_min_number(target_tree, mid + 1, end, left, right, 2 * now_node + 1)
# 반환된 값들 중 None이 존재하는 경우
if val_1 is None and val_2 is None:
return None
elif val_1 is None:
return val_2
elif val_2 is None:
return val_1
# None이 없다면
else:
# 두 구간의 최소값 중에서 더 작은 값을 반환
return min(val_1, val_2)
def change_segtree(target_tree: list, start: int, end: int, target_idx: int, target_val: int, now_node: int) -> None:
'''
리스트에 생긴 변경점을 트리에 반영하는 함수
'''
# 포인터가 한 곳으로 모인 경우
if start == end:
# 목표로 하는 인덱스랑 동일하다면 변경값을 반영
if start == target_idx:
target_tree[now_node] = target_val
# 포인터가 범위로 주어진 경우
else:
# 목표 인덱스가 범위 내에 존재할 경우에만 갱신 가능성 존재
if start <= target_idx <= end:
# Devide and Conquer Algorithm
# 중간 지점 선언
mid = (start + end) // 2
# 중간 지점을 기준으로 변경될 수 있는 인덱스를 재조사
change_segtree(target_tree, start, mid, target_idx, target_val, 2 * now_node)
change_segtree(target_tree, mid + 1, end, target_idx, target_val, 2 * now_node + 1)
# 하위 노드들의 갱신이 진행된 이후 현재 노드의 갱신 진행
target_tree[now_node] = min(target_tree[2 * now_node], target_tree[2 * now_node + 1])
# 수열의 크기 및 수열 정보 입력
target_length = int(input())
target_arr = ['*'] + list(map(int, input().split()))
# 수열의 구간 최소 숫자를 담을 세그먼트 트리 리스트 선언
segtree_arr = [None for _ in range(pow(2, ceil(log2(target_length) + 1)))]
# 함수를 호출하여 트리 생성
make_segtree(target_arr, segtree_arr, 1, target_length, 1)
# 퀴리 갯수 입력 및 출력 리스트 선언
query_number = int(input())
output = []
# 쿼리 실행
for _ in range(query_number):
# 각 쿼리의 정보
order_type, num_1, num_2 = map(int, input().split())
# 타입 1의 경우
if order_type == 1:
# 리스트 값을 변경 및 함수를 호출하여 트리에 반영
target_arr[num_1] = num_2
change_segtree(segtree_arr, 1, target_length, num_1, num_2, 1)
# 타입 2의 경우
elif order_type == 2:
# 함수를 호출하여 해당 구간의 최소 숫자를 출력 리스트에 추가
output.append(find_min_number(segtree_arr, 1, target_length, num_1, num_2, 1))
# 결과 출력
for result in output:
print(result)
24시간은 부족한 게 맞다