DP - 구간 합 빠르게 계산하기

DP(Dynamic Programming) 기법
해결한 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 캐싱 기법을 활용하여 문제의 시간 복잡도를 줄이는 문제 해결 기법.
-> PrefixSum (배열의 맨앞부터 특정 위치까지의 합을 미리 기록)
접두사 합을 이용한 알고리즘을 응용한다.

✅ 문제

• N개의 정수로 구성된 수열이 있다.
• M개의 쿼리(Query) 정보가 주어진다.
  • 각 쿼리는 left와 right으로 구성된다.
  • 각 쿼리에 대하여 [left,right] 구간에 포함된 데이터들의 합을 출력
• 수행시간의 제한은 O(N + M) 이다. (선형 탐색의 반복 O(N * M)은 안됨)

💻 코드

import java.util.*;

public class TwoPointer
{
    public static int n = 5; // 데이터의 개수 N과 데이터 입력 받기
    public static int arr[] = {10, 20, 30, 40, 50};
    public static int[] prefixSum = new int[arr.length + 1];

    public static void main(String[] args)
    {
        // 접두사의 합(Prefix Sum) 배열 계산
        int sumValue = 0;

        for (int i = 0; i < n; i++)
        {
            sumValue += arr[i];
            prefixSum[i + 1] = sumValue;
        }

        // 구간 합 계산 (예시 : 3번째 수부터 4번째 수까지)
        int left = 3;
        int right = 4;
        System.out.println(prefixSum[right] - prefixSum[left - 1]);
    }
}

📝 정리