[DP] LCS(Longest Common Subsequence) 알고리듬

1. 문제정의

  LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. 우리가 알고 있는 substring과 비교하면 substring은 연속된 부분 문자열이고 subsequence는 연속적이지는 않은 부분 문자열이다.

 예로 들어 Iamhungry라는 문자열에서 연속된 부분 문자열인 mhun은 substring이 되고 연속적으로 이어지지는 않았지만 순서는 맞는 mugy는 subsequence가 된다.

그러면 LCS는 어디에 쓰일까? 대표적으로 LCS가 쓰이는 곳은 염기서열 유사성 분석이다. 이외에도 음파 단어 검색 및 교정 등에 사용된다.

---

2. 문제 설계

 

Dynamic Programming기법으로 문제를 해결하여 두 문자열 크기에 해당하는 2차원 배열의 값을 채우므로 Big-O는 O(n*m)이다. 일반적으로 O(n^2)은 n의 최대 크기가 5000일 때, 1초안에 답을 낼 수 있다. 결과적으로 문자열 크기가 약 5000이하일 때, 1초안에 답을 낼 것으로 예상된다.

 

---

3. 구현

#include<stdio.h>
#include<math.h>
#include<string.h>
#define Max(x,y) ((x)>(y)?(x):(y))
#define MAX 100

int lcs (char* X,char* Y,int m,int n ){
  if(m ==0|| n ==0)
    return 0;
  if(X[m-1]== Y[n-1])
    return 1+ lcs(X, Y, m-1, n-1);
  else
    return Max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

void main(){
  char s1[MAX], s2[MAX];
  int m, n, OUTPUT;
  scanf("%s",s1);
  scanf("%s",s2);

  m = strlen(s1);
  n = strlen(s2);

  OUTPUT = lcs(s1, s2, m, n);
  printf("%d", OUTPUT);
}

---

4. 테스트