[BOJ] 14002. 가장 긴 증가하는 부분 수열 4 (Python)

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

가장 긴 증가하는 부분 수열 (최장 증가 수열), LIS라고도 불리는 알고리즘 문제!

굉장히 기초 알고리즘 문제 중에 하나라고 할 수 있다.

최장 증가 수열을 푸는 방법은 크게 다이나믹 프로그래밍(DP), Lower Bound 두 가지 방법이 있다.

14002번 문제의 경우 DP로도 충분히 제한 시간 안에 풀 수 있고, "동적 계획법과 최단거리 역추적"에 포함되어 있으므로 DP로 풀어보았다.

 

LIS를 DP로 푸는 아이디어는 간단하다.

수열의 i번째 숫자에 대한 LIS를 구하기 위해서는 i-1번째까지 수열의 LIS를 하나씩 보면 된다.

예를 들어, 수열이 다음과 같을 때 4번째(30) 숫자의 LIS를 구하는 방법을 살펴보자.

10 20 10 30 20 50

1번째 LIS : [10]

2번째 LIS : [10, 20]

3번째 LIS : [10]

 

* 4번째 LIS 구하는 법

10(첫번째 수열 값) > 30 이므로 첫번째 LIS에 30을 붙이면 증가하는 수열을 구할 수 있음  -> [10, 30]

20(두번째 수열 값) > 30 이므로 두번째 LIS에 30을 붙이면 증가하는 수열을 구할 수 있음 -> [10, 20, 30]

10(세번째 수열 값) > 30 이므로 첫번째 LIS에 30을 붙이면 증가하는 수열을 구할 수 있음  -> [10, 30]

따라서 4번째(30) 숫자의 최장증가수열은 두번째 LIS에 이어붙이는 경우이다. [10, 20, 30]

 

이런 식으로 하나씩 순서대로 LIS를 구해가면 쉽게 구할 수 있다. 

단, dp의 경우 O(n^2)이라는 것!

 

n = int(input()) # 수열의 길이
a = list(map(int, input().split())) # 수열
dp = [[a[i]] for i in range(n)] # dp, 초기 수열 설정

for i in range(1, len(a)) :
    num = a[i]
    for j in range(0, i) :
        if a[j] < num and len(dp[i]) <= len(dp[j]): # 증가하는 수열인지 and 최장증가수열인지
            dp[i] = dp[j] + [num]

answer = max(dp, key = len)
print(len(answer))
print(* answer)

 

LIS는 예전에도 풀어본 적이 있었으나 LIS의 숫자까지 구해본적은 없는 것 같다!

이번 알고리즘 문제에서 새롭게 알게 된 것은 파이썬 max 함수에 key를 줄 수 있다는 것!