백준 2042 구간 합 구하기 - JAVA

2042 문제 링크

---

https://www.acmicpc.net/problem/2042

 

문제 설명

---

 

입출력

---

 

코드

---

<세그먼트 트리 풀이>

import java.io.*;
import java.util.*;
 
public class Main {
    private static long[] arr;
    private static long[] tree;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); 
        int M = Integer.parseInt(st.nextToken()); // 변경
        int K = Integer.parseInt(st.nextToken()); // 구간 합
        
        arr = new long[N];
        tree = new long[getTreeSize(N)]; // 세그먼트 트리
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        } 
        initTree(1, 0, N - 1);
        int T = M + K;
        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());
            
            if (a == 1) {
                update(1, 0, N - 1, b - 1, c);
            } else if (a == 2) {
                sb.append(query(1, 0, N - 1, b - 1, c - 1) + "\n");
            }
        }
        bw.write(sb.toString());
        bw.flush();
    }
    private static int getTreeSize(int N) {
        int size = 1;
        while (size < N) size *= 2;  // N 이상의 2의 거듭제곱 찾기
        return size * 2;             // 전체 트리 크기
    }
    private static long initTree(int node, int start, int end) {
        if (start == end) return tree[node] = arr[start];
        int mid = (start + end) / 2;
        long leftSum = initTree(node * 2, start, mid);
        long rightSum = initTree(node * 2 + 1, mid + 1, end);
        return tree[node] = leftSum + rightSum;
    }
    private static void update(int node, int start, int end, int idx, long num) {
        if (idx < start || idx > end) return;
        if (start == end){ // 원본 배열 변경 및 리프 노드 변경
            arr[idx] = num;
            tree[node] = num;
            return;
        } 
        int mid = (start + end) / 2;
        update(node * 2, start, mid, idx, num);
        update(node * 2 + 1, mid + 1, end, idx, num);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    private static long query(int node, int start, int end, int left, long right) {
        if (right < start || end < left) return 0;
        if (left <= start && end <= right) {
            return tree[node];
        } 
        int mid = (start + end) / 2;
        long leftSum = query(node * 2, start, mid, left, right);
        long rightSum = query(node * 2 + 1, mid + 1, end, left, right);
        return leftSum + rightSum;
    }
}

 

<선형 탐색 풀이>

import java.io.*;
import java.util.*;
 
public class Main {
    private static long[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); 
        int M = Integer.parseInt(st.nextToken()); // 변경
        int K = Integer.parseInt(st.nextToken()); // 구간 합
        
        arr = new long[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        } 
        int T = M + K;
        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());
            
            if (a == 1) {
                changeNum(b, c);
            } else if (a == 2) {
                sb.append(addSum(b, c) + "\n");
            }
        }
        bw.write(sb.toString());
        bw.flush();
    }
    private static void changeNum(int b, long c) {
        arr[b - 1] = c;
    }
    private static long addSum(int b, long c) {
        long result = 0;
        for (int i = b - 1; i < c; i++) {
            result += arr[i];
        } 
        return result;
    }
}

 

알고리즘 설명

---

해당 문제는 각 입력에 맞추어 합을 계산하는 선형 탐색 풀이로도 통과할 수 있는 문제입니다. 하지만 결과를 보면 선형 탐색 시간의 풀이는 그리 효과적이지 못하다는 것을 알 수 있습니다.

선형 탐색 풀이의 시간 복잡도는 O(N)로, 배열의 길이가 길고 값 갱신이 많아지는 경우, 구간합을 구하는 데에 많은 시간이 소요됨을 알 수 있습니다. 따라서, 갱신되지 않는 구간의 합을 미리 계산해놓고, 값이 갱신되는 원소에 의해서 구간합이 변경되는 부분만 새로운 값으로 채워넣어주는 세그먼트 트리 방식으로 풀이를 진행하는 것이 효율적인 풀이라고 할 수 있습니다.

해당 문제에서는 값의 갱신이 빈번할 수 있으므로, 누적합을 계산해놓고, 구간합을 구하는 방식인 누적합 풀이는 제외하였습니다.

 

배열 [1, 2, 3, 4, 5]을 기준으로 선형 탐색 풀이와 세그먼트 트리 풀이의 차이를 간단하게 설명드리겠습니다.

1. 선형 탐색 풀이 시간 복잡도

• 구간 합을 구하려면 매번 해당 구간을 전부 순회해야 합니다.
• 예를 들어 [2,5] 구간 합을 구한다면 → 2 + 3 + 4 + 5 = 14 → O(N) 소요.
• 또 다른 구간 [1,3] 합을 구할 때는 → 1 + 2 + 3 = 6 → 다시 처음부터 더해야 함.
• a가 2인 경우 즉, 매 구간합 계산마다 길이만큼 직접 계산해야 해서 구간합이 많아질수록 시간이 기하급수적으로 커집니다.

2. 세그먼트 트리 풀이 시간 복잡도

• 미리 트리를 만들어 구간 합을 저장해둡니다.
• [2,5] 구간 합을 구할 때는 필요한 구간만 더해서 O(logN)으로 계산합니다.
• 만약 arr[2] = 2 → 10 으로 값이 바뀌어도, 세그먼트 트리는 그 값이 속한 경로(리프노드 ~ 루트노드)만 갱신하면 되므로 O(logN) 안에 업데이트 가능.

세그먼트 트리의 구현에 대해 더 깊게 알고 싶은 분들은 아래 위키백과 링크 참고바랍니다.

세그먼트 트리

 

선형 탐색 풀이

세그먼트 트리 풀이

위의 결과에서도 볼 수 있듯이, 주어진 문제처럼 원소의 갱신이 빈번할 경우, 선형 탐색 풀이 대비 세그먼트 트리 풀이가 시간적으로도 효율적이라는 것을 알 수 있습니다.

 

메서드 및 코드 해석

---

세그먼트 트리 풀이를 기준으로, 각 메서드를 해석해보겠습니다.

먼저, getTreeSize() 메서드입니다.

private static int getTreeSize(int N) {
    int H = (int) Math.ceil(Math.log(N) / Math.log(2));
    return (int) Math.pow(2, H + 1);
}

세그먼트 트리는 완전 이진트리 구조를 사용하기 때문에, 배열 [1, 3, 7, 9, 11]의 경우 세그먼트 트리는 아래 그림과 같고, 루트노드를 포함해 최소 4의 높이를 가지는 것을 알 수 있습니다.

세그먼트 트리 배열의 크기를 안전하게 잡기 위해, 배열 크기 N을 기준으로 log2(N)을 이용해 필요한 트리 높이 H를 계산하고, 이를 바탕으로 2^(H+1)을 세그먼트 트리 배열 크기로 설정합니다. 이렇게 하면 리프 노드 수와 내부 노드를 모두 포함하면서 완전 이진트리 구조를 유지할 수 있게됩니다.

💡완전 이진트리(Complete Binary Tree)
• 모든 레벨(level)이 꽉 차 있어야 하는 것은 아님
      ◦ 마지막 레벨만 왼쪽부터 채워져야 함
      ◦ 나머지 레벨은 모두 꽉 차 있어야 함
• 리프 노드를 제외한 모든 노드는 2명의 자식을 가져야 함
      ◦ 리프 노드는 당연히 자식이 없음

---

다음은 initTree() 메서드입니다.

private static long initTree(int node, int start, int end) {
    if (start == end) return tree[node] = arr[start];
    int mid = (start + end) / 2;
    long leftSum = initTree(node * 2, start, mid);
    long rightSum = initTree(node * 2 + 1, mid + 1, end);
    return tree[node] = leftSum + rightSum;
}

배열의 0번째 위치를 제외하고 1번째 위치부터 사용합니다. (node 변수에 1 대입)

initTree()는 재귀적으로 트리를 순회하며 각 노드에 구간 합을 저장합니다. 먼저, 리프 노드에 도달하면 해당 위치에 원본 배열 값을 그대로 저장하고, 리프 노드가 아닌 경우에는 왼쪽과 오른쪽 자식을 재귀적으로 초기화한 뒤, 현재 노드에는 왼쪽과 오른쪽 자식의 합을 저장합니다.

이 과정을 통해 루트 노드에는 전체 배열의 합이 저장되고, 각 내부 노드에는 자신이 담당하는 구간의 합이 저장됩니다.

 

배열 [1, 2, 3, 4, 5]를 예로 들어 설명하면, 세그먼트 트리 배열은 0번째 위치를 제외하고 1번째 위치부터 사용하며, 루트 노드를 나타내는 node 변수에는 1이 대입됩니다. 초기 호출은 initTree(1, 0, 4)로, 배열 전체 [0~4]를 루트 노드가 담당합니다.

initTree(1, 0, 4)의 왼쪽 자식 노드 호출하면 initTree(2, 0, 2), 더 안쪽 왼쪽 자식을 호출하면 initTree(4, 0, 1), 더 안쪽 왼쪽 자식을 호출하면 initTree(8, 0, 0)으로 start == end 조건을 만족하여 세그먼트 트리 배열의 8번째에 arr[0]이 들어가게 되고, 종료됩니다.

위의 간단한 예시와 같이 각 루트노드들과 리프노드들이 자리를 찾아 세그먼트 트리 배열에 전부 삽입되게 됩니다.

---

다음은 update() 메서드입니다.

private static void update(int node, int start, int end, int idx, long num) {
    if (idx < start || idx > end) return;
    if (start == end){ // 원본 배열 변경 및 리프 노드 변경
        arr[idx] = num;
        tree[node] = num;
        return;
    } 
    int mid = (start + end) / 2;
    update(node * 2, start, mid, idx, num);
    update(node * 2 + 1, mid + 1, end, idx, num);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

이 메서드는 배열의 특정 인덱스 값을 변경하고, 세그먼트 트리 배열에서 변경된 원소와 관련된 구간 합을 갱신하는 역할을 합니다.

먼저, 변경하려는 인덱스 idx가 현재 노드가 담당하는 구간 [start, end]에 속하지 않으면 아무 작업도 하지 않고 반환합니다.

리프 노드에 도달하면 start == end 조건을 만족하므로, 원본 배열의 값을 새로운 값으로 바꾸고, 해당 리프 노드의 값도 트리에 반영합니다.

리프 노드가 아닌 경우에는 중간 위치 mid = (start + end)/2를 기준으로 왼쪽과 오른쪽 자식 노드에 재귀적으로 update()를 호출합니다.

재귀 호출이 끝나면 현재 노드에는 왼쪽과 오른쪽 자식 노드 값의 합을 저장하여, 구간 합이 올바르게 갱신되도록 합니다.

---

다음은 마지막으로 주어진 구간합을 구하는 query() 메서드입니다.

private static long query(int node, int start, int end, int left, long right) {
    // 리프 노드까지 내려갔는데, 요청 구간과 겹치지 않으면 0 반환 (구간합에서 제외)
    if (right < start || end < left) return 0;
    if (left <= start && end <= right) {
	// 완전 포함 시, 해당 노드의 리프노드까지 전부 구간에 포함되므로 해당 노드의 값을 반환
        return tree[node];
    } 
    int mid = (start + end) / 2;
    long leftSum = query(node * 2, start, mid, left, right);
    long rightSum = query(node * 2 + 1, mid + 1, end, left, right);
    return leftSum + rightSum;
}

먼저, 현재 노드가 담당하는 구간 [start, end]가 요청한 구간과 아예 겹치지 않으면 0을 반환합니다. 현재 구간이 요청한 구간을 완전히 포함하고 있다면, 해당 노드에 저장된 구간 합을 바로 반환합니다.

그 외의 경우, 현재 구간과 요청 구간이 부분적으로 겹치는 경우에는 중간 위치 mid = (start + end)/2를 기준으로 왼쪽과 오른쪽 자식 노드에 재귀적으로 query()를 호출합니다.

왼쪽과 오른쪽에서 반환된 합을 더해서 현재 구간 합을 계산하고, 최종적으로 루트 호출에서 전체 요청 구간 합을 반환합니다.