boj 65491 세그먼트 트리(Segment tree) 왜 Segment tree를 쓰는가? Segment라는 단어를 사전에서 찾아보면 '부분, ..을 분할하다' 이런 뜻이 나온다. 말 그대로 구역을 나누어 트리를 만들겠다는 것이다. 무엇을 어떻게 구역으로 나누는가? 가장 흔히 나오는 예시로 배열의 부분합을 구하는 경우를 생각해보자. (세그먼트 트리가 부분합을 구하는데만 사용되는 것은 아니다. 다른 응용문제를 풀어보길 원한다면 BOJ 6549번을 풀어보길 바란다. 내가 세그먼트 트리를 공부하게 된 계기이기도 하다.) 배열 A는 100개의 원소를 가지며, 우리는 i번째부터 j번째 원소의 합을 구하려고한다. 그런데 테스트 케이스가 너무나도 많으므로 매번 i부터 j번째 원소를 더하는 것은 너무 낭비인듯 하다. 그래서 각각의 합(S[i]: 0번째 원소부터 i번째 원.. 2020. 1. 10. 이전 1 다음