Notice
Recent Posts
Recent Comments
Link
«   2024/09   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
Tags more
Archives
Today
Total
관리 메뉴

fatalite

LIS(Longest Increasing Subsequence) 문제 (자가정리용) 본문

코딩 인터뷰

LIS(Longest Increasing Subsequence) 문제 (자가정리용)

fataliteforu 2023. 10. 14. 21:36

문제 링크

 

11054번: 가장 긴 바이토닉 부분 수열

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

www.acmicpc.net

이 문제를 풀려고 했는데, 2차원 DP 문제일까 생각을 해봤지만,
고민해봐도 비교하는 것과 규칙이 생각나지 않아서 해설을 봤다. 

잘 알려진 문제인 것 같다 최장 부분 증가 수열, LIS라고 불리는 문제이다.

근데 이거의 베이스 문제가 이미 풀었던 문제였더라, 아마 해답 보고 다시 생각해보지 않아서 그랬나보다.. 복습을 해야겠다.

DP 문제의 핵심은 어떻게 부분 문제로 나눌 것인가가 핵심인 것 같다. 

다양한 시도가 필요해보인다.

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

문제 소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>

using namespace std;

int Arr[1001];
int ReverseArr[1001];
int DP[1001];
int ReverseDP[1001];
void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
}



int main()
{
    Init();
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int Tmp;
        cin >> Tmp;
        Arr[i] = Tmp;
        ReverseArr[n - i + 1] = Tmp;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (Arr[i] > Arr[j]) {
                DP[i] = max(DP[j] + 1, DP[i]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (ReverseArr[i] > ReverseArr[j]) {
                ReverseDP[i] = max(ReverseDP[j] + 1, ReverseDP[i]);
            }
        }
    }
    int Max = 0;
    for (int i = 1; i <= n; i++) {
        Max = max(DP[i] + ReverseDP[n - i + 1], Max);
    }
    cout << Max + 1;
}