[백준 11053] 가장 긴 증가하는 부분 수열(C++)

가장 긴 증가하는 부분 수열

링크: https://www.acmicpc.net/problem/11053

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

문제 접근

• 처음에는 문제 자체를 이해하지 못했다. 이유는 부분수열의 정의를 모르고 있었기 때문이다.
  • 부분 수열의 정의: 주어진 항을 원래 순서대로 나열하여 얻을 수 있는 수열
• DP로 풀 수 있는 알고리즘 중 LIS(Longgist Increasing Subsequence)을 사용하는 문제이다.
• 자, LIS를 먼저 간단히 알아보도록 하자.

LIS(Longgest Increasing Subsequence)

• 최장 증가 부분 수열이라고도 불린다.
• O(N^2)의 풀이와 O(NlogN)의 방법이 존재한다.
  
  • O(NlogN)의 방법은 전자를 최적화 한 것이므로 여기서는 O(N^2)의 방법을 통해 기초적인 LIS의 이해를 목표로 서술하겠다.

문제에서 주어진 예제를 다시 한 번 살펴보자.

{10, 20, 10, 30, 20, 50}

각 요소를 부분 수열의 마지막 항으로 가질 시 그 부분 수열의 길이를 나타낼 수 있다.

테이블 D는 부분 수열의 최장 길이를 가진다.

• 시간복잡도가 O(N^2)인 이유는 현재 비교하려는 항목 i에 대하여 i - 1까지 살펴보아야 하기 때문이다.
• O(NlogN)으로 이를 최적화하는 방법
  • 테이블 X의 index를 LIS로 둔다.
  • 각 index에 대한 값을 LIS로 가지는 가장 작은 항목을 갱신하며 진행한다.
  • 여기서 X는 오름차순으로 정렬이 되어있기 때문에 해당 항목이 X의 어디에 해당하는지 검색하는 것은 Binary Search를 통해 진행할 수 있으므로 시간 복잡도를 줄일 수 있다.

풀이 힌트

• 로직을 이해했다면 구현은 간단하다.
  • LIS를 저장할 배열 D를 가지고 이전 값들을 순회한다.
  • 현재 인덱스 i 보다 작은 수 중 D[j]가 가장 큰 값을 찾는다.
  • D[i]의 값은 D[j] + 1 이다.

코드

#include <iostream>

using namespace std;
int arr[1001];
int part[1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, longest, mx = 0;
    cin >> N;
    part[0] = 0;
    for (int i = 1; i <= N; ++i) {
        cin >> arr[i];
        longest = 0;
        for (int j = 0; j < i; ++j) {
            if (arr[j] < arr[i]) {
                longest = max(longest, part[j]);
            }
        }
        part[i] = longest + 1;
        mx = max(part[i], mx);
    }

    cout << mx;
}

 

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.