[백준] 11053번 문제: 가장 긴 증가하는 부분 수열(LIS)

코택·2020년 9월 8일

DP python 동적계획법 백준 알고리즘

문제

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

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

예제 입력
6
10 20 10 30 20 50

예제 출력
4

접근방법

동적계획법을 활용한 기본적인 문제풀이법은 다음과 같다.

문제를 분석해서 부문제로 분할한다.

부문제의 해를 이용하여 큰 문제의 해를 표현한다(점화식 세우기).

세운 점화식을 이용해 표를 채운다.

알고리즘의 정확성을 확인하며 표에서 최종해를 구한다.

동적계획법이란 규칙성을 파악하는 것이 핵심이다. 직관이 뛰어나거나 DP 문제에 익숙한 사람들은 단번에 점화식을 세우기도 하지만, 대다수의 사람들에겐 쉽지 않을 것이다. 게다가, 점화식 문제를 분석해서 부문제로 분할하는 것 자체가 잘 안되는 경우도 있다. 그럴 땐 역으로 주어진 예제나 반례들을 이용하여 표를 먼저 채워보는 것도 해결법이 될 수도 있다.

떠올린 생각들

1. 이 문제 같은 경우 부분해를 '고려'해야하는 문제이다.

기존의 해를 단순히 이용만 하면 되는 경우엔 O(n)
기존의 해를 이용 뿐만 아니라 고려까지 해야하는 경우엔 O(n^2)
즉, 이중 for문을 이용한다.

2. 매 반복문마다 각 행의 마지막 숫자와 모든 숫자를 비교해준다.

해(DP[i])에 변화가 있는 경우는 행의 마지막 숫자(A[i])가 각 숫자(A[j])보다 큰 경우다. 이를 통해 점화식을 작성한다.
if A[i] > A[j]: DP[i] = max(DP[i], DP[j]+1)

코드

import sys
n = int(sys.stdin.readline().strip())
A = [int(x) for x in sys.stdin.readline().split()]
DP = [1 for _ in range(n)]

for i in range(n):
    for j in range(i+1):
        if A[i] > A[j]:
            DP[i] = max(DP[i], DP[j]+1)  # DP[i]는 계속해서 갱신된다.

print(max(DP))