[Subsequence] LIS와 LCS

LIS와 LCS

---

1. LIS

2. LCS

---

1. LIS

LIS(Longest Increasing Subsequence)는 최장 증가 부분 수열입니다.

주어진 수열에서 원소들의 순서를 유지하면서 가장 긴 증가하는 부분 수열을 찾는 문제입니다.

 

10, 20, 10, 30, 20, 50 수열에서 LIS는 10, 20, 30, 50 입니다.

이를 찾는 방법은 동적 계획법과 이분 탐색+DP가 있습니다.

 

2. LCS

LCS(Longest Common Subsequence)는 최장 공통 부분 수열입니다.

두 개의 문자열에서 순서를 유지하면서 가장 긴 공통 부분 수열을 찾는 문제입니다.

 

문자열 A: ABCD 과 문자열 B: ACBD 에서 LCS는 ABD 또는 ACD 입니다.

이를 찾는 방법은 동적 계획법과 메모이제이션이 있습니다.

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3