목록최장 공통 부분수열 (1)

화분

[9251]LCS

이번 문제는 최장 공통 부분수열(LCS:Longest Common Subsequence)이다. 어떻게 동적계획법을 이용해 풀지 고민하다가 테이블에 어떻게 기록할진 떠올렸으나 코드로 구현할 방법은 떠오르지 않아 결국 인터넷을 참고하였다. 이 문제에 어떻게 접근했냐하면 우선 큰 문제를 해결하기 위한 공통된 작은 문제를 찾아내려 했다. 앞에서부터 공통된 문자를 찾기보단 뒤에서부터 찾으려 했다. 그 결과 다음과 같은 테이블을 완성했다. A C A Y K P C 3 A 4 2 P 1 C 3 A 2 2 K 1 가장 우측 하단 위치에서부터 왼쪽 행과 윗쪽 열의 안쪽에 있는 수를 증가시켜 나간다. 이렇게 접근하면 LCS를 만족하는 문자의 개수를 알아내는 실마리를 찾은거 같았다. 하지만 문제가 있었다. 어떻게 저 가장 ..
Study/CODINGTEST 2022. 2. 16. 15:18
이전 Prev 1 Next 다음