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) 그것을 식으로 나타나면 이렇게 된다. 기본문제: h..
2023. 6. 13.