BOJ14428 수열과 쿼리 16
문제
BOJ14428 수열과 쿼리 16
골드I | 백준 14428 | Python3 파이썬 풀이
알고리즘
-
세그먼트 트리 자료구조를 안다면 쉽게 풀 수 있는 문제이다.
-
이 문제에서는 우선, 최솟값을 찾기 위해 세그먼트 트리를 사용한다. (최솟값을 알면 인덱스는 당연히 알 수 있다.) 10868 최솟값 문제와 매우 유사하지만, 최솟값을 출력하는 것이 아닌, 그 값의 인덱스를 출력해야 한다. 이때, 값의 인덱스를 찾기 위해 index() 함수를 사용하면 O(N) 시간이 더 소요되므로, 배열 자체에 값과 인덱스를 함께 넣어주었다.
[5, 3, 4, 1, 2]
-> [[5, 1], [3, 2], [4, 3], [1, 4], [2, 5]]
-
값의 대소를 비교할 때, 대상이 값이 아닌 리스트가 되므로 리스트의 0번째 인덱스의 값의 대소를 비교하는 min() 함수를 따로 작성하였다.
-
부모는 자식 중 작은 값을 가지고 있게 된다. (최솟값이 아닌 인덱스를 출력해야 하므로, 리스트가 된다.)
코드
import sys
from math import *
input = sys.stdin.readline
INF = sys.maxsize
# 리스트의 대소를 비교하기 위한 사용자정의 min 함수
def min(a : list, b : list) -> list:
if a[0] > b[0]:
return b
else:
return a
# 세그먼트 트리 생성 함수
def initTree(node, start, end):
if start == end:
segtree[node] = values[start]
return segtree[node]
mid = (start + end) // 2
segtree[node] = min(initTree(node * 2, start, mid), initTree(node * 2 + 1, mid + 1, end))
return segtree[node]
# 세그먼트 트리 쿼리 함수
def query(node, start, end, left, right):
if start > right or end < left:
return [INF, INF]
if left <= start and end <= right:
return segtree[node]
mid = (start + end) // 2
return min(query(node * 2, start, mid, left, right), query(node * 2 + 1, mid + 1, end, left, right))
# 트리 업데이트 함수
def update(node, start, end, index, x):
if index < start or index > end:
return [INF, INF]
if start == end:
segtree[node] = x
return
mid = (start + end) // 2
update(node * 2, start, mid, index, x)
update(node * 2 + 1, mid + 1, end, index, x)
segtree[node] = min(segtree[node * 2], segtree[node * 2 + 1])
N = int(input())
temp = list(map(int, input().split()))
values = [[0, 0] for _ in range(N)]
# 입력 값을 [값, 인덱스] 형태로 변환해 리스트 저장
for i in range(N):
values[i][0] = temp[i]
values[i][1] = i + 1
# 세그먼트 트리 사이즈
ts = 1 << (int(ceil(log2(N))) + 1)
segtree = [0] * ts
# 트리 생성
initTree(1, 0, N - 1)
M = int(input())
for _ in range(M):
A, B, C = map(int, input().split())
# 트리 값 변경
if A == 1:
values[B - 1][0] = C
update(1, 0, N - 1, B - 1, values[B - 1])
# 구간 출력
else:
print(query(1, 0, N - 1, B - 1, C - 1)[1])
결과
Author And Source
이 문제에 관하여(BOJ14428 수열과 쿼리 16), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehe228/boj14428저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)