[코드트리/INTERMEDIATE LOW] DP 최대 증가 부분 수열 Python 파이썬

 

목차

 

🔥 문제 링크

https://www.codetree.ai/missions/2/problems/longest-increasing-subsequence?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

🔥 문제 

 

 

🔥 풀이

dp 배열을 어떻게 채울지 고민.. 연습문제라 어렵진 않았다.

 

✅ 숫자 배열의 원소를 하나하나 점검하면서 값을 비교하고 dp 배열을 갱신한다

✔️ 수열은 자기자신을 채움으로서 무조건 1개 이상 존재하기 때문에 dp 배열을 1로 초기화하고 시작한다.

⚠️ 처음 dp배열을 0으로 채우고 시작할 거라면 arr 배열의 숫자 중 최대 증가 부분 수열의 시작이 되는 숫자들에 1을 갱신하는 추가 코드가 필요하다

dp 배열을 0으로 채울 경우

 

n = int(input())
arr = list(map(int, input().split()))
dp = [0]*n

for i in range(0, n):
    for j in range(i-1, -1, -1):
        if arr[i] > arr[j]:
            dp[i] = max(dp[j]+1, dp[i])

	#최대 증가 부분 수열의 시작이 되는 숫자들에 1을 갱신하는 추가 코드
    if dp[i] == 0:
        dp[i] = 1

print(max(dp))

 

✔️ 이중 반복문을 이용하여 각각의 값을 비교한다.

(1) 기준이 되는 index: 0부터 n까지 1씩 증가하는 for문

(2) 비교할 index: 기준이 되는 index부터 0까지 1씩 감소하는 for문

 

✔️ 만약 arr[비교 index]의 값이 arr[기준index]의 값보다 작다면 최대증가수열 조건에 만족하므로 dp 갱신을 시작한다.

- 현재 가지고 있는 최대증가수열개수와 비교index가 가진 최대증가수열의 개수+1 을 비교해 max값으로 갱신한다

 

✅ dp 배열을 완성한 후, dp 배열의 값 중 최대값이 최대증가수열의 개수이므로 max(dp) 출력한다

 

 

🔥 코드

n = int(input())
arr = list(map(int, input().split()))
dp = [1]*n

for i in range(0, n):
    for j in range(i-1, -1, -1):
        if arr[i] > arr[j]:
            dp[i] = max(dp[j]+1, dp[i])

print(max(dp))