[백준 알고리즘] Q1912 부분합 - 카데인 알고리즘

1. Java 구현

 (1) 모든 경우의 수를 적용 - 시간초과 (시간복잡도 O(n^3)) → 실패

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

public class Solution {

	public static void solution1() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		int index = 0;
		while (st.hasMoreTokens())
			arr[index++] = Integer.parseInt(st.nextToken());

		int sum = 0;
		int max = 0;
		// 1개, 2개, 3개 ... n개 고른다!
		for (int i = 1; i <= arr.length; i++) {
			// 0번 인덱스부터 인접한 i개씩 고른다!
			for (int j = 0; j < arr.length - i + 1; j++) {
				sum = 0;
				for (int k = j; k < j + i; k++) {
					sum += arr[k];
				}
				max = max > sum ? max : sum;
			}
		}

		bw.write(max + "\n");
		bw.close();
		br.close();

	}
}

 

 (2) 위에 방식을 개선 - 시간초과 (시간복잡도 O(n^2)) → 실패

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

public class Solution {

	public static void solution1() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		int index = 0;
		while (st.hasMoreTokens())
			arr[index++] = Integer.parseInt(st.nextToken());

		int sum = 0;
		int max = 0;
		// 1개, 2개, 3개 ... n개 고른다!
		for (int i = 1; i <= arr.length; i++) {
			// 0번 인덱스부터 인접한 i개씩 고른다!
			for (int j = 0; j < arr.length - i + 1; j++) {
				sum = 0;
				for (int k = j; k < j + i; k++) {
					sum += arr[k];
				}
				max = max > sum ? max : sum;
			}
		}

		bw.write(max + "\n");
		bw.close();
		br.close();

	}
}

 (3) 카데인 알고리즘 적용 (시간복잡도 O(n)) → 성공

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

public class Solution {
	public static void main(String[] args) throws IOException {
		/* 카데인 알고리즘 */
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		int index = 0;
		while (st.hasMoreTokens())
			arr[index++] = Integer.parseInt(st.nextToken());

		int[] result = new int[arr.length];
		result[0] = arr[0];
		for (int i = 1; i < arr.length; i++)
			result[i] = Math.max(result[i - 1] + arr[i], arr[i]);

		int max = result[0];
		for (int i = 1; i < result.length; i++)
			max = Math.max(max, result[i]);

		bw.write(max + "\n");
		bw.close();
		br.close();
	}
}

 

2. 코드 설명

 int[] arr = {-1, 3, 4, 5, 1} 라고 하자.

 첫번째 원소에서 끝나는 부분합 : -1.

 두번째 원소에서 끝나는 부분합 : -1 + 3, 3

 세번째 원소에서 끝나는 부분합 : -1 + 3 + 4, 3 + 4, 4 

 위와 같이 계속해서 동작하면 규칙성 보인다. 

  * Max(i) = Max(Max(i - 1) + arr[i], arr[i])

첫번째 원소까지	두 번째 원소까지	세 번째 원소까지	네 번째 원소까지	다섯 번째 원소까지
-1	3	7	12	13

 그리고 다섯 번째 원소까지 합중 가장 큰 값이 부분합이 가장 큰 값이다. soltuion1 과 2 방식은 첫 번째 원소부터 시작하는 방식으로 동작했다.

 카데인 알고리즘은 반대로 첫번째 원소로 끝나는 방식이었다. 발상의 전환..

3. Pain Point

 시간복잡도는 O(n^3) -> O(n^2) 으로 줄였지만 ... O(n)까지는 줄일 수 없었다. 반대로 생각하면 풀수 있는 문제였다. 30분 넘게 고민하다가 풀지 못하여 힌트를 

 받았다.