[🥈2 / 백준 11053 / 파이썬] 가장 긴 증가하는 부분 수열 (LIS(Longest Increasing Subsequence))

 

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

 

문제

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

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

입력

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

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

출력

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

 

예제 입력 6 10 20 10 30 20 50

예제 출력 4

 

 

풀이

 

순서대로 주어진 수들을 골라내어 가장 긴 수열의 길이를 구하는 문제이다.

 

각 수까지 갈 때의 최대의 길이를 저장하고, 적절할 때 이를 꺼내어 쓰는 방식으로 문제를 풀 것이다.

 

 

맨 처음 숫자는 입력과 관계없이 무조건 0 이 존재한다고 가정하고

0 2 5 4 6 1 7 8 이라는 입력이 들어왔다고 하자.

 

각 수가 마지막일 때의 수열 길이 최댓값을 저장해두는 배열을 dp,

비교해줄 수들을 저장하는 배열을 cp라고 한다.

 

최초값으로 0이 들어가있고 첫 번째 수는 무조건 수열의 길이가 1이다. 따라서 

 

dp = [0, 1]

cp = [0, 2]    꼴이 된다.

 

이제 5를 비교해보자.

 

cp에 2가 최대이다. 5는 이보다 크므로 그대로 cp에 저장해주고, dp에 저장된 2의 인덱스는 1이다.

 

이에 1 만큼 더해주자.

 

dp = [0, 1, 2]

cp = [0, 2, 5]

 

4를 비교한다. 4는 5보다 작고 2보다 크다. 2의 인덱스는 1 이므로 여기에 1만큼 더해서 저장해주자.

단, 여기서 5를 4로 교체한다. 다음으로 들어올 수들의 수열 길이가 2보다 크려면, 5가 아닌 4와 비교해주면 되기 때문이다.

 

dp = [0, 1, 2, 2]

cp = [0, 2, 4]

 

이런 식으로 식을 쭉 채워나간다.

 

cp	dp
0, 2, 5	0, 1, 2
0, 2, 4	0, 1, 2, 2
0, 2, 4, 6	0, 1, 2, 2, 3
0, 1, 4, 6	0, 1, 2, 2, 3, 1
0, 1, 4, 6, 7	0, 1, 2, 2, 3, 1, 4
0, 1, 4, 6, 7, 8	0, 1, 2, 2, 3, 1, 4, 5

 

수열의 최대 길이는 5가 된다.

 

아래는 cp와 dp의 계산 과정을 보여주는 코드이다.

 

nums = [0,2,5,4,6,1,7,8]
n = len(nums)-1
# 0은 그대로 두고, 뒤의 숫자를 교체하며 비교해보면 된다.
dp = [0, 1]
cp = [0, nums[1]]

for i in range(2, n+1):
    for j in range(len(cp)-1,-1,-1):
        if nums[i] > cp[j]:
            dp.append(j+1)
            if j+1 < len(cp):
                cp[j+1]=nums[i]
            else:
                cp.append(nums[i])
            print(cp,dp)
            break

 

 

아래는 정답 코드.

 

n = int(input())
nums = [0] + list(map(int,input().split()))
dp = [0, 1]
cp = [0, nums[1]]

for i in range(2, n+1):
    for j in range(len(cp)-1,-1,-1):
        if nums[i] > cp[j]:
            dp.append(j+1)
            if j+1 < len(cp):
                cp[j+1]=nums[i]
            else:
                cp.append(nums[i])
            break
print(max(dp))