백준 9251: LCS ( 최장 공통 부분수열 {DP} / Swift )
두 개의 부분수열이 주어졌을 때, 가장 긴 공통 부분 수열을 구해야하는 문제이다. ACAYKP와 CAPCAK가 주어진다면 ACAYKP CAPCAK ACAK라는 부분 수열이 있기에 답은 4가 된다. Point 1: arr[i][j]가 나타내는 것은, a문자열의 i번째 요소를 b문자열의 j번째 요소까지 비교하였을 때 최장 공통 부분수열의 길이이다. Point 2: arr[i][j] = arr[i - 1][j - 1] + 1이다. 예를 들면, ACCC와 같이 b문자열이 진행되고, 현재 a문자열에서 C문자를 체크하고 있을 때, C가 나올 때마다 1씩 증가시키는 것은 말이 되지 않는다. 1 222와 같이 진행되는 것이 맞다. Point 3: arr[i - 1]과 b[j - 1]이 일치하지 않는 경우, arr[i]..
Swift알고리즘
2023. 9. 20. 19:39
