LIS, Bitonic

강한친구·2022년 4월 15일

알고리즘 문제풀이 기법

목록 보기

10/27

LIS

LIS에 대한 설명은 문제를 읽어보면 이해가 빠를것이다.

6개의 수를 가진 수열
10 20 10 30 20 50이 있다고 하자.

이때 최장 증가 부분수열을 어떻게 구해야할까?

풀이

일단 모든 자리는 기본적으로 1이라는 최장수열을 가진다. 자기자신이 그 수열이 되기 때문이다.

2번째 수의 경우, 10 20이기에 2가 최장수열이 된다.

3번째 수의 경우, 10 20 10이기에 자기자신이 최장수열이 된다.

4번째 수의 경우, 10 20 10 30 이기에 10 20 x 30 해서 3짜리 길이의 수열을 가진다.

여기서 한가지 규칙을 발견할 수 있다.

현재 자기 자리수 이전의 나보다 현재 값보다 작은 숫자들의 최장수열중 max값 + 1이 내가 가지는 최장수열의 값.

이라는 규칙을 찾을 수 있다.

이를 식으로 나타내려면 이중 for문을 사용해야한다.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int n;

int dp[1001];

int main() {
    cin >> n;
    int arr[n+1];
    fill_n(dp, 1001, 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    for (int i = 2; i <=n; i++) {
        for (int j = 1; j <= i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dp[i] > max) max = dp[i];
    }
    cout << max;
}

이렇게 구하면 LIS는 쉽게 구해진다.

Bitonic

이름은 거창하지만 LIS를 한번 뒤집고, 1을 빼주면 된다.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int n;

int dp1[1001];
int dp2[1001];
int ans[1001];


int main() {
    cin >> n;
    int arr[n+1];
    fill_n(dp1, 1001, 1);
    fill_n(dp2, 1001, 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp1[0] = 0;
    dp2[0] = 0;

    for (int i = 1; i <=n; i++) {
        for (int j = 1; j <= i; j++) {
            if (arr[i] > arr[j]) {
                dp1[i] = max(dp1[i], dp1[j] + 1);
            }
        }
    }
    
    for (int i = n; i >= 1; i--) {
        for (int j = n; j >= i; j--) {
            if (arr[i] > arr[j]) {
                dp2[i] = max(dp2[i], dp2[j] + 1);
            }
        }
    }
    int max = 0;
    int counter = 1;
    for (int i = 1; i <= n; i++) {
        ans[counter] += dp1[i];
        counter++;
    }
    counter = n;
    for (int i = n; i >= 1; i--) {
        ans[counter] += dp2[i];
        counter--;
    }
    for (int i = 1; i <= n; i++) {
        //cout << ans[i] << " ";
        if (ans[i] > max) max = ans[i];
    }
    //cout << "\n";
    cout << max - 1;
    
}