[동적계획법] Maximum Product SubArray

 

동적계획법(Dynamic Programing)이란?

 

복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법

동적계획법은 분할된 모든 경우의 수를 검토한다. 

중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 

 

 

Maximum Product SubArray

 

예제) 정수로 구성된 한 수열이 주어질 때, 곱이 최대가 되는 부분수열을 구하라.

 

 

[ 3, -2, 1, 0,  -8, 9 ]

 

 

동적계획법을 발상하기 어려운 문제다.

 

부분수열로 분할할 수 있는 경우의 수가 너무 많다. Top에서 Down하면서 분할하기가 쉽지 않다. 그래서 일반적으로는 브루트포스 방법을 생각하게 된다. 

 

[ 3 ], [ 3, -2 ] [ 3, -2, 1] [ 3, -2, 1, 0 ] [ 3, -2, 1, 0, -8 ] [ 3, -2, 1, 0, -8, 9 ]

[ -2 ] [ -2, 1] [ -2, 1, 0 ] [-2, 1, 0, -8 ] [ -2, 1, 0, -8, 9 ]

[ 1 ] [  1, 0 ] [ 1, 0, -8 ] [ 1, 0, -8, 9 ]

[ 0 ] [ 0, -8 ] [ 0, -8, 9 ]

[ -8 ] [ -8, 9 ]

[ 9 ]

 

이중 for문을 사용하면 모든 경우를 조사할 수 있다. 하지만 비용이 많이 든다.  동적계획법의 BottomUp 방식을 사용하면 쉽게 구할 수 있다.

 

 

1) [ 3 ]

 

부분수열이 한 가지 경우가 있다. 최대곱은 3이 된다.

 

2) [ 3, -2 ]

 

 

 

1)에서 다룬 부분수열을 제외하면 부분수열은 두 가지 경우가 있다. 최대곱은 -2이고 최소곱은 -6이다.

 

 

3) [ 3, -2, 1 ]

 

 

 

2)에서 다룬 부분수열을 제외하면 부분수열이 세 가지 경우가 있다. 최대곱은 1이고 최소곱은 -6이다. 

 

이제 어느정도 패턴이 보인다. 

 

 

결과는 두 가지로 나뉜다.

 

1) 수열에 추가된 수 ( = 1 ) 

2) 이전단계의 경우의 수에 추가된 수를 곱한 결과 ( -2 와 -6 ) 

 

2)는 이전 단계의 최대곱과 최소곱에 추가된 수를 곱하면 최대곱과 최소곱을 구할 수 있다. 1)과 2)를 비교하여 최대곱과 최소곱을 구해준다. 

 

결과 : 최대곱 : 1 , 최소곱 : -6

 

곱셈은 음수끼리 곱하면 양수가 되고 음수와 양수를 곱하면 음수가 된다. 최소값을 음수와 곱하면 최대값이 될 수 있기에 최소곱과 최대곱 둘다 구해주어야 한다.

 

1)  I(n)

2)  F(n-1) x I(n) 과 f(n-1) x I(n); F(n-1)은 이전단계 최대값, f(n-1)은 이전단계 최소값

 

원리를 파악했으니 배열을 구현하여 문제를 풀어보자. 

 

 

---

 

 

1) [ 3 ]

 

 

 

 

부분수열 [3]의 최대곱과 최소곱은 3이다. 

 

 

2) [ 3, -2 ]

 

 

1)  I(n) = -2 ( 최대곱 )

2)  F(n-1) x I(n) = -6 ( 최소곱 )

3)  f(n-1) x I(n) = -6

 

2)는 이전단계의 값에서 I(n)을 곱하여 나온 결과이니 StartIndex가 0이다.

1)은 I(n)이니 StartIndex가 현재위치인 인덱스 1이 된다.

 

 

3) [ 3, -2, 1 ]

 

 

 

1)  I(n) = 1 ( 최대곱 )

2)  F(n-1) x I(n) = -2 

3)  f(n-1) x I(n) = -6 ( 최소곱 )

 

1)은 인덱스 2에서 시작하고 3)은 인덱스 0에서 시작한다. 

 

 

3) [ 3, -2, 1, 0 ]

 

 

 

1)  I(n) = 0 ( 최대곱, 최소곱 )

2)  F(n-1) x I(n) = 0 

3)  f(n-1) x I(n) =  0

 

1)은 인덱스 3에서 시작한다.

 

3) [ 3, -2, 1, 0, -8 ]

 

 

1)  I(n) = -8 ( 최소곱 )

2)  F(n-1) x I(n) = 0 ( 최대곱 )

3)  f(n-1) x I(n) =  0

 

1)은 인덱스 4에서 시작한다. 2)는 인덱스 3에서 시작한다.

 

4) [ 3, -2, 1, 0, -8, 9 ]

 

 

1)  I(n) = 9  ( 최대곱 )

2)  F(n-1) x I(n) = 0 

3)  f(n-1) x I(n) =  -72 ( 최소곱 )

 

1)은 인덱스 5에서 시작하고 3)은 인덱스 4에서 시작한다.

 

 

 

결과가 나왔다. 

 

배열에서 가장 큰 최대곱은 9이다. 

9는 StartIndex가 9이고 위치한 인덱스도 9이다. 

 

그러므로 곱이 최대가 되는 부분수열은 [ 9 ] 가 된다. 

 

 

 

---

 

 

참고자료