[탐욕법,LIS] 반도체 설계(최장증가수열)

문제

TIP

위와 같이 다음 수가 이전 수보다 커야 하는 증가하는 수열을 풀기위해 LIS 알고리즘이라는 것이 따로 있다.

LIS 알고리즘

증가하는 가장 긴 수열을 찾아라

일반적으로 DP로 풀어야 할 문제이다.

DP

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[1001];
int dp[1001];
int ans;
int N;
int main() {
    cin >> N;
    for(int i = 1; i <= N; ++i) {
        cin >> arr[i];
        int here = 0;
        for(int j = 1; j < i; ++j) {
            if(arr[i] > arr[j])
                here = max(here, dp[j]);
        }
        dp[i] = here + 1;
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

dp[i] 에는 i로 끝나는 가장 긴 수열이 들어간다.

here은 증가하는 수열의 조건에 맞을시에 가능한 수열 중 가장 긴 값을 대신한다.

LIS

LIS는 각각의 요소들이 위치할 수 있는 가장 작은 Index인 lower bound를 찾는 것을 통해 답을 찾는다.

 

lower_bound 메소드는 배열의 시작과 끝 주소, 타겟이 되는 값 세 파라미터를 통해 배열에서 타겟보다 큰 배열을 iterator 타입으로 반환한다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int L[1001], len, N;
int main() {
    cin >> N;
    for(int i = 1; i <= N; ++i) {
        int here;
        cin >> here;
        auto pos = lower_bound(L , L + len, here);
        *pos= here;
        if(pos == L + len )
            len++;
    }
    cout << len;
    return 0;
}

다음과 같은 예제에서 다음과 같이 작동한다.

입력값 : 3,2,5,2,3,1,4

 

1.

here = 3, pos = [3], L=[3], pos[0] = 3, len = 1

타겟 3보다 같거나 큰 값은 L에 존재하지 않는다.

L의 첫번째 값에 here을 할당한다.

 pos의 첫번째에 here을 할당된다.

here의 

 

2.

here = 2, pos = [2], L=[2], pos[0] = 2, len = 1 

L의 두번째 배열에 2가 할당된다.

타겟인 2는 

3.

here = 5, pos = [5], L=[2,5], pos[0] = 2, len = 2

4.

here = 2, pos = [5], L=[2,5], pos[0] = 2, len = 2

5.

here = 3, pos = [5], L=[2,5], pos[0] = 2, len = 2

6.

here = 1, pos = [5], L=[2,5], pos[0] = 2, len = 2

7.

here = 4, pos = [5], L=[2,5], pos[0] = 2, len = 2

 

코드

#include<iostream>
#include<algorithm>
 
using namespace std;
int arr[40001];
int LIS[40001];
int n,ans=0;
int Size=1;
 
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    LIS[1] = arr[1];
    int tmp;
    for(int i=2;i<=n;i++) {
        
        if (LIS[Size] < arr[i]) {
            Size++;
            LIS[Size] = arr[i];
            continue;
        }
        tmp = lower_bound(LIS + 1, LIS + Size + 1, arr[i]) - LIS;
        LIS[tmp] = arr[i];
    }
    ans = Size;
    cout << ans << "\n";
    return 0;
}

4 2 6 3 1 5

LIS = 4
SIZE = 1
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
i = 2
LIS[1] < arr[2]  ==> 증가수열이라면


tmp =  현재 LIS(증가수열) 안에서 arr[i] 타겟보다 큰 수의 첫번째 메모리 주소 - LIS(증가수열)의 메모리 주소

low_bound => [ 4 ]

LIS = [ 4 ]
i = 2 

tmp = 1
LIS[1] = arr[i] ( 2 )
LIS = [ 2 ]
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
i= 3
SIZE = 1
LIS[ 1 ] < arr[3] 
  2       <   6  
SIZE ++ ;
LIS[2] = 6
LIS[ 2 , 6 ]

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
i = 4
SIZE = 2
LIS[ 2 ] < arr[ 4 ]
  6      <   3     
LIS[ 2 , 6 ]
lower_bound = [ 6 ]
tmp = 2
LIS[tmp] = arr[4]
LIS [ 2 , 3 ] 
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
i = 5
SIZE = 2
LIS [ 2 ] < arr[ 5 ]
    6     <   1  
LIS [ 2 , 3 ]
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
i = 6
SIZE = 2
LIS [ 2 ] < arr [ 6 ]
  3       <    5 
LIS [ 2 , 3 , 5]