5582 공통 부분 문자열

5582 공통 부분 문자열 / c++ / Gold5 / 19분

문제 및 코드

풀이 과정

문자열 / 동적 프로그래밍

1. 두 문자열 A, B가 주어질 때, 공통 부분 문자열의 길이 중 최대값을 출려하는 문제
2. 동적 프로그래밍으로 최장 공통 부분 문자열(LCS, Longest Common Substring)알고리즘을 사용한다.
3. 각 문자열의 길이를 행과 열 크기로 갖는 2차원 행렬을 선언한 뒤, 2중 순회를 통해 아래의 로직을 반복
   1. A[i] == B[j] 이라면, dp[i][j] = dp[i-1][j-1] + 1
   2. 아니라면, 초기값 그대로 0
4. 이 때, 나온 최대값을 Answer 에 갱신
5. Answer 를 출력
6. 해결

회고

1. 예전에 풀어봤던 알고리즘이라 금방 풀 수 있었다. 덕분에 까먹을랑말랑 했던 알고리즘을 복습할 수 있어서 좋았다.
2. LCS는 최장 공통 부분 문자열(Longest Common Substring)과 최장 공통 부분 수열(Longest Common Subsequence)로 나뉜다. 이는 결과물의 연속성에 따라 다르다.
3. 최장 공통 부분 수열의 경우 결과가 연속되지 않아도 되므로, A[i] != B[j]인 경우, dp[i-1][j]의 값과 dp[i][j-1]의 값 중 큰 값을 취한다.
4. 반면, A[i] == B[j]인 경우에는 마찬가지로 dp[i-1][j-1] + 1의 값을 취한다.
5. 여기서 약간의 최적화 방법은 dp 배열으 각 문자열의 크기 + 1로 선언해두고 진행하는 것이다. 그러면 dp[i-1][j-1]을 검사할 때, i와 j가 음수로 떨어지는 조건을 체크하지 않아도 돼서 효율이 올라간다.