CommonChild

생각했던 것

척봐도 LCS(Longest Common Sequence, Substring이 아니다.) 문제임을 알 수 있었다. 부분 수열이 무엇인지는 필요없고 개수만 파악하면 돼서 오히려 더 쉬운 문제였다.

진행

일반적인 LCS 풀이와 같이 했다. 0부터 시작하는 테이블을 만들어 두 문자열을 비교해가면서 두 문자가 같은 경우는 직전 문자열(테이블의 대각선 1칸 전의 값)까지의 개수 + 1을 해주고, 다른 경우에는 각 문자열의 직전 문자열(테이블의 아래, 위로 1칸 전의 값 중 최대값)까지의 개수를 가져오면 된다. 예컨대,

 

• 두 문자가 같은 경우
  • ABCD와 ACCB에서 세번째 C가 같기 때문에 AB, AC의 최장 수열 개수인 1(A만 공통)에서 1을 더해줘 2가 된다.
• 두문자가 다른 경우
  • ABCD와 ACCB에서 네번째 D와 B가 다르기 때문에 ABC, ACCB의 최장 수열 개수인 2(AC가 공통), ABCD, ACC의 최장 수열 개수인 2(마찬가지로 AC가 공통) 중 최대값인 2를 그대로 가져오면 된다.

만약 계산이 끝난 다음 최종 결과 수열을 알고 싶다면 대각선 방향으로 진행하며 값이 증가한 첫번째 포인트에 해당하는 문자를 이어 붙이면 된다. 다음에서는 "AB" 또는 "AC"가 된다.

결론

이 방법은 테이블에 각 진행을 기록하며 그 값을 기반으로 하는 메모이제이션을 사용한 DP라고 할 수 있다.

 

 

그림 출처 : https://twinw.tistory.com/126

LCS(Longest Common Subsequence) 알고리즘