[동적 계획법] Longest Increasing Sequence, JLIS 합친 LIS

-jlis 문제를 푸는 과정에서의 나의 잘못된 접근방법

1. LISLongest Increasing Sequence

jlis 문제를 풀기전에 알고리즘 문제해결전략 책에 나와있는 LIS의 더 빠른 알고리즘을 구현하였다.

(동적계획법을 사용한 O(n^2)알고리즘과 다르게 O(nlgn)만에 수행된다.)

 

이 알고리즘은 배열의 각 원소들을 앞에서 부터 탐색해나가며

다음과 같은 배열에 원소들을 집어넣는다.

 

C[i] = 지금 까지 만든 부분 배열이 갖는 길이 i인 증가 부분 수열 중 최소의 마지막값

 

C[i]에 원소들을 집어 넣을 때 push()함수가 쓰이는데

이 함수는 삽입정렬과 비슷하며 다음과 같이 작동한다.

 

C[i] 배열에 x라는 원소를 삽입하고자할 때 이 함수는 i에서 시작하여 1까지 탐색하여     

 

                       lo < x   &&    x <= hi   && (lo + 1 == hi)

 

lo 와 hi를 구하여 hi에 원소를 삽입한다.

이는 lo길이를 가지는 수열에 x를 덧붙여 hi 길이인 수열을 만드는것이다.

 

이 때 C[] 배열은 항상 오름차순으로 정렬되며 

이는 이진 탐색을 사용할 수 있음을 의미한다.

 

 

int C[501];
 
void push(int x, int lo, int hi, int& maxlen)
{
    int mid = (lo + hi)/2;
    if (C[maxlen - 1] < x)
       C[maxlen++] = x;
    else if(lo + 1 == hi)
       C[hi] = x;
    else if (C[mid] >= x)
        return push(x, lo, mid, maxlen);
    else
        return push(x, mid, hi, maxlen);
}
 
void lis(vector<int> alist, int ai, int& maxlen)
{
    if(ai == an) return;
 
   int a = alist[ai]; 
   push(a, 0, maxlen, maxlen);
    return lis(alist, ai+1, maxlen);
}

2.JLIS (합친 LIS) 잘못된 풀이.

 

처음 jlis라는 문제를 봤을때 1lis와 마찬가지로

C[i]같은 배열을 만들자고 생각하였다.

 

이 C[i]는 lis때 와 마찬가지로 증가 수열 길이 와 마지막 원소값의 정보를 가지고 있고

a와 b의 배열을 합친 lis이다.

 

하지만 작성한 코드는 시간초과가 되었고, 나는

int cache[ai][bi] 를 생성하여

ai 와 bi 의 단계에서 한번 계산이 수행되었으면 return 하는

동적계획법을 사용한 함수를 다시 구현하였다.

 

하지만 이 코드는 원활하게 돌아가지 않았고, 문제점이 많았다.

그 문제는 정보가 하나 더 필요했던 것이다.

 

그 정보는 바로 ai bi 즉

a 배열의 남은 갯수, b 배열의 남은 갯수와 더불어 

이 남은 것들을 조합하여 최장이 되었을 떄의 맨 앞의 원소의 정보가 

더 필요로 하였다.

void jlis(int ai, int bi)
{
    int &ret = cache[ai][bi];
    
    if(ret != -1) return;
    if(ai == an && bi == bn) return;
    
    int a = alist[ai];
    int b = blist[bi];
 
    ret = 1;
    if(ai != an)
    {     
        jpush(a, 0, jsize);
        jlis(ai+1, bi);
    }
    if(bi != bn)
    {
        jpush(b, 0, jsize);
        jlis(ai, bi + 1);
    }
}

 

 

이는 a와 b를 각 배열 안의 원소들의 순서는 지키되

a와 b를 섞어 넣은 모든 배열을 생성한뒤

lis를 생성한 모든 배열에 실행하여

가장 긴 것을 찾는것과 동일한 코드일 것이다.

 

이 코드의 잘못된 수행은 다음과 같다.

 

j1: a0 a1 a2 b0

                   b1 b2

 

j2: a0 a1 b0 a2

                   b1 b2

 

코드 순서에 따라 j1 이 만들어 진 다음 j2 배열이 만들어진다

 

이 때 a2 == b1 이라고 하고 b0 < a2라 하자

 

j1의 배열은

최대 5의 길이를 가지는 lis를 생성할 수 있다

만약 이 경우

a2까지 쓰였고, b0 이 쓰인 다음 즉 cache[2][0]에 2가 들어가게 된다.

 

j2가 생성될때

a2가 추가된 이후 cache[2][0] != -1 이 므로 2 + 1 이 되어 

결국

a0 a1 b0 a2 b1 b2 라는 증가함수 즉 최대 길이가 6인 수열이 생기게 된다.

 

하지만 a2 == b1이므로 이것은 거짓된 값이 된다.

 

그러므로 여기서 이 코드가 문제가 생김을 알 수 가 있었고

 

이는 원소의 정보가 하나 더 필요함을 의미 한다.

 

원소의 정보를 하나 더 추가한다는것은 

간결한 코드가 되지않고 복잡한 코드가 된다는 것이다.

따라서 이런 접근 방식은 잘못된 접근이라고 생각한다.

 

복습할 때 이 풀이는 다시 생각해봐야 겠다.

 

JLIS

Longest Increasing Sequence