본문 바로가기

코딩테스트 준비

[알고리즘 강의] DP5. 최장 증가 부분 수열(LIS)

https://www.youtube.com/watch?v=sYh62pujaH8 

최장 증가 부분 수열 설명을 잘하여 스크랩함

핵심은 다음과 같다

dp[i] 는 마지막으로 뽑은 수가 array[i] 일때 가장 긴 부분 수열의 길이

따라서 dp[i] 는 모든 0<=j<i 에 대하여 

if array[j] < arrray[i] 인 경우들 중 

dp[i] = max(dp[i], dp[j]+1) 것을 찾으면 됨

 

# 11053번
x = int(input())

arr = list(map(int, input().split()))

dp = [1 for i in range(x)]

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

print(max(dp))

https://seohyun0120.tistory.com/entry/%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4LIS-%EC%99%84%EC%A0%84-%EC%A0%95%EB%B3%B5-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC

 

가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬

최근 들어, 알고리즘에 재미를 붙였다. 백준 문제를 풀면 문제 난이도마다 티어가 올라가는 재밌는 사이트(solved.ac)가 생겨서 뭔가 동기 부여되는 것 같다. 언어는 python을 사용하고 있다. (취준

seohyun0120.tistory.com