N log N1 가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) LIS는 어떠한 수열에서 증가하는 부분 수열중 길이가 가장 긴 수열를 뜻합니다. LIS를 찾는 알고리즘은 다이나믹 프로그래밍을 이용한 O(N^2) 알고리즘과 이보다는 좀 더 복잡한 O(N log N) 알고리즘이 있습니다. 부분 수열이란 어떠한 수열에서 일부 숫자를 지워서 만들 수 있는 새로운 수열을 의미합니다. O(N^2) O(N^2) 알고리즘은 비교적 간단하게 구현할 수 있습니다. dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이 dp[i]를 구하는 법은 1 ~ (i - 1)까지의 원소들 중 i번째 원소보다 값이 작은 것들 중 dp의 값이 가장 큰 것에 1을 더하면 된다. 즉, j = 1 ~ (i - 1)을 순회할 때, a[i]보다 a[j]가 작다면, dp[i] = max(dp[i], dp[.. 2020. 4. 7. 이전 1 다음