[알고리즘] LCS 길이 구하기와 LCS 출력하기

LCS(최장 공통부분 수열) 알고리즘은 두 개의 문자열에서 가장 긴 공통부분 수열을 찾는 알고리즘이다. 예를 들어 ACAYKP와 CAPCAK의 LCS는 ACAK로 길이는 4이다.

 

LCS 알고리즘은 동적 프로그래밍으로 효율적으로 구현할 수 있다. 

dp[i][j]는 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지의 LCS 값이다. 알고리즘의 동작 단계는 다음과 같다.

 

1. 초기 조건 설정

• 각 문자열 앞에 0을 두어서 초기 조건을 설정한다.
• 이런 식으로 초기 조건을 설정하는 이유는 효율성이나 안정성 같은 측면에서는 영향이 없지만, 가독성과 코드 이해에 도움이 된다.
• dp [0][j] = 0, dp [i][0] = 0으로 설정한다. 초기 조건을 설정함으로써 다음에 나올 점화식을 초기 조건 없이 바로 첫 문자부터 적용할 수 있다.

2. 점화식

if(str1[i] == str2[j])
	dp[i][j] = dp[i-1][j-1] + 1;
 else
 	dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

• i번째 문자와 j번째 문자가 서로 같다면 해당 문자를 LCS에 포함시킬 수 있다. 따라서 i-1까지와 j-1까지로 만든 문자열의 LCS에 1을 더하면 된다.
• i번째 문자와 j번째 문자가 서로 다르다면 이들 중 하나는 현재 step에서 LCS에 포함되지 않을 것이다. 따라서 현재 단계에서 둘 중 하나를 버린다고 생각하면 된다. 만약 dp [i-1][j]가 더 크다면 str1의 i번째 문자를 버리고 dp [i-1][j]를 현재 LCS값으로 사용하면 된다.
• 이 점화식을 떠올리는게 가장 어려운데 처음부터 논리적으로 접근하기보다는 dp [i][j]를 뭘로 둘지 생각한 다음 표를 먼저 채우면서 규칙을 발견하는 것도 괜찮은 방법이다. 

3. 위의 점화식대로 배열을 다 채우고나면 최장 공통부분 수열의 실제 값을 찾기 위해 백트래킹 작업을 수행한다.

• dp [len1, len2]을 시작점으로 둔다.
• 현재 위치에서 왼쪽 값과 위쪽 값, 왼쪽 위 대각선 값 중 큰 값을 선택하여 이동 방향을 결정한다.
• 이동한 방향이 왼쪽 위 대각선이라면 두 문자열에서 해당 위치의 문자가 일치하는 것이므로 LCS 결과에 추가한다.
• 위 과정을 계속 반복한다.