LCS (Longest Common Sequence) 알고리즘

이미지 출처

 

i랑 j for문 2개 돌리면서 순회하는데,

 

첫번째 문자열의 i번째 글자랑
두번째 문자열의 j번째 글자를 비교한다.

 

다르면 왼쪽 칸, 위쪽 칸 중 최댓값을 가져오고
같으면 왼쪽 위 대각선 칸 값에서 1 더한 값을 넣는다.

 

그림과 이야기로 설명을 해보자.

 

첫번째 문자열의 2번째 글자 (AB에서 B)
두번째 문자열의 3번째 글자 (GBC에서 C)가
다른 걸 발견함
→ "B랑 C 비교했더니 다르네. 부분 순열에 같이 포함 못 시키겠다."
→ 1. B만 넣은 AB하고, C를 안 넣은 GB의 공통 순열 길이는 B 1개
→ 2. B를 안 넣은 A하고, C를 넣은 GBC를 공통 순열 길이는 0개
→ "1.의 결과를 골라서 순열의 다음 글자로 B를 추가하면 되겠다."

 

아니 뭐하러 결과를 두개나 비교함? 그냥 B 넣은 AB하고 C 넣은 GBC를 비교하면 되는거 아님?
→ 이전 결과 두 개 중의 최댓값이 이번 결과값인데 뭐하러 또 비교를 해서 연산 늘림? 이렇게 연산 줄이는게 dp잖음.

 

첫번째 문자열의 3번째 글자 (ABC에서 C)
두번째 문자열의 3번째 글자 (GBC에서 C)가
같은 걸 발견함
→ "C랑 C 비교했더니 같네. C를 부분 순열에 포함시켜야겠다."
→ "C랑 C 비교하기 전에 AB랑 GB 비교했을 때 부분순열 길이 몇이었음? 거기에 1개 더 추가하면 됨."