[Python] 백준 14002번 - 가장 긴 증가하는 부분 수열 4 (골드 4)

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 다이나믹 프로그래밍 (DP)

 

 

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

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

 

 

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

---

 

유사한 유형이 많은 DP문제이다.

 

import sys
input = sys.stdin.readline

n = int(input())  # 요소의 개수를 입력 받음
data = [0]  # 기본 사례 처리를 위해 data 리스트를 0으로 초기화
data += list(map(int, input().split()))  # 시퀀스를 읽어 data에 추가

# dp 리스트 초기화, dp[i][0]은 i에서 끝나는 LIS의 길이를 저장하고, dp[i][1]은 LIS의 이전 요소 인덱스를 저장
dp = [[0 for _ in range(2)] for _ in range(n+1)]

length = 0  # LIS의 길이 저장 변수
length_idx = 0  # LIS의 마지막 요소의 인덱스 저장 변수

# 각 요소에 대해 LIS를 계산하는 루프
for i in range(1, n+1):
    for j in range(0, i):
        # 현재 요소가 j번째 요소보다 크면
        if data[i] > data[j]:
            # 이것이 LIS의 첫 번째 요소이거나 더 긴 LIS를 만드는 경우
            if dp[j][0] == 0:
                dp[i][0] = 1
            else:
                if dp[j][0]+1 > dp[i][0]:
                    dp[i][0] = dp[j][0]+1  # i에서 끝나는 LIS의 길이를 업데이트
                    dp[i][1] = j  # LIS의 이전 요소 인덱스를 업데이트
    # 전체 LIS의 길이와 마지막 요소의 인덱스를 필요한 경우 업데이트
    if length < dp[i][0]:
        length = dp[i][0]
        length_idx = i

# dp 테이블에서 결과 시퀀스를 재귀적으로 구성하는 함수
def makeResult(length, idx):
    if length == 0:
        return
    result.append(data[idx])
    makeResult(length-1, dp[idx][1])

result = []  # LIS를 저장할 결과 리스트 초기화
makeResult(length, length_idx)  # 결과 시퀀스 구성

result.reverse()  # 결과를 올바른 순서로 얻기 위해 뒤집음
print(length)  # LIS의 길이 출력
for i in result:  # LIS의 요소 출력
    print(i, end=' ')

 

 

숫자 시퀀스의 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)을 찾습니다. 시퀀스의 LIS는 각 요소가 이전 요소보다 큰 가장 긴 부분 수열입니다. 여기서 사용된 접근 방식은 동적 프로그래밍으로, 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 방법입니다.

1. 초기화: 프로그램은 요소의 수 n과 시퀀스 자체를 읽어들이고, 기본 사례를 쉽게 처리하기 위해 시퀀스의 시작 부분에 0을 추가합니다.
2. 동적 프로그래밍 테이블 (dp): dp[i][0]은 인덱스 i에서 끝나는 LIS의 길이를 저장하고, dp[i][1]은 LIS의 이전 요소의 인덱스를 저장하는 2D 리스트 dp를 초기화합니다. 이 구조는 길이가 계산된 후 LIS의 요소를 추적하는 데 도움이 됩니다.
3. LIS 계산: 메인 로직은 시퀀스를 반복하며, 중첩된 루프를 사용해 각 요소를 모든 이전 요소와 비교합니다. 더 큰 요소를 발견하면 이것이 더 긴 LIS로 이어지는지 확인합니다. 그렇다면 dp 테이블에 길이와 이전 인덱스를 업데이트합니다.
4. LIS 추출: dp 테이블이 완전히 채워지면, length_idx에 의해 식별된 LIS의 마지막 요소에서 시작하여 실제 시퀀스를 구성하기 위해 재귀 함수 makeResult를 사용하여 역추적합니다.
5. 출력: 마지막으로, 프로그램은 LIS의 길이와 그 시퀀스 자체를 출력합니다.

이 방법은 효율적이고 우아하며, LIS의 길이뿐만 아니라 실제 시퀀스도 찾을 수 있게 해주어 문제에 대한 포괄적인 해결책을 제공합니다.

 

내 코드를 gpt에게 던져서 주석과 글을 작성해달라고 하였다.