가장 긴 증가 하는 부분 수열

점화식

if (array[i] < array[j]) {
    dp[i] = max(dp[i],dp[j]+1);
 }

가장 긴 증가하는 부분 수열에 위 점화식으로 모두 해결이 가능하다.

다음은 백준 11053번 문제이다.

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

여기서 우리가 알아야할 것은 부분 수열이다.

수열은 숫자가 열거된 형태를 말하기 때문에 배열이라 생각해도 무방할 것 같다.

부분수열이란?

그렇다면 부분 수열이라는것은 무엇일까?

위 수열

{10,20,10,30,20,50} 의 부분수열은

{10}, {10,20}, {10,20,10},

{30,20}... 등등 이런것이 부분수열이다. 그렇다면

가장 긴 부분 수열은 무엇을 뜻하는 걸까?

현재 전체 수열을 표로 그려보자(표로 그린다고 엄청나게 있는건 아니지만...)

10	20	10	30	20	50
초기값	증가	감소	증가	감소	증가

 

이런게 증가 수열이 아닐까?

{10,20}, {30},{50} 이 증가하는 부분 수열이 아닐까 추측해본다.

가장 긴 부분수열 구하기

그러면 가장 긴 부분수열의 총 길이는 4가 된다.

따라서 답은 4다.

출처 : https://wootool.tistory.com/96

이 그림을 보면...

어떻게 부분수열을 만들어주는지 보여주고 있다.

현재 dp의 숫자가 a배열의 숫자보다 크다는걸 알수 있는데, 아마도 첫번째는 0으로 초기화 시키기 위함이 아닐까 생각한다.

초기 10일때는 당연히 자신이 가장 크기 때문에 1이고...

20은 a[0]인 10보다 크기 때문에 2로 둔것 같다.

두번째 10같은 경우, 20보다 작다. 그렇기 때문에 증가하지 않는다. 오히려 줄었다고 할 수 있다.

그렇기 때문에 a[0]값이랑 똑같은 1이 되는 것 같다,

30은 10,20,30 이기 때문에

50 10,20,30,50, 이렇게 구하면 되는게 가장 긴 증가하는 부분 수열이다.

dp에 어떤값을 저장시키는지 확인했기 때문에 이제 점화식이 어떻게 만들어졌는지 확인해보자.

점화식 파악하기

위에 점화식이 있다.

만약에 이해가 되지 않는다하면 잠깐 외우는것도 나쁘지 않는 방법인것 같다.(그렇다고.. 애국가 외우는것 처럼 즉각적으로 반응할 정도로 외우지는 않아도 될것 같다. 어차피 적응되면 이게 뭔지 알 수 있기 때문이다.)

다시 위 점화식을 가져와서 분석해보자.

if (array[i] < array[j]) {
    dp[i] = max(dp[i],dp[j]+1);
 }

이런건데

보면 i와 j가 나눠져 있다는걸 알 수 있다.

그렇다는건,..

for(int i = 0; i<n;i++) {
	for(int j = 0; j<n;j++) {
    }
}

이런 느낌으로 되있지 않을까 생각한다.

근데 array[i]와 array[j]가 다르다는 걸 알 수 있다.

그러면

for(int i = 0; i<n;i++) {
	for(int j = 1; j<n;j++) {
    }
}

이런식으로 하면 달라지지 않을까?

그리고 dp[i] = max(dp[i],dp[j]+1)를 두번째 for문에 넣으면 되지 않을까?

for(int i = 0; i<n;i++) {
	for(int j = 1; j<n;j++) {
    	dp[i] = max(dp[i],dp[j]+1);
    }
}

그러면 내가 구한 위 식이 맞는 걸까? 다시 그림을 가져 와보자.

출처 : https://wootool.tistory.com/96

보면... dp[i]을 잘보자.

처음에는 10까지 이동하고, 2번째는 20까지 이동된다. 이를 생각해보면

j<n값은 아니라는것을 알 수 있다.

그러면 무엇일까? 당연한 소리겟지만 i가 아닐까?

그래야 10은 까지 이동할게 아닌가...

for(int i = 0; i<n;i++) {
	for(int j = 1; j<i;j++) {
    	dp[i] = max(dp[i],dp[j]+1);
    }
}

무조건적으로 이렇게 하면 되는걸까?

위 그림을 보면 20일때는 2고 그 다음 10일때는 1이 된다. 이를 미뤄봤을때..

for(int i = 0; i<n;i++) {
	for(int j = 1; j<i;j++) {
    	if (arr[i] < arr[j]) { 
    		dp[i] = max(dp[i],dp[j]+1);
        }
    }
}

가 되는게 아닐까?

그래야 ... 20일때는 10,20이되서 결국엔 2가 되지 않을까?

그러면 마지막으로 확인해야할 것은 max부분이다. 얘네는 도대체 뭐지...

처음에는 dp[i]가 0이다. 그리고

dp[1]은 1이 된다.

이를 생각해보면

dp[1] = max(dp[1],dp[2]+1); 가 되는 것 같다. 그러면 이렇게 생각할 수 있다. 그러면 무조건 뒤가 큰게 아닌가 라고...

결론부터 말하면 뒤가 클 수도 있다. 그 이유는 이중 for문이기 때문에 이런 현상이 나타나는 것이다.

즉. i가 2일때 j는 1부터 다시 시작된다는 이야기다.

이제 확실하게 하기 위해 내가 작성한 코드가 맞는지 확인하자.

결국...

for (int i = 0; i < n; i++) { 
    for (int j = 0; j < i; j++) {
    	if (arr[i] > arr[j]) { 
        	dp[i] = max(dp[i], dp[j] + 1); 
       } 
}

j가 0이 었구나.... 자기자신 포함이구나 라는걸 알 았다.

일부로 초기화 코드는 넣지 않았다.

초기화는 1로 초기화 시킨다.

 

결론은 가장 긴 증가하는 부분수열이라는건...

배열을 순회하면서 서로의 값을 비교하고, 비교한 값보다 몇개가 더 큰지 확인하는 문제가 아닐까 생각한다.

이걸 반대로 하면... 혹시... 가장 짧은 부분이 되는건가....????!