![[9252번] LCS 2](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fr5NDU%2FbtqxGvOu0HM%2FktubZsaDSUFg9kKgYKyrL0%2Fimg.png)
반응형
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
[이전 포스팅] 글의 다음 단계라고 할 수 있습니다.
방법은 간단합니다.
이전에는 길이만을 출력하게 했다면, 이번에는 역추적을 통한 검사를 추가로 포함시켜주면 됩니다.
역추적은 만들어진 DP table에서 길이 값이 같거나 하나 줄어드는 방향으로 움직이며 table 기준으로
아래에서 출발하여 위쪽으로 움직일 때마다 그 문자를 저장해주면 됩니다.
그 후에는 출력만 해주면 되겠죠.
기본적인 LCS 알고리즘에 대한 공부는 이것으로 이해되셨을겁니다.
이제는 이를 이용하여 풀 수 있는 문제에 도전해보는 건 어떨까요?
반응형