[알고리즘] 동적 계획법(Dynamic programming) - 최장 증가 부분 수열(LIS)

1. 🔍 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)

최장 증가 부분 수열(LIS)은 주어진 수열에서 증가하는 부분 수열 중 가장 긴 수열을 찾는 문제이다.

LIS의 정의

• 부분 수열이란 주어진 수열에서 일부 원소를 선택하여 만든 수열이다. 여기서 원소의 전후 관계는 유지되어야 한다.
• 예를 들어, 수열 [1, 4, 2, 3, 1, 5, 7, 3]의 부분 수열은 [1, 2, 3], [2, 3, 5], [1, 2, 3, 5, 7] 등이 있다.
• 최장 증가 부분 수열은 주어진 수열에서 원소가 오름차순을 유지하는 부분 수열 중 가장 긴 수열을 찾는 문제이다.
  • 반드시 이전 원소가 다음 원소보다 작아야 하므로 [1, 1, 5]는 증가 부분 수열이 아니다.

LIS의 길이를 동적 계획법으로 구하기

최장 증가 부분 수열의 길이를 구하기 위해서는 다음과 같은 점화식을 세울 수 있다.

• 수열의 각 원소를 끝으로 하는 LIS의 길이를 구하는 것이 핵심이다.
• 예를 들어, 수열 [1, 4, 2, 3, 1, 5, 7, 3]의 경우, 각 원소를 끝으로 하는 LIS의 길이는 다음과 같다.
  • 1을 끝으로 하는 LIS의 길이는 1
  • 4를 끝으로 하는 LIS의 길이는 2
  • 2를 끝으로 하는 LIS의 길이는 2
  • 3을 끝으로 하는 LIS의 길이는 3
  • 1을 끝으로 하는 LIS의 길이는 1
  • 5를 끝으로 하는 LIS의 길이는 4
  • 7을 끝으로 하는 LIS의 길이는 5
  • 3을 끝으로 하는 LIS의 길이는 3
• 순차적으로 LIS를 구하는 것을 보면 이전 LIS의 길이를 활용하여 현재 LIS의 길이를 구할 수 있다.
  • 예를 들어, [1, 4, 2, 3, 1, 5, 7, 3]의 경우, 1을 끝으로 하는 LIS의 길이는 1이다.
  • 4를 끝으로 하는 LIS의 길이는 1을 끝으로 하는 LIS의 길이 + 1이다.
  • 2를 끝으로 하는 LIS의 길이는 1을 끝으로 하는 LIS의 길이 + 1이다.(4로 끝나는 LIS도 체크를 하지만 증가 수열 조건에 위배되므로 무시한다.)
  • 3을 끝으로 하는 LIS의 길이는 2를 끝으로 하는 LIS의 길이 + 1이다.
  • 1을 끝으로 하는 LIS의 길이는 1이다.
  • 5를 끝으로 하는 LIS의 길이는 3을 끝으로 하는 LIS의 길이 + 1이다.
  • 7을 끝으로 하는 LIS의 길이는 5를 끝으로 하는 LIS의 길이 + 1이다.
  • 3을 끝으로 하는 LIS의 길이는 2를 끝으로 하는 LIS의 길이 + 1이다.

메모이제이션을 활용한 LIS 구현

메모이제이션을 활용하여 LIS를 구현할 수 있다.

• 메모이제이션을 위한 배열을 dp라고 하자.
• dp[i]는 수열의 i번째 원소를 끝으로 하는 LIS의 길이를 저장한다.
• 초기값은 dp[i] = 1이다.(i번째 원소 자체가 부분 수열이므로 최소 길이는 1이다.)
• 점화식은 다음과 같다.
  • dp[i] = max(dp[i], dp[j] + 1) (단, j < i이고 arr[j] < arr[i])

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    size_t n;
    std::cin >> n;
    std::vector<int> arr(n);
    for (size_t i = 0; i < n; i++) {
        std::cin >> arr[i];
    }

    std::vector<int> dp(n, 1);
    for (size_t i = 1; i < n; i++) {
        for (size_t j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
              dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }

    std::cout << *std::max_element(dp.begin(), dp.end());
}

Algorithm Theory 카테고리 내 다른 글 보러가기