다이나믹 프로그래밍 - LCS, LIS 차이

LCS

가장 긴 공통 부분 수열 (공통적으로 일치하는 수열 중 가장 긴 부분)

• 유사문제(백준)
  • 편집 거리 (서로 다른 두 단어의 변경 횟수)

LIS

가장 긴 증가(또는 감소)하는 수열

• 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 부분 수열이라고 하며, 이 수열이 오름차순(또는 내림차순)을 유지하면 증가(또는 감소)하는 부분 수열이 되는 것
• 유사문제(백준)
  • 병사 배치
  • 가장 긴 증가하는 부분 수열 문제
• LIS를 n - log n에 구할 수 있지만, 요소를 확인할 수 있는 정확한 답은 아니라는 것을 알아야 한다.
  • 단순한 길이는 n^2 이나 n-logn이랑 같다.