[알고리즘] LIS(최장 증가 부분 수열의 길이)

Sujung Shin·2023년 1월 29일

알고리즘

목록 보기

8/12

문제 풀러 바로가기 >> 11053 :: 가장 긴 증가하는 부분 수열의 길이

때는 바야흐로 2023년 1월...
알고리즘 공부를 시작한지 2주차 되는 날 시련이 온다.
다른 dp문제는 뭔가 감이라도 잡겠는데, 음. 이건 이해가 안 간다...😣😣

하... 진짜 이렇게까지 틀린 적이 없는데 한 숨만 푹푹 나온다.

그래서 이건 하나의 널리 알려진(well-known) 알고리즘이겠거니... 하고 받아들이는 게 내 숙명이라고 받아들였다.

💡문제

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

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

💻 입력

첫째 줄에 수열 $A$ 의 크기 $N$ (1 ≤ $N$ ≤ 1,000)이 주어진다.

둘째 줄에는 수열 $A$ 를 이루고 있는 $A_i$ 가 주어진다. (1 ≤ $A_i$ ≤ 1,000)

💻 출력

첫째 줄에 수열 $A$ 의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

✨ 내가 생각한 로직이라 쓰고 삽질이라 읽는다

해당 문제는 2가지의 풀이 방법이 가능하다고 한다.

DP로 풀기(O(n^2))
이분탐색으로 풀기(O(nlogn))

이번 포스팅에서 소개할 풀이는 O(n^2)의 시간복잡도로 풀 수 있는 dp풀이 방법이다.
dq문제 풀이 과정에 맞추어, step-by-step으로 문제를 차근차근 풀어보자.

🚩 Dynamic Programming으로 풀기

STEP 1. 상태 정의 (dp 테이블 정의)

dp[i] = a[1]~a[i]까지 만들 수 있는 가장 긴 증가하는 부분 수열의 길이

dp 상태 값을 다음과 같이 정의하면, dp 테이블은 이렇게 채워진다.

STEP 2. 점화식 도출

이제 점화식을 도출해보자. 초록색 화살표는 현재 위치값인 a[i]보다 작은 범위 (j 범위: 1~i-1)중에서 자신보다 작은 값(a[j])을 탐색한다.

dp[1] = a[1]까지 만들 수 있는 가장 긴 증가하는 부분 수열의 길이 = 1
a[1]의 값은 10이다. a[1]보다 이전에 있는 값들은 존재하지 않으므로 해당 dp값이 초기값이다. (dp[1] = 1)
dp[2] = a[1]~a[2]까지 만들 수 있는 가장 긴 증가하는 부분 수열의 길이 = 2

a[2]의 값은 20이다. 이전에 있는 값들 중에서 자신보다 작은 값은 a[1]인 10밖에 없으므로 해당 dp값인 dp[1]+1=2가 dp[2]의 값이다.

dp[3] = a[1]~a[3]까지 만들 수 있는 가장 긴 증가하는 부분 수열의 길이 = 1

a[3]의 값은 10이다. 이전에 있는 값들 중에서 자신보다 작은 값은 존재하지 않는다. 따라서 dp[3]=1이다.

dp[4] = a[1]~a[4]까지 만들 수 있는 가장 긴 증가하는 부분 수열의 길이

a[4]의 값은 30이다. 이전에 있는 값들이 다 자신보다 작으므로 전부 다 비교대상이 된다. 이 중 가장 큰 dp값은 2이므로 dp[2]+1이 dp[4]의 값이다.

dp[5] = a[1]~a[5]까지 만들 수 있는 가장 긴 증가하는 부분 수열의 길이

a[5]의 값은 20이다. 이전에 있는 값들 중에서 자신보다 작은 값은 a[1]=a[3]인 10밖에 없으므로 해당 dp값인 dp[1]+1=dp[3]+1=3이다.

dp[6] = a[1]~a[6]까지 만들 수 있는 가장 긴 증가하는 부분 수열의 길이

a[6]의 값은 50이다. 이전에 있는 값들이 다 자신보다 작으므로 전부 다 비교대상이 된다. 이 중 가장 큰 dp값은 3이므로 dp[4]+1=3+1=4이다.

✔️ 결론

우선 dp 테이블을 전부 1로 초기화한 다음,
i = 1 to n 까지 순회하면서 dp[i] 값을 차례대로 채운다.
또, j<i에 대하여 a[i]보다 작은 값을 가진 a[j]가 있는지 탐색하고,
있다면 개 중 가장 큰 dp값+1 해준 값이 dp[i]가 된다.
없다면 dp[i]=1이다.

💻 정답 코드

//LIS 문제
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[1004], dp[1004];
//dp[i] : a[i]로 끝나는 가장 긴 증가하는 부분수열 길이
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  for(int i =1; i <=n; i++) cin >> a[i];
  
  for(int i =1; i <=n; i++) {
    dp[i] = 1; //3. 존재하지 않는다면, 1
    for(int j =1; j <i; j++) {
      //1. a[1]~a[i-1] 중 작은 값이 존재하는지 찾는다.(선형탐색, O(n^2)의 시간복잡도 발생)
      if(a[j]<a[i]) dp[i]=max(dp[j]+1, dp[i]);
      //2. 존재한다면, 개 중 제일 큰 dp값을 뽑아내어 1을 더해준다.
    }
  }
      //4. dp테이블을 다 채우면, i=0 to n까지 순회하며 가장 큰 dp[i]값을 추출한다.
  int ans = 0;
  for(int i =1; i <=n; i++) {
    ans = max(dp[i], ans);
  }
  cout << ans << "\n";
}