47. 최대 연속부분수열(Max Consecutive Number Sub Sequence)의 합 알고리즘

1. 개요

최대 연속부분수열의 합 알고리즘은 쉬움.

어떤 수열의 연속부분수열이란 그 수열의 원소를 하나 이상 연속하여 선택한 부분수열을 뜻한다.

예를들어)

33 36 -73 15 43 -17 36 -28 -1 21

이란 수열이 있다면, 이 수열의 연속부분수열들이 될 수 있는 것은 이렇다.

33 36 -73 15 43 -17 36 -28 -1 21

33 36 -73 15 43 -17 36 -28 -1 21

33 36 -73 15 43 -17 36 -28 -1 21

33 36 -73 15 43 -17 36 -28 -1 21

그리고 찾아야 할 문제는 이런 연속부분수열들의 합이 최대가 되는 것을 말한다.

점화식은 2가지 재귀적 규칙이 있다.

M(n): 0부터 n-1까지의 연속부분수열의 합이 최대치가 되는 것을 의미.

M'(n): M2(n-1)과 n번째 수열값을 비교. 큰 값을 선택. 이것의 의미는 연속된 수열의 합이 끊기는지, 아닌지 판단.

코드에도 기술했지만, 최종 점화식을 보면

//M[n] = MAX( M[n-1], M'[n] )

//=> MAX( M'[n], MAX( M[n-2], M'[n-1] )

//=> MAX( M'[n], M'[n-1], M[n-2] )

//=> MAX( M'[n], M'[n-1], M'[n-2], M'[n-3] ... M'[0]) 성립

이 규칙을 토대로 코드를 작성하면 된다. 

점화식을 보면 알겠지만 2종류의 재귀 함수가 등장한다.

2. 문제

정수들의 배열이 주어지면최대 연속부분수열의 합을 찾는 프로그램을 작성하라.

(단, 프로그램은 100만 개의 정수 수열에서 최대 값을 1초 내에 찾을 수 있어야 한다.)

3. 코드

3-1) Recursion

3-2) Memoization

3-3) Dynamic Programming

3-4) SIZE 10

3-5) SIZE 100

3-6) SIZE 1000

3-7) SIZE 10000

3-8) SIZE 100000

3-9) SIZE 1000000

4. 정리

이 문제를 통해 알게된 것은 재귀, 메모이제이션, DP의 흐름이다.

문제를 풀거나 해결해야할 때, 먼저 재귀적 흐름, 즉 점화식을 찾는다.

그리고 이 점화식에 따라서 재귀 함수를 만들어서 1차 테스트를 한다.

그리고 2가지 길이 있다.

만약, 이 문제를 해결해야 할 때, 데이터의 크기가 무수히 많고 속도적인 측면을 고려한다면 DP를 선택한다.

하지만 재귀나 메모이제이션이 가지는 스택 오버플로우의 위험이 없고, 코드의 미감을 살려야한다면 

재귀 or 메모이제이션을 선택한다. 

결국 미감 vs 성능, 추상 vs 객관, 간결성 vs 안정성

재밌네, 알고리즘.