문제

앞, 뒤 어느쪽에서 읽어도 동일한 염기서열을 pDNA (palindromic DNA) 라고 합니다. 예를 들어, AGA 는 pDNA 이지만, TAGCT 는 pDNA 가 아닙니다.

국방의 의무를 마치고 학교에 돌아온 진호는 보이지 않는 손에 의해 bioinformatics 를 연구하는 연구실의 인턴이 되어 있었습니다. 최근 진호가 맡은 과제는 pDNA를 찾는 것으로, 진호는 며칠간의 밤샘 작업을 통해 여러개의 pDNA 를 찾고 자신이 한 일에 보람을 느끼며 연구실에서 퇴근했습니다.

그런데, 모든 연구실의 사람들이 퇴근하여 아무도 없는 새벽에 만취 상태의 현환이가 들어와서 진호의 자리를 자신의 자리로 착각하고 그곳에 앉아서 컴퓨터를 쓰게 되었습니다. 평소에 바탕화면을 깨끗하게 쓰기로 유명한 현환이는 너무나 많은 바탕화면의 아이콘을 보고, '악성코드가 생겼나' 라는 생각을 하며 바탕화면에 있는 모든 것을 지워버렸습니다. 그런데 하필이면 진호가 찾은 pDNA의 데이터는 바탕화면에 저장이 되어 있었던 것입니다!

간만에 숙면을 하고 말끔해진 피부로 연구실에 나온 진호는 아침에 컴퓨터를 켜고나서 데이터가 지워진 사실을 알고 경악을 금치 못했습니다! 그리하여 부랴부랴 LastData 라는 복원 프로그램을 사용하여 복원을 시도하였으나, pDNA들이 조각 나고 순서가 뒤죽박죽 된 채로 복원이 되었습니다.

당황한 진호는 YUTAR Local Contest 에 참여하고 있는 절친인 당신에게 도움을 청했습니다. 교수님이 진호에게 진행 상황을 물어보는 랩미팅은 2009년 7월 5일 오후 6시 부터 이기 때문에, 그전까지 pDNA 데이터를 복원하는 프로그램을 작성해야 합니다!