[백준] 1749 점수따먹기 (누적합, 카데인 알고리즘)

park geonwoo·2024년 9월 19일

목록 보기

8/32

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

풀이

이 문제는 2차원 행렬에서 가장 큰 합을 갖는 부분 행렬을 구하는 문제입니다. 주어진 행렬에서 적절한 부분 행렬을 찾아서 그 안에 있는 원소들의 합이 최대가 되는 값을 출력해야 합니다. 이 문제는 부분 배열에서의 최대 합을 찾는 카데인 알고리즘(Kadane's Algorithm)을 확장한 2차원 버전으로 해결할 수 있습니다.

해결 전략

부분합:
- 2차원 배열에서 최대 합을 가지는 부분 행렬을 찾아야 합니다. 이를 위해 부분 배열에서 최대 합을 찾는 알고리즘을 적용할 수 있습니다.
- 먼저 2차원 배열을 1차원 배열의 형태로 변환하고, 각 행이나 열에 대한 합을 계산하면서 카데인 알고리즘을 적용하여 최대 부분 합을 구하는 방법을 사용합니다.
2차원 카데인 알고리즘:
- 각 열의 구간을 설정한 후, 이 구간에 해당하는 열들의 값을 합하여 1차원 배열로 변환합니다.
- 이 1차원 배열에서 카데인 알고리즘을 사용해 최대 부분 배열 합을 계산합니다.
카데인 알고리즘:
- 주어진 배열에서 연속된 부분 배열 중 최대 합을 구하는 알고리즘입니다. 이는 O(n) 시간 복잡도로 구할 수 있습니다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 행렬의 크기 N (행), M (열) 입력 받기
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 행렬 입력 받기
        int[][] matrix = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 최대 합을 저장할 변수 (초기 값은 아주 작은 음수)
        int maxSum = Integer.MIN_VALUE;

        // 열 구간을 정해서 1차원 배열로 변환하여 최대합 구하기
        for (int left = 0; left < M; left++) {
            int[] temp = new int[N];  // 각 열 구간에 대한 임시 배열

            for (int right = left; right < M; right++) {
                // 열 구간 (left ~ right)에 대한 합을 temp에 저장
                for (int i = 0; i < N; i++) {
                    temp[i] += matrix[i][right];
                }

                // 1차원 배열에서 최대 부분합 구하기 (카데인 알고리즘)
                int currentMax = kadane(temp);
                maxSum = Math.max(maxSum, currentMax);
            }
        }

        // 결과 출력
        System.out.println(maxSum);
    }

    // 카데인 알고리즘: 1차원 배열에서 최대 부분합을 구하는 함수
    public static int kadane(int[] arr) {
        int maxEndingHere = arr[0];
        int maxSoFar = arr[0];

        for (int i = 1; i < arr.length; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }
}

코드 설명

입력 처리:
- 행렬의 크기 N(행)과 M(열)을 입력받고, matrix[N][M] 배열에 행렬의 값을 저장합니다.
부분합 계산:
- 왼쪽 열부터 오른쪽 열까지의 구간을 설정하고, 이 구간에 해당하는 열들의 값을 합쳐 1차원 배열로 변환합니다. 이 과정을 통해 left부터 right 열까지의 값을 모두 합한 부분 배열을 만듭니다.
- 예를 들어, left = 0, right = 1일 때, 0번 열과 1번 열을 더한 1차원 배열이 생성됩니다.
카데인 알고리즘 적용:
- 구간을 정한 후, 그 구간의 합으로 만든 1차원 배열에 대해 카데인 알고리즘을 적용하여 최대 부분 배열 합을 구합니다.
- 카데인 알고리즘은 각 위치에서의 최대 부분 배열 합을 구하면서 전체 최대 합을 갱신해 나가는 방식입니다.
최종 결과 출력:
- 전체 구간에 대해 반복적으로 최대 합을 갱신하며, 최종적으로 최대 합을 출력합니다.

시간 복잡도 분석

이중 반복문 (left와 right):
- left는 0부터 M-1까지, right는 left부터 M-1까지 반복되므로, 열 구간을 선택하는 과정의 시간 복잡도는 O(M^2)입니다.
카데인 알고리즘 적용:
- 각 구간에서 temp[] 배열에 대해 카데인 알고리즘을 적용하는데, 이 과정의 시간 복잡도는 O(N)입니다. (행의 크기만큼 처리)
최종 시간 복잡도:
- 전체 알고리즘의 시간 복잡도는 O(M^2 * N)입니다.
- 최대 N = 200, M = 200일 때, 최악의 경우 200^2 * 200 = 8,000,000 연산이므로 제한 시간 내에 충분히 해결할 수 있습니다.

공간 복잡도 분석

행렬 저장 공간:
- 행렬을 저장하기 위해 O(N * M) 공간이 필요합니다.
임시 배열:
- 열 구간에 대한 합을 저장하는 temp[] 배열은 크기가 N이므로, 추가로 O(N)의 공간이 필요합니다.

사용된 알고리즘 및 자료구조

카데인 알고리즘:
- 1차원 배열에서 최대 부분 배열 합을 구하는 데 사용됩니다. 이 문제에서 2차원 배열을 1차원 배열로 변환한 후 적용됩니다.
2차원 배열 구간합:
- 열 구간을 선택한 후, 각 열 구간에 대해 구간합을 구하는 방식으로 2차원 배열 문제를 1차원 배열 문제로 변환하여 해결합니다.

추가 설명

카데인 알고리즘(Kadane's Algorithm)이란?

카데인 알고리즘은 연속된 부분 배열에서 최대 합을 구하는 효율적인 알고리즘입니다. 1차원 배열에서 연속된 숫자들의 부분 배열 중에서, 그 합이 가장 큰 배열을 찾는 문제를 해결합니다. 이 알고리즘은 동적 계획법(DP)의 아이디어를 기반으로, 배열을 한 번 순회하면서 최대 부분 배열 합을 구할 수 있습니다.

문제 정의

주어진 배열 arr에서, 연속된 부분 배열의 합 중 최대값을 구하는 문제입니다.

예를 들어, 배열 arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]가 있다고 할 때, 이 배열의 최대 부분합을 갖는 부분 배열은 [4, -1, 2, 1]이며, 그 합은 6입니다.

카데인 알고리즘의 동작 원리

카데인 알고리즘은 배열의 각 요소를 차례대로 살펴보면서, 현재 요소를 포함한 부분 배열에서의 최대 합을 갱신해 나가는 방식입니다.

초기 설정:
- 배열에서 첫 번째 원소를 최대 합으로 설정합니다. 즉, 처음에 maxSoFar = arr[0]입니다.
- 첫 번째 원소부터 시작하는 부분 배열의 합을 maxEndingHere라는 변수에 저장합니다.
순차적으로 배열을 탐색:
- 각 배열의 원소 arr[i]에서:
  - 현재까지의 최대 부분 배열 합인 maxEndingHere에 arr[i]를 더한 값과 arr[i] 중 더 큰 값을 maxEndingHere로 갱신합니다. 이 과정에서, 기존의 부분 배열을 계속 이어가는 것이 더 나은지, 아니면 현재 위치에서 새로운 부분 배열을 시작하는 것이 나은지를 결정합니다.
- 매번 최대 합을 maxSoFar에 저장하며, maxSoFar와 maxEndingHere를 비교해 더 큰 값으로 갱신합니다.
최종 결과:
- 배열을 모두 순회한 후, maxSoFar가 최종적으로 최대 부분 배열 합을 가지는 값이 됩니다.

public int kadane(int[] arr) {
    // 배열의 첫 번째 원소로 초기화
    int maxEndingHere = arr[0];
    int maxSoFar = arr[0];

    // 배열의 두 번째 원소부터 순회
    for (int i = 1; i < arr.length; i++) {
        // 현재 원소를 포함한 최대합을 계산 (계속 이어가거나 새로운 시작)
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        
        // 현재까지의 최대 부분 배열 합을 갱신
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;  // 최대 부분 배열 합을 반환
}

예시

배열 arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]에 대해 카데인 알고리즘을 적용해보겠습니다.

초기 상태:
- maxEndingHere = arr[0] = -2
- maxSoFar = arr[0] = -2
첫 번째 반복 (i = 1):
- maxEndingHere = max(1, -2 + 1) = 1
- maxSoFar = max(-2, 1) = 1
두 번째 반복 (i = 2):
- maxEndingHere = max(-3, 1 + (-3)) = -2
- maxSoFar = max(1, -2) = 1
세 번째 반복 (i = 3):
- maxEndingHere = max(4, -2 + 4) = 4
- maxSoFar = max(1, 4) = 4
네 번째 반복 (i = 4):
- maxEndingHere = max(-1, 4 + (-1)) = 3
- maxSoFar = max(4, 3) = 4
다섯 번째 반복 (i = 5):
- maxEndingHere = max(2, 3 + 2) = 5
- maxSoFar = max(4, 5) = 5
여섯 번째 반복 (i = 6):
- maxEndingHere = max(1, 5 + 1) = 6
- maxSoFar = max(5, 6) = 6
일곱 번째 반복 (i = 7):
- maxEndingHere = max(-5, 6 + (-5)) = 1
- maxSoFar = max(6, 1) = 6
여덟 번째 반복 (i = 8):
- maxEndingHere = max(4, 1 + 4) = 5
- maxSoFar = max(6, 5) = 6

최종적으로, 최대 부분 배열 합은 6이 됩니다.

시간 복잡도

카데인 알고리즘은 배열을 한 번만 순회하면서 최대 부분 배열 합을 찾기 때문에, 시간 복잡도는 O(n)입니다. 여기서 n은 배열의 크기입니다. 이는 매우 효율적인 알고리즘입니다.

공간 복잡도

카데인 알고리즘은 배열을 순차적으로 처리할 때, 추가적인 배열이나 데이터 구조가 필요 없고 단지 몇 개의 변수만 사용합니다. 따라서 공간 복잡도는 O(1)입니다.

요약

카데인 알고리즘은 1차원 배열에서 최대 부분 배열 합을 구하는 문제를 해결하는 효율적인 알고리즘입니다.
배열을 한 번 순회하면서 동적 계획법의 원리를 적용해 현재까지의 최대 부분 배열 합을 갱신해 나가는 방식입니다.
시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

2차원 -> 1차원

for (int left = 0; left < M; left++) {
    int[] temp = new int[N];  // 임시 배열로 각 행의 부분합을 저장
    for (int right = left; right < M; right++) {
        // 각 행의 부분합을 갱신
        for (int row = 0; row < N; row++) {
            temp[row] += arr[row][right];
        }

        // 카데인 알고리즘으로 temp 배열에서 최대 부분합 구하기
        int currentMax = kadane(temp);
        maxSum = Math.max(maxSum, currentMax);
    }
}

이 코드는 2차원 배열을 탐색하면서 특정 구간을 1차원 배열로 변환하고, 그 1차원 배열에서 카데인 알고리즘을 사용해 최대 부분합을 구하는 방식입니다.

핵심 아이디어

문제에서 우리는 2차원 행렬에서 부분 행렬을 찾고, 그 부분 행렬 내의 합이 가장 큰 값을 구하려고 합니다. 이를 효율적으로 처리하기 위해 2차원 문제를 1차원 문제로 변환하고 있습니다.

열 구간(left, right)을 설정:
- 이 코드는 두 개의 중첩된 반복문을 사용하여 행렬의 열 구간 left에서 right까지 선택합니다. left는 열 구간의 시작을, right는 끝을 나타냅니다.
1차원 배열로 변환 (temp 배열):
- 열 구간 left에서 right까지 선택한 열들을 합쳐서 1차원 배열을 만듭니다. 이 배열 temp[]는 열 구간에서 각 행의 합을 저장한 것입니다.
- 즉, 열 left부터 열 right까지의 합을 같은 행의 위치에서 모두 더한 값이 temp[]에 저장됩니다.

예시를 통한 설명

2  3 -21 -22 -23
5  6 -22 -23 -25
-22 -23  4   10  2

열 구간 선택

left = 0, right = 1 (열 0에서 열 1까지의 합을 구함):
- 첫 번째 행에서 2 + 3 = 5
- 두 번째 행에서 5 + 6 = 11
- 세 번째 행에서 22 + (-23) = -45
  
  이 구간에 대한 1차원 배열은 temp = [5, 11, -45].
이 1차원 배열에 대해 카데인 알고리즘을 적용하면, 연속된 부분 배열의 최대 합을 찾을 수 있습니다.

다음 열 구간 처리

left = 1, right = 2 (열 1에서 열 2까지의 합을 구함):
- 첫 번째 행에서 3 + (-21) = -18
- 두 번째 행에서 6 + (-22) = -16
- 세 번째 행에서 23 + 4 = -19
  
  이 구간에 대한 1차원 배열은 temp = [-18, -16, -19].
이 과정이 끝날 때마다 temp[]에 대해 최대 부분합을 구해, 전체 행렬에서 최대 부분 행렬 합을 찾습니다.

코드 설명

for (int left = 0; left < M; left++):
- left는 열의 시작 구간을 의미합니다.
int[] temp = new int[N];:
- temp[]는 N개의 행에 대해 선택된 열 구간에 대한 합을 저장하는 1차원 배열입니다.
for (int right = left; right < M; right++):
- right는 열의 끝 구간을 의미합니다. left부터 시작해 점차 열 구간을 확장합니다.
for (int row = 0; row < N; row++):
- 열 구간 left에서 right까지의 각 열의 값을 더해서, 각 행의 합을 temp[]에 저장합니다.
- 이 부분이 2차원 배열을 1차원 배열로 변환하는 핵심입니다. 같은 행의 값을 모두 더해 한 행의 값으로 만들고, 이를 temp[] 배열에 저장합니다.
카데인 알고리즘 적용:
- temp[]는 이제 열 구간에서 각 행의 합을 저장하고 있으므로, 카데인 알고리즘을 적용하여 이 1차원 배열에서 연속된 부분 배열의 최대 합을 찾습니다.

1차원으로 변환하는 이유

2차원 배열에서 부분 행렬을 구하려면 모든 가능한 부분 행렬을 탐색해야 하지만, 이는 비효율적입니다.
이를 해결하기 위해 열 구간을 고정하고 그 구간 내에서 각 행에 대해 더한 값을 1차원 배열로 변환한 후, 1차원 배열에서 최대 부분합을 구하는 방식으로 문제를 해결할 수 있습니다.
이렇게 하면 2차원 배열 문제를 효율적으로 해결할 수 있고, 전체 시간 복잡도를 크게 줄일 수 있습니다.

시간 복잡도 분석

열 구간 탐색: 두 개의 반복문이 열 구간 left와 right를 선택하므로 O(M^2)입니다.
각 열 구간에 대해 카데인 알고리즘 적용: 각 열 구간에 대해 N개의 행을 처리하며, 카데인 알고리즘을 적용하는 데 O(N)의 시간이 소요됩니다.

따라서 전체 시간 복잡도는 O(M^2 * N)입니다.

누적합(Summed Area Table, Prefix Sum)과 카데인 알고리즘(Kadane's Algorithm)에 대한 설명

1. 누적합 (Prefix Sum)

누적합은 배열의 부분 합을 빠르게 계산하기 위해 사용하는 기법입니다. 배열을 처리할 때, 특정 구간의 합을 구해야 할 때 그 구간의 합을 빠르게 계산할 수 있도록 미리 합을 계산하여 저장하는 방식입니다.

누적합의 동작 원리:

원본 배열의 각 원소에 대해 해당 위치까지의 합을 계산하여 저장합니다.
예를 들어, 배열 arr = [1, 2, 3, 4]의 누적합 배열 prefixSum은 [1, 3, 6, 10]이 됩니다.
배열의 특정 구간 [i, j]의 합은 prefixSum[j] - prefixSum[i-1]로 한 번에 계산할 수 있습니다.

시간 복잡도:

배열을 한 번 순회하여 누적합을 계산하는 데 O(n)의 시간이 걸립니다.
구간의 합을 구할 때, 시작점과 끝점을 한 번씩 참조하는 것만으로도 구간 합을 계산할 수 있으므로 O(1) 시간에 구간합을 구할 수 있습니다.

2. 카데인 알고리즘 (Kadane's Algorithm)

카데인 알고리즘은 연속된 부분 배열에서 최대 합을 구하는 알고리즘으로, 동적 계획법을 기반으로 동작합니다. 연속적인 배열 내에서 최대 합을 구할 때, 현재까지의 최대 합을 저장하고, 현재 원소를 추가할 때 계속 누적할지 아니면 새로운 배열을 시작할지를 결정하는 방식으로 최댓값을 구합니다.

카데인 알고리즘의 동작 원리:

배열을 왼쪽부터 오른쪽으로 순회하면서 현재 원소를 포함하는 최대 부분합을 계산합니다.
현재 원소를 포함할 때, 이전까지의 최대 합에 현재 원소를 더한 것과 현재 원소 그 자체 중 더 큰 값을 선택합니다.
배열 전체를 순회하면서 최대 합을 계속 갱신합니다.

시간 복잡도:

카데인 알고리즘은 배열을 한 번 순회하면서 최대 부분 배열 합을 구하기 때문에 O(n)의 시간이 소요됩니다.

차이점

비교 항목	누적합 (Prefix Sum)	카데인 알고리즘 (Kadane's Algorithm)
적용 범위	특정 구간의 합을 빠르게 계산하는 문제	연속된 부분 배열에서 최대 합을 구하는 문제
시간 복잡도	배열을 처리하는 데 O(n), 구간 합 구하는 데 O(1)	O(n), 배열을 한 번 순회
알고리즘 적용 대상	구간 합 계산 (특정 범위의 합이 자주 필요할 때)	최대 연속 부분 배열 합 계산
구간 합 계산	여러 구간 합을 반복적으로 계산할 때 유리	구간 합 자체는 계산하지 않음
메모리 사용	추가 배열(누적합 배열)이 필요	추가 메모리 사용 없음
부분 배열 연속성	비연속적인 구간 합 계산 가능	연속된 부분 배열만 처리

어떤 방식이 효율적인가?

두 알고리즘은 문제가 요구하는 특성에 따라 각각 다른 상황에서 효율적입니다.

구간 합을 자주 구하는 문제:
- 누적합이 더 적합합니다. 배열에서 구간합을 자주 구하는 문제에서는, 미리 누적합을 계산해 두고 구간합을 즉시 계산하는 방식이 효율적입니다. 한 번의 구간합 계산에 O(1)의 시간이 걸리기 때문에 여러 구간의 합을 빠르게 계산할 수 있습니다.
  
  예시: 배열에서 여러 구간의 합을 구하는 쿼리가 있을 때, 누적합을 사용하면 O(1) 시간에 답을 구할 수 있습니다.
연속된 부분 배열의 최대합 문제:
- 카데인 알고리즘이 더 적합합니다. 카데인 알고리즘은 연속된 부분 배열에서 최대 합을 구하는 문제를 효율적으로 해결할 수 있습니다. 배열을 한 번만 순회하면 바로 결과를 얻을 수 있기 때문에 매우 효율적입니다.
  
  예시: "연속된 부분 배열"에서 최대 합을 구해야 할 때는 카데인 알고리즘이 O(n)의 시간 복잡도로 해결할 수 있는 최적의 방법입니다.

2차원 배열에서의 차이점

2차원에서 누적합 적용:
- 2차원 구간 합을 구할 때도 누적합을 사용할 수 있습니다. 이를 2차원 Prefix Sum이라고 부릅니다.
- 각 구간에 대해 빠르게 구간합을 계산할 수 있지만, 비연속적인 구간도 다룰 수 있습니다.
- 구간 [r1, c1]에서 [r2, c2]까지의 합을 계산하는 경우:

sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1];

2차원에서 카데인 알고리즘 적용:

카데인 알고리즘은 연속된 부분 배열에서 최대 합을 구하는 데 최적화되어 있습니다. 2차원 배열에서도 특정 열 구간을 선택하고 그 구간을 1차원 배열로 변환한 후, 카데인 알고리즘을 적용하여 연속된 부분 행렬의 최대 합을 구하는 방식으로 확장할 수 있습니다.
구간이 반드시 연속적이어야 하므로, 비연속적인 구간에 대해서는 사용할 수 없습니다.

결론

누적합은 특정 구간의 합을 반복적으로 구해야 하는 문제에서 효율적입니다. 예를 들어 여러 구간에 대한 합을 빠르게 구하는 문제에서는 매우 유리합니다.
카데인 알고리즘은 연속된 부분 배열에서 최대 합을 구하는 데 가장 적합합니다. 연속된 구간에서 최대 합을 구하는 문제에서는 최적의 알고리즘입니다.

따라서 문제의 특성에 따라 누적합과 카데인 알고리즘 중 하나를 선택하는 것이 중요합니다. 구간 합을 구하는 문제가 아니고, 연속된 부분 배열의 최대 합을 구하는 문제라면 카데인 알고리즘이 훨씬 효율적입니다.

park geonwoo

이전 포스트

[백준] 31848 엉성한 도토리 분류기 (이진탐색)

다음 포스트

[백준] 1749 점수따먹기 (누적합, 카데인 알고리즘)

코딩테스트

풀이

해결 전략

코드 설명

시간 복잡도 분석

공간 복잡도 분석

사용된 알고리즘 및 자료구조

추가 설명

카데인 알고리즘(Kadane's Algorithm)이란?

문제 정의

카데인 알고리즘의 동작 원리

예시

시간 복잡도

공간 복잡도

요약

2차원 -> 1차원

핵심 아이디어

예시를 통한 설명

열 구간 선택

다음 열 구간 처리

코드 설명

1차원으로 변환하는 이유

시간 복잡도 분석

누적합(Summed Area Table, Prefix Sum)과 카데인 알고리즘(Kadane's Algorithm)에 대한 설명

1. 누적합 (Prefix Sum)

누적합의 동작 원리:

시간 복잡도:

2. 카데인 알고리즘 (Kadane's Algorithm)

카데인 알고리즘의 동작 원리:

시간 복잡도:

차이점

어떤 방식이 효율적인가?

2차원 배열에서의 차이점

결론

[백준] 31848 엉성한 도토리 분류기 (이진탐색)

[백준] 30456번 바닥수

0개의 댓글