2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
본 문제는 세그먼트 트리라는 자료구조를 알고 있는가 없는가를 묻는 문제이다. 올바른 자료구조를 사용할 경우 별도의 조작 없이 바로 정답을 얻을 수 있기 때문에 세그먼트 트리의 튜토리얼 문제라고 볼 수 있다.
그렇기 때문에 트리의 개념과, 이진트리를 선행적으로 알고 있어야 한다.
추가로 배열을 이용해 이진트리를 구현했기 때문에 배열을 이용한 이진트리의 구현에 대해서도 선행적으로 알고 있으면 도움이 된다.
위와 같은 배열을 이용해 트리를 만들고 그것을 이용해 세그먼트 트리를 구성할 것이다.
세그먼트 트리는 구간합, 또는 구간 내의 최댓값 / 최솟값 등을 구할 때에 유용한 자료구조이다.
문제를 풀기 위해 인덱스가 16개인 배열을 트리로 구성하였다. 만약 배열을 이용한 이진트리 구현에 대하여 잘 모를 경우 곧 추가할 링크를 참고하자 검색을 통하여 배열을 이용한 이진트리의 구성에 대해 공부하자.
세그먼트 트리를 구성하기 위해서는 입력값의 개수(= 5개) 이상의 리프 노드를 가진 완전 이진트리가 필요하기 때문에 리프 노드가 8개인 (= 노드의 개수가 15개인) 트리를 구성하였다. 이후 리프 노드에 순차적으로 입력값을 넣어준다.
이후, 각 노드는 자신의 자식 노드 두 개를 합한 값을 취하도록 한다.
여기까지 구성이 되었다면 우선 문제 해결을 위한 자료구조인 세그먼트 트리를 구성한 것이 된다.
문제의 정답을 띄우기 위한 규칙을 설명하기 앞서, 세그먼트 트리의 특징과 문제 해결을 위한 팁을 설명하고자 한다.
1. 세그먼트 트리의 특징은 하나의 노드가 그 자식 노드 전체를 대표한다는 것이다.
위의 사진에 값이 10인 2번 노드를 선택했다고 가정하자, 세그먼트 트리의 특징에 따르면 이 노드의 값인 10은 자식 노드를 대표한다고 할 수 있다. ( = 2번 노드의 자식 영역인 8~11 구간, 즉 입력값 1, 2, 3, 4 영역의 합이 10 임을 의미한다.)
2. 세그먼트 트리를 사용하기 위해서는 임의의 한 노드가 대표하는 구간을 알 수 있어야 한다.
위처럼 트리의 크기가 커졌을 때, 파란색 노드가 대표하는 구간이 몇 번부터 몇번 노드인지 한 번에 확인할 수 있는가?
물론 직접 탐색을 통해 어느 구간을 대표하는지 알아낼 수 있다. 하지만 그렇게 한다면 세그먼트 트리의 장점(=속도)을 살리지 못하는 결과가 된다. 그러므로 임의의 노드가 대표하는 구간을 간단하게 획득 가능한 환경을 만들어야 한다.
본 글에서는 배열을 이용하였기 때문에 인덱스를 이용하여 대표구간을 바로 계산하도록 한다.
문제 해결을 위한 간단한(?) 규칙은 다음과 같다.
값 변경 규칙
루트 노드부터 시작하여 아래의 규칙을 따른다.
- (규칙 A) 값을 바꿀 인덱스를 이용해 바꾸고자 하는 값과 기존 값의 차이를 offset으로 계산한다.
- (규칙 B) 해당 노드의 대표구간 시작점, 대표구간 종료점, 현재 인덱스를 구한다.
- (규칙 C) 이후 아래의 탐색 규칙을 따른다.
- (규칙 C-1) 임의의 노드에 도착하였다면 해당 노드가 변경하고자 하는 인덱스를 포함하는지를 확인한다.
- (규칙 C-2) 포함한다면 해당 노드의 값에 offset을 더해준다.
- (규칙 C-3) 만약 임의의 노드가 값을 교체하고자 하는 노드라면 그대로 탐색을 종료한다.
- (규칙 C-4) (규칙 C-3)에 해당하지 않는다면 자신의 자식 노드 들을 탐색하는 것을 계속한다.
- (규칙 C-4-1) 이때, 자신의 왼쪽 자식 노드의 대표구간은 [자신의 대표구간 시작 ~ 자신의 대표구간 중간]이다.
- (규칙 C-4-2) 이때, 자신의 오른쪽 자식 노드의 대표구간은 [자신의 대표구간 중간 ~ 자신의 대표구간 끝]이다.
구간 합 계산 규칙
루트 노드부터 시작하여 아래의 규칙을 따른다.
- (규칙 A) 임의의 노드에 도착하였다면, 합을 구해야 하는 구간과 자신이 대표하는 구간을 비교한다.
- (규칙 A-1) 합을 구해야 하는 구간이 자신이 대표하는 구간을 완전히 포함하고 있다면 자신의 값을 반환한다.
- (규칙 A-2) 합을 구해야 하는 구간이 자신이 대표하는 구간과 전혀 겹치지 않는다면 0을 반환한다.
- (규칙 A-3) 그 외의 경우 자신의 좌, 우 자식의 반환 값을 더하여 반환한다.
- (규칙 B) 모든 탐색이 끝났다면 최종적으로 반환된 값을 해당하는 구간의 합으로 이용한다.
우선 값 변경 규칙부터 확인해보자.
이때 바꿀 인덱스가 10인 이유는 3번째 리프 노드의 인덱스가 10 이기 때문이다.
이것은 [전체 배열의 크기 / 2 + 입력받은 인덱스 - 1]와 같다. (= 16 / 2 + 3 - 1 = 10)
또한 오프셋이 +3 인 이유는 [바뀔 값 - 기존 값] 이 +3 이기 때문이다.
이때, 첫 루트 노드의 경우 배열의 크기 절반 ~ 배열의 크기 -1 구간에 대표구간을 갖으며, 시작 인덱스는 1을 이용한다.
즉 다음과 같아진다.
이제 (규칙 C)를 이용해 탐색을 시작해보자.
바꿀 인덱스가 시작점 ~ 종료점 사이에 존재한다.
그러므로 현재 노드에 오프셋을 더해준다.
하지만 현재 노드가 값을 교체하고자 하는 노드는 아니다. (= 현재 인덱스와 바꿀 인덱스의 값이 다르다)
그러면 좌우로 나누어 탐색을 계속한다.
이렇게 값의 변경 동작이 끝났다.
다음으로 구간합을 구하는 동작에 대해 살펴보자.
루트 노드에서 시작했을 때, 구간합 시작점과 구간합 종료점이 대표구간을 완전히 포함하고 있지 않다. 그러므로 좌우 자 식 노드의 반환 값을 더해서 정답을 구해야 한다. 즉 A-3 규칙을 따른다.
여기서 구간 합의 영역이 대표구간을 전혀 포함하고 있지 못한 상황이 발생한다.
이때 A-2 규칙을 적용받아 0을 반환한다.
여기에서 구간 합 구간이 대표구간을 완벽히 포함한다. 그러므로 A-1 규칙을 적용받아 해당 노드의 값인 2를 반환한다.
이러한 방식으로 모든 탐색을 마치고 나면 다음과 같은 형태가 된다.
이러한 방식으로 구간의 합을 구할 수 있다.
세그먼트 트리는 구현에 약간의 어려움이 있을 수 있으므로 이후 유사 문제를 풀게 될 경우 코드에 대한 해설을 올리도록 하겠다.
code
GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지
알고리즘 온라인 저지. Contribute to YoungWoo93/algorithmOnlineJudge development by creating an account on GitHub.
github.com
'알고리즘 온라인 저지 > BOJ' 카테고리의 다른 글
| BOJ 7576 토마토 (0) | 2022.02.10 |
|---|---|
| BOJ 11054 가장 긴 바이토닉 부분 수열 (0) | 2022.02.10 |
| BOJ 16964 DFS 스페셜 저지 (0) | 2022.02.03 |
| BOJ 1463 1로 만들기 (0) | 2022.01.30 |
| BOJ 1339 단어 수학 (0) | 2022.01.30 |
