LCS problem 이라고
longest common subsequence준말인데,
이거 푸는거랑 longest palindrome subsequence (LPS) problem이랑 똑같은거 아니냐?
LCS는 두 Sequence
X = A1 A2... An
Y = B1 B2... Bn
에서 매칭되는 가장 긴 subsequence찾는 문제고,
LPS는 Sequence에서 앞으로 읽나 뒤로 읽나 같은 subsequence 찾는 문젠데
LPS에서 주어진 Sequence를 역순으로 바꾼 다음에
X = A1 A2 ... An<input type="image" src="http://nstatic.dcinside.com/dgn/gallery/images/btn_save.gif" alt="저장"></p>
Y = An An-1 ... A1
이렇게 두고 LCS문제처럼 풀면 되는거아님?
누가 설명좀
아니 다르지 lcs가 더 고난도지 - DCW
단순히 겹치는 부분을 찾아내는걸 넘어서 가장 큰 부분을 찾는거니까 - DCW
lcs 알고리즘을 구현한뒤에 회문 찾았을시 공통부분이 전체 문자열이면 뭐 니말대로 회문 맞겟지 근데 이건 lcs가 더 강력하니 그렇게 할수 있다는거지 이거나 그거나의 문제가 아니 - DCW
여담이지만 lcs를 쉽게 이해하려면 다이나믹을 잘 해야하는거 같음 ㅠ
ㄴ씹죶 그니까 LCS에서는 두개의 일련에서 가장 긴 섭시퀀스를 찾는거고, LPS문제는 ABCDBA라고 하면 앞으로 읽고나 뒤로 읽거나 해서 같은 섭시퀀스인 ABCBA찾는 건데, 이거를
ABCDBA하고 ABDCBA 역순으로 바꿔서 두개의 LCS를 찾는 문제랑 동치아니냐고 물어본건뎅