junie   8년 전

LCS를 DP로 구하는 9251 (LCS1) 문제는 풀 수 있었습니다.

하지만 LCS를 재추적해서 실제 LCS를 출력하는 부분에서는 잘 모르겠더라구요..


여러가지 방법을 생각해 볼 수 있었습니다.


1. mem[i][j] > mem[i+1][j] && mem[i][j] > mem[i][j+1] 일 때 이 수가 LCS에 포함된다고 생각하기

반례 : abbbbb, baaaaa

2. mem[i][j] > mem[i+1][j+1]일 때 이 수가 LCS에 포함된다고 생각하기

반례 : friend, member

3. (아래에 나와있는 코드) i, j를 이동해가면서 a[i] == b[j] 일 때 이 수를 LCS에 포함시키기

반례 : 또다시 abbbbb, baaaaa


흐아...

어떻게 해야 LCS를 어떤 경우에서도 재구성해낼 수 있을까요?

algoshipda   8년 전

일단 dp 테이블을 다 채워놓은 다음에 i, j 에 있을떄 a[i]==b[j]이면 i-1, j-1로 가면서 i,j를 답에 포함시키구요 a[i]!=b[j]라면 dp[i][j] == dp[i-1][j] 일때 i-1, j로 또는 dp[i][j] == dp[i][j-1] 일때 i, j-1로 타고가면 될것 같네요

algoshipda   8년 전

그리고 처음에 제일 끝 글자부터 타고가시면 될거에요

junie   8년 전

우와 정말 빠르고 명쾌한 답변 감사드려요!! ㅠㅠㅠ

하루종일 고민하고 있었는데 ㅎㅎㅎ

댓글을 작성하려면 로그인해야 합니다.