jae_coding

문제 문제 링크 문제 접근 LCS: 최장 공통 부분 수열 ex)ACAYKP, CAPCAK -> ACAK output: LCS의 길이 예제로 문제를 접근해 보았다. x, y 축의 첫 항의 값은 모두 0으로 고정이다. (margin을 주기 위함) x, y 축에 cross하여 같은 것이 있으면 바로 위의 표 or 바로 왼쪽표 or 바로 왼쪽 위 대각선 표의 값에 + 1해주는 식의 알고리즘이다. 그렇지 않으면, 바로 위의 표 or 바로 왼쪽표 or 바로 왼쪽 위 대각선 표의 값 중 높은 값을 입력하면 된다. 잘 이해가 되지 않으니 그림으로 설명하겠다. 그림1 0 C A P C A K 0 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 A 0 1 Y 0 1 K 0 1 P 0 1 그림2 0 C A ..