문제

강산이 한번 변하고도 남는, 무려 12년 반이라는 기간 동안 한 학교에서 학사부터 박사까지 마친 Hwan은 우연찮은 기회를 잡아 먼 타향의 어느 의대 부속 연구소에서 박사후과정을 하게 되었다. 2개월 가량이 지나 어느 정도 적응을 마친 어느 날, 그가 속한 연구실의 교수는 그의 자리에 들러 갑작스레 새로운 프로젝트를 진행하자고 이야기 하였고, 이에 대한 간략한 설명을 전달하고 자리를 떠났다. 하지만 너무나 새로운 분야의 프로젝트에 참가하게 되었기 때문에 당장은 자신이 해야 하는 일이 무엇인지 알 수 없었으나, 박사과정에서 익힌 며칠간의 꾸준한 구글 검색 엔진을 통해 이번 프로젝트를 전산학의 문제로 치환하여 풀 수 있다는 것을 알게 되었다. Hwan이 정의한 문제인 maximal k$k$-edit subset이라는 문제는 다음과 같다.

우선 알파벳 A, C, G 그리고 T로 구성된 문자열들로 이뤄진 L$L$과 S$S$가 주어진다. 이때 L$L$의 모든 원소의 문자열의 길이는 모두 같고, S$S$의 모든 원소의 문자열의 길이는 같으며, 그리고 S$S$ 문자열의 길이는 L$L$보다 길거나 같다고 가정한다. 여기서 S$S$의 부분 집합 중, 모든 부분집합의 원소들이 적어도 한 개 이상의 L$L$에 속한 문자열과 k$k$ 이하의 Edit Distance(두 문자열을 일치하도록 만들기 위한 연산의 수, 이 때 문자의 삽입, 삭제 혹은 변경을 하는 경우를 한번의 연산으로 간주한다)를 갖는 부분문자열(substring)을 포함하고 있으면, 해당 부분집합을 k$k$-edit subset으로 정의할 수 있다. 이 문제에서는 가능한 k$k$-edit subset이 되는 경우 중 최대 크기를 찾아야한다.

Hwan은 문제를 잘 정의했지만, 다른 프로젝트도 진행하고 있던 중이였기 때문에 이 문제를 풀 코드를 작성할 시간이 없었고, 아직 영어의 장벽을 느끼고 있는지라 다른 연구실 동료들에게 부탁하기도 힘든 상태이다. 결국 그는 한국에 있는 문제 해결과 코딩에 조예가 깊고 친한 후배였던 당신에게 도움을 구하기로 했으며, 당신은 그의 사탕발림에 넘어가게 되어 이 문제를 해결해야 한다. 그리고 그는 마지막으로 한마디를 더 덧붙였다.
"데이터의 개수가 방대하니까 프로그램 수행시간이 아주 빨라야 할 거야!"