[BaekJoon/백준] 11053번 / 순열 조합은 동적계획법인가? | 복습 1회 완료

LIS( 최장증가수열 ) 문제다.

 

이 문제를 보고는 곧바로 풀이가 떠올랐다.

원리가 간단해보였다. 하지만 갈등했다. 문제는 명칭의 문제였다.

 

여태까지 풀어온 방식대로 뭔가 동적계획법 같은 느낌으로 풀어볼까 라는 마음으로 시작했는데,

내가 지금 생각해낸 방식이 동적계획법을 이용한 풀이가 맞는지에 대한 강박이 생겼다.

 

'동적계획법' 카테고리에 소속되어 있는 문제인데, 내가 푼 풀이는 뭔가 여태까지 풀어온 동적계획법과는 느낌이 달랐다.

 

그래도 일단 짜봤다. 내방식대로. 그리고 제출에 넣어봤다. 정답 받았다.

그리고 사람들의 풀이를 봤다. 나와 동일했다.

#include <stdio.h>

int N;
int a[1000][2];

int main() {
    int i, j, max = 1; // max = 1은 N = 1은 무조건 충족하므로 기본값.
    scanf("%d", &N);
    
    a[0][1] = 1;
    
    for(i = 0; i < N; i++) {
        scanf("%d", &a[i][0]);
    }
    
    for(i = 1; i < N; i++) {
        for(j = i - 1; j >= 0; j--) {
            if(a[i][0] > a[j][0] && a[i][1] < a[j][1])
                a[i][1] = a[j][1];
        }
        a[i][1]++; // 자신보다 낮은 수 중 수열의 최댓값을 찾은 뒤 '자신'도 포함해야 하므로 +1
        if(max < a[i][1])
            max = a[i][1];
    }
    printf("%d", max);
}

+추가, 현재 이 코드에서는 첫 번째 자리를 1로 미리 채우고 포문의 인덱스 시작을 1부터 했는데, 1로 안채우고
포문을 0부터 돌아도 첫번째 자리는 a[0][1]++ 실행으로 알아서 1로 채워진다 - 11054번의 풀이

잠시 고민의 시간을 가졌다.

이전의 문제들은 최댓값 / 최솟값을 구하는 과정에서 모든 인덱스를 하나하나 열어볼 수고를 덜면서 동적계획법에 의미를 부여시킨 것 같은데, 이 풀이는 결국엔 전체 인덱스를 모두 뒤져야 했다. 그럼 내가 순열/조합 풀이를 했던 방식도 결국 모든 경우의 수 인데 이것도 동적계획법이 맞는걸까? 라는 생각이 꼬리에 꼬리를 물었다.

 

하지만, 조금 더 생각해보면 이 풀이는 동적계획법을 위한 두 가지 조건을 충족한다.

1. 최적 부분 구조

2. 반복되는 부분 문제

 

 

 

그리고 내가 이전에 풀었던 순열 / 조합 문제에 대해서도 동적계획법 방식인지 판단이 필요했다. (일단 기본적으로 순열 조합 문제는 백트래킹 알고리즘이다.)

hevton.tistory.com/329

위 글에서 이전에도 비슷한 의문을 품은 적이 있다. 이 때에는 이 방법이 메모이제이션 적용이라는 의미가 충족되는가 였다.

언뜻 메모이제이션 느낌이 들긴 했는데, 확신하진 못했었다. 아직 확실하진 못하지만 뭔가 이렇게 차차 자리잡는 느낌이다.

 

순열 조합은 생각해보면 반복되는 부분문제라고 하기엔 애매하다. 뽑기(1) 뽑기(2) 뽑기(3) 이렇게 진행되기 때문에..

물론 뽑기(3)을 진행하기 위해선 뽑기(1)이 이미 진행되었어야 했지만, 이건 그냥 최적부분구조 라는 의미 하에 정리될 수 있는 뜻이다.

그리고 이 때 단순하게 메모이제이션과 비슷한 원칙을 도입했다고 볼 수도 있기야 하다. 근데 반복되는 부분문제라는 조건이 충족되기엔 조금 아쉽다는 생각이 든다. 다음에 더 확실해지면 다시 정리해야겠다.

 

 

 

 

 

11053번 문제 풀이 참고

wootool.tistory.com/96

[백준][11053번][DP] 가장 긴 증가 부분 수열

 

---

2021.02.25 복습

다시 풀어보았다. 뭐 비슷하게 푼 것 같다.

#include <stdio.h>

int N;
int dp[1000][2]; // [0] = value , [1] = LIS value
int M = 0;

int main() {
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        
        scanf("%d", &dp[i][0]);
        
        for(int j = 0; j < i; j++) {
            // 이전 수들 중 현재보다 작은 수(dp[j][0] < dp[i][0])이면서
            // LIS value가 현재보다 크거나 같을 때(dp[j][1] >= dp[i][1]. 같을때도 허용되어야함) = 업데이트 할만한 가치가 있을 때
            if(dp[j][0] < dp[i][0] && dp[j][1] >= dp[i][1])
                dp[i][1] = dp[j][1] + 1;
        }
        if(M < dp[i][1])
            M = dp[i][1];
    }
    printf("%d", M + 1); // 기본값이 0부터 시작이였으므로, + 1 진행 (맨 첫번째 수의 LIS는 1인데, 0부터 시작했으므로)
}

/*
 LIS
 */