코딩스토리

오랜만에 블로그에 알고리즘 관련 글을 작성하는 것 같은데.. 절대 알고리즘에 손을 놓고 있던 게 아니라 우리 학교 알고리즘 소학회에 참여하느라 ㅎㅎ.. ( KOALA 뽜이팅!!) LCS 알고리즘은 DP를 공부했던 시점부터 계속 공부해야지, 공부해야지 했던 알고리즘인데 결국 오늘에서야 공부했다. ( 다음 주 학회의 주제가 마침 DP여서도 있고 ) 어쨌든 LCS 알고리즘에 대해 알아보면 Longest Common Subsequence, 즉 최장 공통부분 수열이라는 뜻이다. 만약 ACAYKP 란 문자열과 CAPCAK 란 두 개의 문자열이 주어졌을 때, LCS = ACAK 가 된다. 최장 길이 문자열과 살짝 헷갈릴 수 있는데, 우리가 구해야 하는 LCS는 최장 부분 공통 수열, 즉 수열이다. 수열이란 뜻은 결국..