문제 링크
https://www.acmicpc.net/problem/2042
풀이
0. 문제 해석
N개의 숫자가 주어지고, M번의 숫자 변경과 K번의 구간 합 구하기 연산을 처리해야 하는 문제다. 수의 개수 N은 최대 1,000,000개, 수의 변경 횟수 M은 최대 10,000번, 구간 합을 구하는 횟수 K는 최대 10,000번이다. 입력되는 수와 연산의 개수가 많으므로, 각 연산을 매우 효율적으로 처리해야 시간 초과를 피할 수 있다.
1. 접근 방법
문제의 핵심은 값의 변경과 구간 합 계산이라는 두 가지 연산을 빠르게 수행하는 것이다.
- 단순 배열 순회: 값 변경은 O(1)이지만, 구간 합 계산 시 최악의 경우 N개의 원소를 모두 더해야 하므로 O(N)의 시간 복잡도를 가진다. M+K번의 연산을 수행하면 전체 시간 복잡도는 O((M+K) * N)이 되어 시간 초과가 발생한다.
- 누적 합 (Prefix Sum): 누적 합 배열을 미리 만들어두면 특정 구간의 합은 O(1)에 계산할 수 있다. 하지만 배열의 값이 한 번 변경되면, 그 이후의 모든 누적 합 값을 다시 계산해야 하므로 O(N)의 시간이 소요된다. 이 역시 비효율적이다.
두 연산 모두 빠른 시간 안에 처리하기 위해서는 O(log N) 수준의 시간 복잡도를 갖는 자료구조가 필요하다. 대표적으로 세그먼트 트리(Segment Tree)와 펜윅 트리(Fenwick Tree, 또는 Binary Indexed Tree)가 있다. 이 풀이에서는 펜윅 트리를 사용하여 문제를 해결했다. 펜윅 트리는 세그먼트 트리에 비해 구현이 간단하고, 메모리를 더 적게 사용한다는 장점이 있다.
2. 사고 흐름
- N, M, K의 크기를 확인하고, O(N) 방식의 풀이는 불가능함을 인지한다.
- 펜윅 트리는 다음 두 가지 연산을 O(log N)에 수행할 수 있다.
update: 특정 인덱스의 값을 변경하고, 이와 관련된 구간 합 정보들을 갱신한다.sum: 1번 인덱스부터 특정 인덱스까지의 누적 합을 계산한다.
- 문제에서 요구하는
[b, c]구간의 합은 펜윅 트리의sum연산을 이용하여sum(c) - sum(b-1)으로 구할 수 있다. - 초기 배열의 값들을 이용하여 펜윅 트리를 구현하고, 이후 M+K개의 연산을 순서대로 처리한다.
a = 1(변경 연산):b번째 수를c로 변경한다. 원래arr[b]값과c의 차이(diff)를 계산하여update(b, diff)를 호출한다.a = 2(구간 합 연산):b부터c까지의 합을 구한다.query(b, c)즉,sum(c) - sum(b-1)의 결과를 출력한다.
3. 동작 방식
펜윅 트리 (Fenwick Tree)
펜윅 트리는 정수의 이진 표현을 활용하여 누적 합을 빠르게 계산하는 자료구조다. tree[i]는 특정 구간의 합을 저장하는데, 그 구간은 i의 이진 표현에서 마지막 1의 위치(Least Significant Bit, LSB)에 의해 결정된다. i & -i 연산은 LSB를 구하는 비트 마스킹 기법이다.
tree[i]가 저장하는 구간:(i - (i & -i) + 1)부터i까지의 합
update(idx, diff)
idx번째 수가diff만큼 변했을 때, 이 변경 사항을 트리에 전파하는 함수다.idx부터 시작하여i += (i & -i)연산을 통해 부모 노드에 해당하는 인덱스로 이동하며diff값을 더해준다.- 이 과정을 통해
idx를 포함하는 모든 구간 합 정보가 O(log N)의 시간 복잡도로 갱신된다.
sum(idx)
- 1번 인덱스부터
idx번 인덱스까지의 누적 합을 계산하는 함수다. idx부터 시작하여i -= (i & -i)연산을 통해 현재 구간의 합을 더하고, 다음 하위 구간으로 이동한다.- 예를 들어
sum(7)을 구하려면tree[7] + tree[6] + tree[4]를 계산하게 된다.i=7 (0111):result += tree[7]->i = 7 - (7&-7) = 6 (0110)i=6 (0110):result += tree[6]->i = 6 - (6&-6) = 4 (0100)i=4 (0100):result += tree[4]->i = 4 - (4&-4) = 0
- 이 과정 역시 O(log N)의 시간 복잡도를 가진다.
query(start, end)
start부터end까지의 구간 합을 구한다.sum(end)(1부터 end까지의 합)에서sum(start - 1)(1부터 start-1까지의 합)을 빼서 간단히 구현할 수 있다.
4. 코드
package BOJ2042;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class FenwickTree {
long[] tree;
public FenwickTree(int size) {
tree = new long[size + 1];
}
public void update(int idx, long diff) {
for (int i = idx; i < tree.length; i += (i & -i)) {
tree[i] += diff;
}
}
public long sum(int idx) {
long result = 0;
for (int i = idx; i > 0; i -= (i & -i)) {
result += tree[i];
}
return result;
}
public long query(int start, int end) {
return sum(end) - sum(start - 1);
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader([System.in](http://System.in)));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
long[] arr = new long[N + 1];
FenwickTree indexTree = new FenwickTree(N);
for (int i = 1; i <= N; i++) {
arr[i] = Long.parseLong(br.readLine());
indexTree.update(i, arr[i]);
}
for (int i = 1; i <= M + K; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// c는 update일때는 long, query일때는 int로 사용됨
long c = Long.parseLong(st.nextToken());
if (a == 1) {
//데이터 변경
indexTree.update(b, c - arr[b]);
arr[b] = c;
} else if (a == 2) {
System.out.println(indexTree.query(b, (int)c));
}
}
}
}
컴퓨터소프트웨어공학과 학부생입니다