LIS 최장증가수열

최장증가수열이란 : 가장 긴 증가하는 수열을 말한다.

 

[1,4,3,6,4,8]

이런식으로 주어졌을때 가장 긴 증가하는 수열은

[1,3,4,8] 4이다.

 

이러한 문제를 풀때는 dp를 사용하여야 하는데, 각 idx까지의 최장증가 수열을 dp에 저장하는 것이다.

 

주어진 idx 보다는 작지만 가장 긴 수열에 + 1을 해주면된다. 

 

idx 가 0 일때 는 dp[0] = 1

1일때는 dp[1] = 2

dp[2] = 2

dp[3] = 3

dp[4] = 3

dp[5] = 4

 

이렇게 하려면 이중 포문을 사용해야한다.

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

 

그것을 식으로 나타나면 이렇게 된다. 

기본문제:

https://windy7271.tistory.com/entry/Python%F0%9F%A5%881%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1105%EB%B2%88%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%B4

(Python/🥈1)백준 알고리즘 1105번:가장 긴 증가하는 부분 수열

조금 부족해 보이지만 계속 공부해보면서 수정해 보도록하겠다.