BOJ 1912 - 연속합 ( 완전탐색, Prefix Sum, DP)

www.acmicpc.net/problem/1912

1912번: 연속합

연속합 문제를 3가지 방식으로 풀어보겠습니다.

1. 완전탐색

말 그대로 전체 배열을 돌면서 모든 경우의 수를 탐색합니다. 시간복잡도는 O(n^3)으로 문제를 제출하면 시간초과가 발생합니다.

import java.util.Scanner;

public class boj1912 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N+1];

        for(int i=1; i<=N; i++){
            arr[i] = sc.nextInt();
        }

        // 1. 완전 탐색
        int max=0;

        for(int i=1; i<=N; i++){
            max = -987654321;
            for(int start = 1; start<=N; start++){
                for(int end = start; end<=N; end++){
                    int total = 0;
                    for(int k=start; k<=end; k++){
                        total += arr[k];
                    }
                    max = Math.max(total,max);
                }
            }
        }
        
        System.out.println(max);

    }
}

 

2. Prefix SUM

Prefix SUM을 활용하는 방법입니다. Prefix SUM 이란 arr[i]에 1~i 까지의 합을 저장해 놓은 배열을 생성하는 방법입니다. 차분하게 생각을 해보면 arr[i] = arr[i-1] + a로 생각해볼 수 있습니다. 그러므로 아래와 같은 식을 세울 수 있습니다.

for(int i=1; i<=N; i++){
    arr[i] = arr[i-1] + a
}
O(n)의 시간복잡도로 각 배열의 index 까지의 합을 구해볼 수 있었는데, 이 배열을 통해 각 구간의 합을 구하는 방법이 있습니다.

arr[3] ~ arr[7] 까지의 구간의 합은 arr[7] - arr[2]로 나타낼 수 있습니다. 이러한 방법을 활용한다면 각 구간의 최대 합을 수월하게 구할 수 있습니다.

아래의 코드는 O(n^2) 의 시간 복잡도를 가지게 되는데 문제에서 주어진 시간제한은 1초이고 최대 N의 크기는 100,000이므로 시간초과가 발생합니다.

O(n^2)은 100,000 * 100,000 = 10,000,000,000으로 100억입입니다. 컴퓨터의 평균적인 연산은 1초에 1억번으로 100초가 걸리니까 시간초과가 발생하겠습니다.

 

import java.util.Scanner;

public class boj1912 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N+1];

        for(int i=1; i<=N; i++){
            arr[i] = sc.nextInt();
        }

        // 2. prefix Sum
        int[] dp = new int[N+1];
        dp[0] = 0;
        for(int i=1; i<=N; i++){
            dp[i] = dp[i-1] + arr[i];
        }
        int max = -987654321;
        for(int start=1; start <= N; start++){
            for(int end=start; end <= N; end++){
                max = Math.max(max, dp[end] - dp[start-1]);
            }
        }

        System.out.println(max);

    }
}

3. DP

마지막 방법은 다이나믹 프로그래밍을 이용하는 것입니다. 바텀 업 방식으로 점화식을 작성하면 O(n)의 방법으로 정답을 도출할 수 있습니다.

dp[i]를 i번째 항까지 진행되었을 때의 연속된 수열의 최대 합이라고 생각해봅니다.
저는 dp 문제를 풀 때, dp[0] = 0으로 초기화하고 N까지를 묻는 문제라면 index를 1부터 ~ N까지로 지정해서 사용합니다. 그러므로 dp[0] = 0으로 초기화 한 후에 dp[1]부터 계산합니다.

dp[1] = dp[0] + K ( K는 K번째 수열)
dp[2] = dp[1] + K
dp[3] = dp[2] + K

이렇게만 세워서 정답을 구할 수 있다면 정말 좋겠지만... 이 주어진 수열은 음의 정수도 포함하고 있습니다. 그렇기 때문에 음의 정수의 경우 더하게 되면 우리는 연속된 수열의 최대 합을 구해야 하는데 음의 정수를 더하게 되면 빼는 것과 같으므로 i번쨰 항까지의 합이 마이너스가 될 수 있는 상황이 발생합니다.

ex) 1, 2, -4 의 3가지 수열이 주어진 상황입니다.
dp[1] = 1
dp[2] = 1 + 2
dp[3] = 1 + 2 - 4
음의 정수를 더하게 되는 상황이 발생하므로 dp[3]은 연속된 수열의 최대 합으로 정의했음에도 불구하고 dp[2]보다 작은 숫자를 가지게 되는 상황이 발생하고 1~2까지의 구간의 합 > 1~3까지의 구간이 합이라고 생각해야 합니다.

그렇기 때문에 우리는 구현을 위해 특정한 조건을 걸어줘야 하는데 만약 dp[i-1]의 값이 0보다 작은 수를 가지게 된다면 dp[i-1]의 값을 더하는게 아닌 0을 더면서 그 수열부터 새롭게 최대 합을 찾는 방식을 사용해야 합니다.

즉 dp[i] = Math.Max(0, dp[i-1]) + K (K는 K번째 수열)의 점화식을 세울 수 있습니다. 

알고리즘 문제를 계속해서 풀어갈수록 느끼는 점이 있습니다.. 바로 노트를 적극적으로 사용하고 어떤 순으로 풀어나갈지 머리로만 생각하는 것이 아닌 순서를 작성해나가면서 계획성 있게 푸는 것입니다. 저는 아직 많이 부족하지만 느리더라도 꾸준하게 습관을 들여볼 생각입니다.

import java.util.Scanner;

public class boj1912 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N+1];

        for(int i=1; i<=N; i++){
            arr[i] = sc.nextInt();
        }

        
		// 3. dp
        int[] dp = new int[N+1];
        dp[0] = 0;
        int max = -987654321;
        for(int i=1; i<=N; i++){
            dp[i] = Math.max(0, dp[i-1]) + arr[i];
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);


    }
}

 

출처 : blog.encrypted.gg/737?category=773649