LCS(Longest Common Subsequence) 개념,시간 복잡도 및 처리과정

Just Do It·2021년 12월 31일
0

Algorithm

목록 보기
3/6
post-thumbnail

📌 1. LCS 개념

Longest Common Subsequence의 약자. 우리 말로는 최장(최대) 공통 부분 수열이라 하며, 두 수열이 주어질 때 공통 부분 수열 중 가장 긴 값을 갖는 수열을 일컫는다.
유전자 비교, git, svn 등에 사용되는 알고리즘으로 동적계획법(Dynamic Programming) 유형 중 하나이다.


📌 2. 구현 방법

핵심 아이디어
두 배열 s1, s2 가 있을 때 처음 부터 각각의 i,j번째 까지를 그 배열의 접두사(prefix)라고 하자.
ex) A C A Y K P 배열의 4번째 까지의 접두사는 수열의 처음부터 4번째까지 즉, A C A Y 이 접두사가 된다.

두 배열 i, j 까지의 접두사의 LCS의 길이를 lcs[i][j]라고 정의한다. 이럴 경우 아래와 같은 점화식을 세울 수 있다.

lcs 의 길이 구하기

    1. 접두사의 길이를 1에서 부터 배열의 끝까지 점차 늘려가며 LCS의 길이를 이차원 배열에 저장한다.
    1. s1[i] 의 값과 s2[j]의 값이 같다면 (배열 상에서 대각 선으로 이동)
      lcs[i][j]=lcs[i-1][j-1]+1
    1. s1[i] 의 값과 s2[j]의 값이 다르다면
      lcs[i][j] = max( lcs[i-1][j], lcs[i][j-1] )
    1. s1의 길이를 n, s2의 길이를 m --> lcs[n][m] 이 lcs의 길이가 된다. lcs의 길이 뿐만 아니라 구성 요소 또한 구할 수 있다.

      LCS 구성 요소 구하기
      앞서 구한 lcs 배열을 역추적하여 특정 조건이 만족하면 벡터에 넣은 후, 마지막에 벡터를 뒤집어 구성 요소를 구할 수 있다.
  1. lcs[n][m] 에서 부터 출발
  2. 만약 lcs[i][j]==(lcs[i][j-1] or lcs[i-1][j])
    값이 같은 곳으로 이동한다(왼쪽 또는 위쪽으로 이동). 이때 둘 다 같으면 어느 방향으로 이동해도 상관 없음.
  3. else (lcs[i][j]!= (lcs[i][j-1] or lcs[i-1][j])
    해당값을 벡터에 넣고, lcs[i-1][j-1] 으로 이동한다
  4. lcs[i][j]가 0일때 까지 2,3을 반복한다.
  5. 사용한 벡터를 뒤집으면 구하고자 하는 lcs의 요소가 된다.

📌3. 시간 복잡도

두 시퀀스를 한번씩 순회하면서 이차원 배열을 작성하므로 O(nm)이 된다.(n= s1의 길이, m=s2의 길이)


📌4. 결론

LIS 에 이어 두 시퀀스를 가지고 동적계획법을 사용한다.
1. 두 시퀀스의 접두사에 대한 lcs 길이를 메모리에 저장해가며 n,m 까지의 lcs 길이를 구한다.
2. 이를 역추적하여 lcs를 구할 수 있다.

profile
조급해 하지 말고 한 계단 한 계단 오르기

0개의 댓글