세그먼트 트리
-
[백준][Kotlin] 2042번 구간 합 구하기백준 2023. 4. 10. 17:00
해당 문제는 세그먼트트리를 이용하면 통과 할 수 있는 문제였습니다. 세그먼트 트리는 구간 질의 (range query) 문제를 효율적으로 해결하기 위한 자료구조입니다. 구간 질의란, 배열이나 리스트와 같은 자료구조에서 주어진 범위에 속하는 값들을 찾는 문제를 의미합니다. 예를 들어, 주어진 배열에서 특정 구간의 합이나 최소값, 최대값 등을 구하는 문제가 구간 질의 문제에 해당됩니다. 세그먼트 트리는 주어진 배열을 트리 형태로 변환하여 구간 질의를 해결합니다. 이를 위해, 배열을 노드로 가지는 이진 트리를 만들고, 각 노드는 해당 구간의 합, 최소값, 최대값 등을 저장합니다. 이진 트리의 루트 노드는 전체 구간에 대한 질의 결과를 저장하며, 자식 노드들은 부모 노드의 구간을 반으로 나눈 구간에 해당하는 값..