[1][LIS : 최장증가수열 알고리즘] - DP 를 이용한 알고리즘 (Longest Increasing Subsequence Algorithm)

LIS Algorithm

LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다.

 

 

다음과 같이 7개의 숫자가 나열되어있을때

 

 

 

 

여기서 LIS는

 

위와같이 20 40 50 80 으로 최대길이는 4이다.

 

 

 

 

물론 아래와 같은 경우도 모두 LIS에 속한다. (LIS알고리즘에서 최대길이를 구성하는 모든 원소들을 구할경우 아래와같이 가능한 경우의 수가 여려개 일수 있기때문에 백준저지에서는 스페셜 저지로 채점을 한다.)

 

 

 

 

+ 주의할점은 항상 이전에 선택한 원소보다 커야하기때문에 같은원소역시 연속으로 선택할수 없다.

 

 

 

---

1. DP(Dynamic Programming) 를 이용한 알고리즘

첫번째로 알아볼 알고리즘은 DP를 이용한 알고리즘이다. 

주어진 배열을 arr[], 값을채워나갈 배열을 dp[] 라고 하자.

dp[i] 를  "arr[i]를 마지막 원소로 갖을때 최대증가수열 값" 이라고 정의하자.

 

 

전체 알고리즘은 다음과 같다.

 

int lis_dp(int n){ // dp를 이용한 lis algorithm
    int i,j;
    int max = 1;
    for(i=0;i<n;i++){
        dp[i] = 1;
        for(j=0;j<i;j++){
            if(arr[j] < arr[i] && dp[j]+1 > dp[i]){
                dp[i] = dp[j]+1;
                if(max < dp[i]){
                    max = dp[i];
                }
            }
        }
    }
    return max;
}

 

위의 알고리즘에서 가장 중요한 부분은 아래의 if문이다.

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

 

i 는 0부터 배열의 길이인 n번 순회하면서 dp[i]를 채워나가고

j 는 0부터 i 이전까지 순회하게 된다.

 

if 문 내의 두 조건을 보면

 

1. arr[j] < arr[i] 

  i 이전의 값이 현재 i 보다 작은지 확인하는 부분이다. LIS 알고리즘이 항상 증가하는 수열이여야하므로 이 조건이 필요하다.

 

2. dp[j]+1 > dp[i]

  j 번째 원소를 마지막으로 갖는 최대증가수열이 dp[j]인데 마지막 i값을 끝에 추가했을때 현재까지의 최대값보다 커야하므로 이 조건이 필요하다

 

따라서 두 조건 모두 만족하게 된다면 해당 해당 j 번째 인덱스에 있는 값이 현재 i 인덱스 값보다 작으며 따라서 i 번째 인덱스 값을 그 뒤에 추가했을때라는 가정하에 가장 최댓값을 가지게 된다.

 

이 조건에 따라 2중 for문을 다 돌게되면 dp에 있는 값중 가장 큰 값이 최종 답이된다.

 

위의 코드에서는 max값으로 최대값이 나올때마다 갱신을 해주었다.

 

위 알고리즘은 O(N^2) 의 시간복잡도를 가진 알고리즘으로 배열의 길이가 100000만 넘어도 매우 오랜시간이 걸리게된다.

 

따라서 다음에는 Lower bound를 이용한 O(NlogN)의 시간복잡도를 가진 알고리즘을 알아보도록하자.