[알고리즘] 가장 긴 증가하는 부분수열(LIS)
※ 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)이란? 부분 수열 중에서 각 원소가 이전 원소보다 큰 부분 수열 중에서 가장 긴 것! 예를 들어서, { 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 때, 증가하는 부분 수열은 { 2, 5 }, { 1, 4, 3} 등이 있지만 LIS는 { 2, 5, 7, 8 } 이다! 알고리즘은 시간복잡도에 따라서 2가지가 있다. ( O(N^2)과 O(N log N) ) 첫 번째 방법은 다이나믹 프로그래밍을 통한 방법이다. 시간 복잡도는 O(N^2) code#1 1 2 3 4 5 6 7 for (int i = 0; i arr[i]; } dp[0] = arr[0]; int idx = 0; for (int i = 1; i
2021. 6. 23.
