[알고리즘] 두가지의 LCS

팀 프로젝트하면서.. 결국에는 도입하지 않았지만

중간에 검색 기능 때문에 알아본  LCS라는 이론에 대해 생각하고 정리한 것들을 

나중에 까먹지 않게끔 적어놓으려 한다 

 

두 가지 뜻이 있다 

 

Longest Common Substring과 

Longest Commone Subsequence가 있다

 

보통 백준에서 나오는 문제는 두 번째 문제가 나온다..

 

정작 내가 필요한 녀석은 위에 놈이라서 위에 이론부터 사알짝 풀어본다

 

이해하면서 그린 표이다 (매우 개판이다)

 

표는 저렇게 나오는데 나는 이 이론을 deque를 이용하면 좀 더 간단하게 풀 수 있지 않을까 생각했다 

 

대충 이러하다

 

가로 배열 = ABACKD

세로 배열 = ACKDPB

 

임시 배열을 각 배열의 크기로 하나씩 만든다 

 

tmp1[A, B, A, C, K, D]

tmp2[A, C, K, D, P, B]

 

그리고 문자열을 담을 tmp3[]

 

tmp1[0]과 tmp2[0]을 비교해서 같다면

가로, 세로[0] leftpop (둘 다 같음)

tmp3.append(A)

 

이번에 가로[0+1], 세로[0+1]을 비교함 (B , C)

둘이 다르니 

ans.append(tmp3)

tmp 3= []

이번에는 tmp1[0+1] 그리고  tmp2[0]부터 비교를 시작한다

(B, A), 둘이 같지 않으니  tmp3=[], 배열 길이가 0이면 그냥 다음으로 넘어간다

 

tmp1[0+2] tmp2[0]  = (A, A)

같으니 tmp3에 추가, 다음으로 넘어가서 tmp[0+2+1], tmp[0+1] = (C, C)

같으니 tmp3에 추가.. 이런식으로 가다 보면 

ans[]은 a, ackd, ckd, d가 담기게 된다 제일 큰 단어인 ans[1]이 가장 긴 공통단어가 된다

 

단어의 인덱스 번호까지 필요하다면 물론 2차원 배열로 하는 게 맞다 

근데 단어만 뽑을 거면 굳이;; 2차원 배열을 안 써도 이런 식으로 풀 수도 있지 않을까도 생각했다..

 

또 다른 LCS인 공통부분 수열을 생각해보자 

 

여긴.. 그냥 간단하다 이번 경우는 index번호를 넘겨줘서..

같지 않으면 그냥 +0하고 다음 순으로 넘기지 않고 그대로 끝까지 보내면 된다

그러다 같으면 +1 다음으로 넘어가서 쭉 나오고.. 

 

머리로는 이해했는데 막상 말로 풀려니 약간 애매한 부분도 있기도 하다..

 

지금은 팀 프로젝트 기간이니 이걸 코드로 만들자니 시간도 좀 애매하고.. 마음의 여유도 없으니

 

국비 끝나면 파이썬으로 한번 만들어봐야겠다