반응형
SMALL
백준 구간 합 구하기 파이썬
-
백준 2042번 구간 합 구하기알고리즘 2023. 8. 9. 09:19
N개의 수가 주어지고 연속된 어떤 부분의 합을 구하는 문제입니다. 중간에 i번째 수를 X로 바꾸어주기도 합니다. 이번 문제의 풀이에 앞서 이번 문제의 알고리즘 분류인 세그먼트 트리에 대해 알아보았습니다. 세그먼트 트리 세그먼트 트리는 여러 개의 연속된 데이터가 존재 할 경우 연속된 어떤 부분의 데이터 합을 구하는 방법에 관한 알고리즘입니다. N개의 변 할 수 있는 데이터에서 연속된 수 M개의 합을 여러번 구하는 방법은 무조건 M번의 반복을 통해서 구할 수 있습니다. N과 M이 엄청 큰 수라면 오랜 시간이 걸리게 될 것입니다. 세그먼트 트리는 트리의 서브트리에 포함된 연속된 범위의 데이터들의 합을 각 서브트리의 루트 노드에 저장 할 수 있도록 해줌으로써 좀 더 빠르게 특정 범위의 데이터의 합을 구 할 수 ..