Baekjoon_14002

Baekjoon_14002

문제

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 A_i가 주어진다. (1 ≤ A_i ≤ 1,000)

출력

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

a = int(input())
arr = list(map(int,input().split()))
# dp 배열 초기화
dp = [[arr[i]] for i in range(a)]

# 동적 계획법으로 부분 수열 업데이트
for i in range(1, a):
    for j in range(i):
        if dp[j][-1] < arr[i]:
            # 최대 부분 수열 업데이트
            if len(dp[i]) < len(dp[j]) + 1:
                dp[i] = dp[j] + [arr[i]]

# 가장 긴 증가하는 부분 수열 찾기
lis = max(dp, key=len)
print(len(lis))  # 부분 수열의 길이
for l in lis:
	print(l,end=" ")

Baekjoon 문제 14002를 해결하는 데 동적 계획법(Dynamic Programming, DP)을 사용한 이유와 코드의 절차를 설명해드리겠습니다.

동적 계획법(DP)을 사용한 이유

DP은 복잡한 문제를 더 작은 하위 문제로 나누고, 각 하위 문제의 해결책을 저장하여 중복 계산을 피함으로써 효율적으로 문제를 해결하는 방법입니다.
이 문제에서는 "가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, ⚙️ LIS)"을 찾아야 합니다.
LIS 문제는 하위 문제의 해를 활용하여 전체 문제를 해결하는 대표적인 동적 계획법 문제입니다.

코드의 절차적 설명

1. 입력 받기: 수열의 크기 a와 수열 arr을 입력받습니다.

2. DP 배열 초기화: 각 원소를 시작으로 하는 부분 수열을 저장할 dp 배열을 초기화합니다. 초기에는 각 원소를 단일 원소 수열로 간주합니다.

3. 동적 계획법으로 부분 수열 업데이트:

   • for i in range(1, a): 수열의 각 원소에 대해 반복합니다.
   • for j in range(i): 현재 원소 i 이전의 모든 원소에 대해 반복합니다.
   • if dp[j][-1] < arr[i]: i번째 원소가 j번째 원소로 끝나는 부분 수열의 마지막 원소보다 큰 경우, 증가하는 부분 수열을 만들 수 있습니다.
   • if len(dp[i]) < len(dp[j]) + 1: 현재 i번째 원소를 포함하는 부분 수열의 길이가, j번째 원소로 끝나는 부분 수열에 i번째 원소를 추가한 길이보다 작다면, dp[i]를 업데이트합니다.

4. 가장 긴 증가하는 부분 수열 찾기:

   • lis = max(dp, key=len): dp 배열에서 가장 긴 부분 수열을 찾습니다.
   • print(len(lis)): 부분 수열의 길이를 출력합니다.
   • for l in lis: print(l, end=" "): 부분 수열을 출력합니다.

반복 절차의 예시

1. 첫 번째 반복 (i = 1):
   • [[10], [10, 20], [10], [30], [20], [50]]
2. 두 번째 반복 (i = 2):
   • [[10], [10, 20], [10], [30], [20], [50]]
3. 세 번째 반복 (i = 3):
   • [[10], [10, 20], [10], [10, 20, 30], [20], [50]]
4. 네 번째 반복 (i = 4):
   • [[10], [10, 20], [10], [10, 20, 30], [10, 20], [50]]
5. 다섯 번째 반복 (i = 5):
   • [[10], [10, 20], [10], [10, 20, 30], [10, 20], [10, 20, 30, 50]]

최종적으로 가장 긴 증가하는 부분 수열의 길이는 4이며, 해당 부분 수열은 [10, 20, 30, 50]입니다.
최종적으로 [10, 20, 30, 50]이라는 가장 긴 증가하는 부분 수열을 찾게 되며, 이의 길이는 4입니다.

이렇게 동적 계획법을 통해 문제를 효율적으로 해결할 수 있습니다. 이 방법은 각 단계에서 이전 단계의 결과를 활용하여, 전체적인 계산 시간을 단축시키는 데에 중요한 역할을 합니다.