다이나믹 프로그래밍1

• 다이나믹 프로그래밍 - LCS, LIS 차이 LCS 가장 긴 공통 부분 수열 (공통적으로 일치하는 수열 중 가장 긴 부분) 유사문제(백준) 편집 거리 (서로 다른 두 단어의 변경 횟수) LIS 가장 긴 증가(또는 감소)하는 수열 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 부분 수열이라고 하며, 이 수열이 오름차순(또는 내림차순)을 유지하면 증가(또는 감소)하는 부분 수열이 되는 것 유사문제(백준) 병사 배치 가장 긴 증가하는 부분 수열 문제 LIS를 n - log n에 구할 수 있지만, 요소를 확인할 수 있는 정확한 답은 아니라는 것을 알아야 한다. 단순한 길이는 n^2 이나 n-logn이랑 같다. Algorithm 2023. 2. 12.