728x90 구간의 최솟값 구하기1 BOJ - 10868번, 최솟값 문제 Segment Tree를 이용한 풀이 이번 문제는 주어진 N개의 정수들에 대해 M번의 구간 최솟값을 묻는 질의에 올바른 답을 반환하는 알고리즘을 구현하는 것이 목표입니다. 물론, 구간의 최솟값을 확인하기 위해 linear한 탐색 방식을 취할 수 있겠지만, 이렇게 하는 경우 - worst case 100,000(N의 최댓값) x 100,000(M의 최댓값) = 10^12번의 연산 위와 같이 연산의 횟수가 너무 커서 시간 초과를 결과로 받게 될 것입니다. 따라서 지난번에 정리한 세그먼트 트리의 개념을 구간 합을 구하는 대신 최솟값을 구할 수 있도록 변형해서 이번 문제를 풀이하는 방식을 채택해 봤습니다. https://kkkdh.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%E.. 2023. 1. 18. 이전 1 다음 728x90
