blog.naver.com/kks227/220791986409
다양한 것을 봤지만 최종적으로 현재 이해한 것의 대부분은 여기서 왔다.
이 블로그 글을 보고 정리한 내용을 적는 것이기 때문에 아직 미숙한 나보다는 위의 링크에서 원글을 보고 이해하는 것이 더 좋을 것이다.
세그먼트 트리
핵심 : 구간들을 보존하고 있는 트리 = 각 노드가 구간 혹은 그 구간의 정보를 가지고 있다.
- 보통 완전 이진 트리를 사용해 전체적으로 동일한 재귀구조가 반복되게 표현한다.
- 값의 개수가 2^n 개가 아닐때는 의미 없는 기본 값으로 채워 포화 이진 트리 형태로 사용하는 것이 대부분이다.
- n개의 값 -> 트리의 높이 log(N)
루트의 인덱스가 1부터 시작되며 레벨 오더 순번으로 노드 번호를 매겨서 자신의 부모, 왼쪽/오른쪽 자식을 접근하게 쉽게 한다.
(https://blog.naver.com/kks227/220791986409)
보통 배열에 담긴 트리 자료구조가 그러하듯, 1부터 루트 노드가 시작한다.
또한, 부모 노드 n, 왼쪽 노드 2n-1, 오른쪽 노드 2n 꼴로 생각하면 된다. 번호는 즉, 인덱스를 의미한다.
이 세그먼트 트리의 사용을 보여주기 위해 원글의 예시를 들고왔다. 원하는 구간을 찾기 위해서는 아래 그림의 빨간색을 찾는 것처럼 조건을 타고타고 재귀를 이용해 찾을 수 있다.( 비재귀를 이용하는 방법 또한 존재하지만 아직 이해해내지 못했다.)
세그먼트 트리는 구간 정보로 사용자가 원하는 아무 값이나 저장해 두는데, 가장 대표적인 것이 구간에 속한 원소들의 합, 구간에 속한 원소들의 곱, 구간 원소들 중 최댓값, 구간 원소들 중 최솟값 등이 있다.( 그 외에 곱, 최대최소,, 백준에 가면 다양한 것을 볼 수 있다.)
구간 [0,2] 의 합을 구하는 방법이다.
구간[2,7]의 합을 구하는 방법이다.
세그먼트트리에 수정이 있을 수 있음을 감안할 때, 구간합을 구함에 있어 O(logN)이라는 최적화된 결과를 보여준다.
'알고리즘' 카테고리의 다른 글
| 프로그래머스 단속카메라 그리디 (0) | 2021.02.16 |
|---|---|
| 프로그래머스 하노이의 탑 (0) | 2021.02.16 |
| 백준 2357번 최솟값과 최댓값 골드1 세그먼트 트리 wip (0) | 2021.02.15 |
| 백준 2170번 선 긋기 파이썬 - 스위핑 알고리즘 1차원 (0) | 2021.02.15 |
| 백준 1655 가운데를 말해요 우선순위 큐 2개 쓰기 (0) | 2021.02.13 |