14. 동적 계획법 1
CLASS 4 ESSENTIAL
두 문자열의 LCS를 구하는 문제입니다. 이 문제는 두 문자열의 길이+1를 각각 가로, 세로로 하는 DP 배열을 사용합니다. 각 원소는 첫 문자열의 i번째 문자까지의 substring과 두 번째 문자열의 j번째 문자까지의 substring이 주어졌을 때의 LCS 최대 길이입니다. 이제 DP 배열의 index 0인 행과 열은 놔두고, 나머지 칸에 대해서 문자열 1의 i번째 문자와 문자열 2의 j번째 문자가 같다면 a[i-1][j-1]+1을, 그렇지 않다면 a[i-1][j]과 a[i][j-1] 중 큰 값을 저장하는 것을 반복합니다. 마지막 행 마지막 열의 원소가 정답이 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2020-04-01 11:55:00 |