[백준/Python] 11053 : 가장 긴 증가하는 부분 수열

[백준/Python] 11053 : 가장 긴 증가하는 부분 수열

정답 코드 및 설명

N = int(input())
A = list(map(int, input().split()))

# DP 배열 초기화
dp = [1] * N  # 각 위치에서의 최대 증가 부분 수열 길이

# LIS 계산
for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j] + 1)

# 가장 긴 증가하는 부분 수열의 길이 출력
print(max(dp))

문제 이해

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence, LIS) 문제는 주어진 수열에서 특정 숫자들을 순서대로 선택했을 때, 이들이 증가하는 순서를 유지하면서 구성되는 가장 긴 부분의 부분 수열을 찾는 문제이다. 부분 수열은 주어진 수열의 원소들 중 일부를 순서대로 선택하여 구성되며, 선택된 원소들 사이에 다른 원소들이 있을 수 있다.

위 문제 해결 알고리즘 의사 코드

1. 입력 : 수열의 크기 N 과 수열 A 를 입력 받는다.

2. DP 배열 초기화 : 길이 N 의 배열 dp 를 생성하고 모든 값을 1로 초기화한다. dp[i] 가 의미하는 것은 위치 i 에서 끝나는 가장 긴 증가하는 부분 수열의 길이를 나타낸다.

3. LIS 계산하기

• 모든 위치 i에 대해 0 부터 i-1 까지의 위치 j 를 검사한다.
• 만약 A[i] 가 A[j] 보다 크다면, dp[i] 는 dp[j] +1 과 dp[i] 중 더 큰 값으로 변경한다
• 위 과정은 A[i] 가 A[j] 보다 크고, j 에서 끝나는 부분 수열 뒤에 A[i] 를 추가하여 더 긴 부분 수열을 만들 수 있음을 의미한다.

4. 결과 출력 : dp 배열 내에서 가장 큰 값을 출력한다.