다음은 두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS)의 길이를 구하는 Java 프로그램입니다.
예제 코드
public class Demo{
int subseq(char[] a, char[] b, int a_len, int b_len){
int my_arr[][] = new int[a_len + 1][b_len + 1];
for (int i = 0; i <= a_len; i++){
for (int j = 0; j <= b_len; j++){
if (i == 0 || j == 0)
my_arr[i][j] = 0;
else if (a[i - 1] == b[j - 1])
my_arr[i][j] = my_arr[i - 1][j - 1] + 1;
else
my_arr[i][j] = max_val(my_arr[i - 1][j], my_arr[i][j - 1]);
}
}
return my_arr[a_len][b_len];
}
int max_val(int val_1, int val_2){
return (val_1 > val_2) ? val_1 : val_2;
}
public static void main(String[] args){
Demo my_inst = new Demo();
String my_str_1 = "MNSQR";
String my_str_2 = "PSQR";
char[] a = my_str_1.toCharArray();
char[] b = my_str_2.toCharArray();
int a_len = a.length;
int b_len = b.length;
System.out.println("The length of the longest common subsequence is"+ " " + my_inst.subseq(a, b, a_len, b_len));
}
}출력 결과
The length of the longest common subsequence is 3
코드 설명
Demo라는 이름의 클래스 안에는 subseq라는 함수가 정의되어 있으며, 이 함수는 주어진 두 문자열 str_1[0 ~ len(str_1)-1]과 str_2[0 ~ len(str_2)-1]에 대한 최장 공통 부분 수열의 길이를 반환합니다. 두 개의 for 루프가 각 문자열의 길이만큼 반복되면서 2차원 배열을 채워 나가는데, i와 j 중 하나라도 0이면 해당 인덱스의 배열 값은 0으로 설정됩니다. 그 외의 경우에는 my_arr[첫 번째 문자열 길이 + 1][두 번째 문자열 길이 + 1] 크기의 테이블이 순차적으로 완성됩니다.
main 함수에서는 Demo 클래스의 새 인스턴스를 생성한 뒤 두 개의 문자열 my_str_1("MNSQR")과 my_str_2("PSQR")을 정의합니다. 두 문자열은 각각 toCharArray() 메서드를 통해 문자 배열로 변환되고, 그 길이는 별도의 변수에 저장됩니다. 마지막으로 이 값들을 인자로 전달하여 subseq 함수를 호출하고 결과를 출력합니다.
동적 계획법(Dynamic Programming) 활용
이 프로그램은 동적 계획법 기법을 활용한 대표적인 예입니다. 한 번 계산한 값은 배열(테이블)에 저장해 두기 때문에, 재귀 방식에서 발생하는 것처럼 동일한 값을 여러 번 반복해서 계산할 필요가 없습니다. 이전에 계산된 요소가 필요할 때마다 배열에서 바로 가져와 사용하므로 실행 효율이 크게 향상됩니다.
LCS 알고리즘은 단순히 학습용 예제를 넘어, 파일 비교(diff) 도구, 버전 관리 시스템, DNA 서열 분석과 같은 생물정보학 분야 등 실무에서도 폭넓게 활용되는 핵심 알고리즘입니다.