LIS 최장증가수열

728x90

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

[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)

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

기본문제:

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

문제 바로가기 문제 : 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10

windy7271.tistory.com

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

windy7271