9251 LCS LCS 문제 해결 기법 두 수열 중 하나를 비교대상으로 잡고 나머지 수열의 문자열을 하나씩 추가하면서 공통 수열 길이 값을 table에 표시해준다. 문자열이 같으면 dp table에 저장을 하고, 다시 구하지 말자. dp table은 memoization 방식으로 이어나간다. 알고리즘 이 문제는 부분 수열 중 가장 긴 것을 찾는 것으로 그냥 숫자만 출력해주면 돼서 dp table에 같은 문자를 확인하면 +1 누적해주면 된다,, table 설명을 위해 i=6, j=4일 때를 예를 들어보자면 일단 table은 이중 for문으로 j가 먼저 돌고있는 상황이다. 그러니까 'ACAYKP'라는 문자열에 대해서 'CAPCAK'를 상대적으로 놓고 하나씩 비교를 하고 있는 것이다. 가장 긴 공통 문자열의 ..