세그먼트 트리(Segment Tree) 알고리즘
Tech/알고리즘2020. 12. 21. 22:12세그먼트 트리(Segment Tree) 알고리즘

이게 뭐야? 트리 종류 중에 하나이며, 연속된 구간(특정 범위)의 합(최솟값, 최댓값, 곱 등)을 구하는데 많이 쓰인다. 아래에서 선형구현과 비교하며 왜 쓰는지, 어떻게 사용하는지 gif를 준비해 놨으니 자세히 알아보자. 세그먼트 트리 문제 보기 문제 - 1 페이지 www.acmicpc.net 일단 결과부터 보자 입력된 수는 10의 7제곱이다. 10개의 데이터 [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]를 두고 구간 합을 구해본다. 예시 입력 : 1 10 예시 출력 : 55 선형 구현 O(N) 초기화 과정 O(N) ARRAY = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] for i in range(1,len(ARRAY)): ARRAY[i] += ARRAY[i-1] 1 3 6..

image