가장긴증가하는부분수열(LIS)_DP/Binary Search
가장 긴 증가하는 부분수열의 개념 부분 수열이란, 본래 수열에서 일부 숫자를 지워 만들 수 있는 수열이다. 가장 긴 증가하는 부분 수열(LIS, Logest Increasing Subsequence)은 오름차순으로 증가하는 부분 수열 중에서 가장 긴(원소의 개수가 많은) 수열을 의미한다. 예를 들어, N = 7인 수열 {6, 2, 4, 3, 1, 4, 8}은 여러 부분 수열을 가진다. - {6, 4, 1}, {6, 8}, {3, 4}, {2, 3, 4} 등은 모두 부분수열이다. - 그 중에서 {2, 4, 8}, {4, 8}, {2, 3, 4}, {1, 4, 8} 등은 증가하는 부분 수열이다. - 가장 긴 증가하는 부분 수열은 길이가 4인 {2, 3, 4, 8} 이다. 가장 긴 증가하는 부분 수열의 길이는..
2022. 2. 20.
동적계획법(Dynamic Programming)
동적계획법에 대한 이해 피보나치 수열은 첫째항이 0, 둘째항이 1이고 이전 두항을 더해가며 새로운 항의 값을 구해나가는 수열이다. 0, 1, 1, 2, 3, 5, 8, 13 ... 과 같이 이어지며, 점화식은 다음과 같다. F(N) = F(N-1) + F(N-2) (N >= 2) F(0) = 0, F(1) = 1 N번째 항의 값을 구하는 문제는, N-1번째 항을 구하는 문제와 N-2번째 항을 구하는 문제로 나누어질 수 있다. 이렇게 큰 문제를 작은 문제로 나누어 풀 수 있는 경우를 최적 부분 구조(Optimal Structure) 라고 한다. 최적 부분 구조에 대해 자세히 말하면, 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다. 최적 부분 구조를 가지는 피보나치 수..
2021. 11. 17.