Code › algorithm-study
LeetCode 300 - Longest Increasing Subsequence
각 위치에서 끝나는 증가 부분 수열의 길이를 저장하는 O(n²) DP Python 풀이
배열에서 가장 긴 strictly increasing subsequence의 길이를 구하는 Medium 문제다. 연속된 구간을 찾는 문제가 아니라 떨어진 원소도 순서를 유지하면 선택할 수 있어서, 각 위치에서 끝나는 최장 증가 부분 수열의 길이를 저장하는 DP로 풀었다.
문제 링크 & 설명
- 문제 링크: 300. Longest Increasing Subsequence
- 요약: 정수 배열에서 원래 순서를 유지하며 일부 원소를 골랐을 때, 값이 계속 증가하는 가장 긴 부분 수열의 길이를 반환한다.
현재 숫자 하나만 선택해도 길이 1의 증가 부분 수열이 되므로 DP 배열은 모두 1로 시작한다. 이후 현재 위치보다 앞에 있는 원소들을 확인하며 이어 붙일 수 있는 수열을 찾는다.
접근 방법
dp[i]를 i번째 원소에서 끝나는 최장 증가 부분 수열의 길이로 정의했다. j가 i보다 앞에 있고 nums[j] < nums[i]라면, j에서 끝나는 수열 뒤에 i번째 원소를 붙일 수 있다.
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)마지막 원소가 전체 최장 수열의 끝이라는 보장은 없다. 그래서 반복이 끝난 뒤 dp[-1]이 아니라 전체 DP 배열의 최댓값을 반환한다.
예를 들어 [10, 9, 2, 5, 3, 7]에서는 7 앞의 2, 5, 3을 확인한다. 2 → 5 → 7과 2 → 3 → 7이 모두 가능하고, 그중 가장 긴 이전 상태에 1을 더해 7에서 끝나는 길이를 계산한다.
복잡도 분석
- 시간 복잡도: O(n²)
- 각 i마다 앞에 있는 모든 j를 확인한다.
- 공간 복잡도: O(n)
- 각 위치에서 끝나는 최장 길이를 DP 배열에 저장한다.
이 문제는 이진 탐색을 이용해 O(n log n)으로도 풀 수 있지만, 이번 구현은 dp[i]의 의미와 상태 전이를 직접 확인할 수 있는 O(n²) 풀이에 집중했다.
구현 코드
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)요약 및 회고
DP 상태를 전체 배열의 정답으로 잡기보다 특정 위치에서 끝나는 정답으로 좁히자 전이 조건이 명확해졌다. 이전 값이 현재 값보다 작을 때만 연결하고, 가능한 이전 상태 중 가장 긴 길이를 선택하면 된다. subsequence는 연속 구간이 아니라는 점과 최종 답이 DP 배열 어디에서든 나올 수 있다는 점을 함께 확인한 문제였다.