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

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

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

이번 포스트에서는 백준 알고리즘 문제인 가장 긴 증가하는 부분 수열을 포스트하겠습니다.

 

해당 문제는 solved.ac 기준 실버 2에 위치한 문제입니다.

 

먼저 문제입니다.

 

수열 A의 크기 N과 수열 A를 입력받았을 때, 최장 길이의 부분 수열(LIS)의 길이를 출력하는 문제 입니다.

 

해당 문제는 시간제한이 1초에 N이 최대 1000까지 주어지므로, O(N^2)의 시간복잡도를 가지는 알고리즘으로도 해결이 가능한 문제입니다.

 

따라서 저는 해당 문제를 DP 알고리즘으로 해결했습니다.

 

해당 1차원 dp 배열을 순차적으로 접근하면서, 수열의 길이를 갱신해주면 되는 점화식을 가집니다.

 

조건으로는, 2중 반복문을 돌면서 arr[i]의 값은 arr[k]보다는 무조건 커야합니다. (증가하는 부분 수열이기 때문에)

그리고, dp[i] 보다 dp[k] + 1이 더 커야합니다.

 

즉, 현재 선택한 값이 앞의 값들보다 크고, 앞의 최장 증가 수열에서 + 1한게 현재 dp 테이블에서 가리키는 값보다 크다면,

dp[i] = dp[k] + 1 연산을 통해 최장 수열 길이를 갱신해줍니다.

 

다음은 C++ 코드입니다.

 

#include <iostream>
 
using namespace std;
 
int dp[1001] = {0,};
int arr[1001] = {0,};
 
int main() {
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++)
        cin >> arr[i];    
 
    for(int i = 0; i < n; i++) {
        dp[i] = 1;
        for(int k = 0; k < i; k++) {
            if(arr[i] > arr[k] && dp[i] < dp[k] + 1)
                dp[i] = dp[k] + 1;
    
    int max = 0;    
 
    for(int i = 0; i < n; i++) {
        if(max < dp[i])
            max = dp[i];
 
    cout << max;
    return 0;
}

다음은 Python 코드입니다.

 

n = int(input())
dp = [0] * n;
arr = list(map(int, input().split()))
 
for i in range(n) :
    dp[i] = 1;
    for k in range(i) :
        if arr[i] > arr[k] and dp[i] < dp[k] + 1 :
            dp[i] = dp[k] + 1
 
max = 0
 
for i in range(n) :
    if max < dp[i] :
        max = dp[i]
 
print(max)

해당 문제는 DP 알고리즘의 대표적인 문제 중 하나로, 쉽게 점화식을 찾아낼 수 있는 문제였습니다.

추후 작성할 포스트에서는 해당 문제의 응용버전인 가장 긴 증가하는 부분 수열 2 문제도 포스트 할 수 있도록 해보겠습니다.

 

다음 포스트에서 또 다른 백준 알고리즘 문제로 포스팅하도록 하겠습니다. 감사합니다.