반응형 알고리즘1 [알고리즘] 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence) 가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence) 혹은 최장 증가 부분 수열은 대표적인 동적 계획법(Dynamic programming) 문제다. 아래와 같이 특정 길이의 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 찾는 것이 문제이다. 아래 예시에서는 {10, 20, 30, 50}의 부분 수열이 수열 A의 가장 긴 증가하는 부분 수열이고 길이는 4이다. A = {10, 20, 30, 15, 25, 50} 가장 긴 증가하는 부분 수열 문제는 간단한 O(N^2)의 알고리즘과 조금 복잡한 O(N log N) 두 가지 알고리즘으로 해결 가능하다. O(N^2) 알고리즘 동적 계획법에서는 어떻게 값을 재사용하는가를 결정하는 .. 2021. 1. 31. 이전 1 다음 반응형
