원당이는 생명공학의 DNA 에 대해 연구 하고 있습니다. DNA의 염기서열은 adenine(A),thymine(T),guanine(G),cytosine(C) 와 같이 네가지로 구성되어 있습니다. 고릴라의 염기서열을 분석해 보니 GATACCAGATACCCA 와 같이 이루어져 있고 원숭이의 염기서열을 분석해 보니 AAGATTGCCATTATT 와 같이 이루어져 있는 것을 발견했습니다. 원당이는 이 두개의 염기서열에서 공통부분 서열 중에 최대로 긴 부분 서열을 구하고 싶습니다. 여기서 부분서열이란 원래 문자열에서 임의적으로 몇개의 문자를 제거하여 순서에 맞춰 빈칸 없이 합쳤을 때 만들 수 있는 문자열을 말합니다. 즉 ATGC 와 ATCT 의 가장긴 부분수열은 ATC 3개 입니다. ATGC 에서 G를 제거 하고 ..