[쉬운 설명] 백준 9251 : LCS( Longest Common Substring ) 길이 찾기

www.acmicpc.net/problem/9251

9251번: LCS

전체적인 이 문제 감상평 :

 

 DP문제는 진짜 문제를 많이 풀어봐야겠네요.

솔직히 말해서, 테이블을 만들어서,  dp를 진행하는 아이디어를 쌩으로 떠올리기에는 어려움이 많죠.

많이 풀어보면서 감을 익혀야할 것 같아요.

이번 하반기에 코테를 9 ~ 10개를 보면서 느낀 거지만, 변별력을 만드는 문제로 꼭, 이 디피 문제가 나왔어요.

백준에 있는 단계별 풀어보기에 동적 프로그래밍은 꼭 풀어보기를 권합니다.

 

 

이 문제 풀이의 방향성 :

문제를 쪼개서 생각해보죠. 전형적인 디피 유형을 다루는 방법이죠.

문제를 매우 작은 유닛으로 나눠서 직접 해본다. 그러다보면 패턴이 나온다.

 

" ACAYKP <-> CAPCAK "

 

 우선 빈 문자열 ""과 "C" "CA" "CAP" "CAPC" "CAPCA" "CAPCAK"의 LCS길이는 모두 0일 것입니다. 왜냐면, 빈 문자열과 어떤 공통된 부분 문자열이 있겠습니까? 없죠.

 

 이제 첫 번째 문자열에서 "A"를 기준으로 생각해보죠.  

"C" : 0개

"CA" : 1개

"CAP" : 1개

"CAPC" : 1개

"CAPCA" : 1개

"CAPCAK" : 1개

맞죠?

 

 이 원리를 그대로 적용해서 다음의 표를 채워 나가 보세요. 스스로. 두 번째 줄까지는, 써놨습니다.

연습해봐요 : )

 자세히 살펴보면, 이 표에서 다음과 같은 패턴을 찾을 수 있습니다. 현재 비교되고 있는 행과 열의 글자가 같으면, 두 단어 모두에서 딱 이전 번째 글자까지의 LCS에 1을 더해서 자신의 칸의 값으로 취하면 됩니다. 만약 같지 않으면요? 그러면, 단어1에서의 이전 번째 글자까지와 단어2의 현재 번째 글자까지의 LCS와 <-> 단어2에서의 이전 번째 글자까지와 단어1의 현재 번째 글자까지의 LCS 중 최댓값을 취한 것이 곧 현재 칸의 LCS 값이 됩니다. 이렇게 부분 부분 나누어서, 점점 쌓아나가는 거고, 그러기에는 표 구조를 쓰는 게 쉽겠죠? ( 사실 지금 저로서는 전혀 떠올릴 수 없습니다만 ... )

 

마져 표를 채워볼게요.

예시에 나온 것은 이렇게 나오겠네요.  아이디어를 경험해보기 이전엔 매우 창의적이어야 풀 수 있는 문제 같아요. 아무튼 저는 그래요  : ( 

 

곧 단어 전체에 대한 답은, 저 표의 마지막 칸( 오른쪽 대각선 마지막 )의 4가 되겠네요. 

 

 

이번 문제 LCS의 기본적인 아이디어 마지막으로 짚고 넘어가도록 하죠 :

 

" 단어1, 단어2의 이번 글자 까지의 최장 공통 부분은, 

   

    만약 각 단어의 "이번 글자"가 같다면,

 

        각 단어의 이전 글자까지의 최장 공통 부분 길이 + 1

 

    만약 이번 각 단어의 "이번 글자"가 일치하지 않는 다면,

 

        밑의 두개 중 최대값을 취한다.

           

             1. 단어1의 이전 글자 까지와 단어2의 이번 글자까지의 최장 공통부문 길이.

             2. 단어2의 이전 글자 까지와 단어1의 이번 글자까지의 최장 공통부문 길이.

 

     이 방식으로 표를 만들어, 각 단어의 처음부터 끝까지를 비교하여, 결국, 두 단어의 최장 공통 길이를 구한다. "

 

 

 

결론 : 

  백준에서 이런 문제를 많이 만나서, 언제 표를 그리면 더 수월할지 감을 기르자. 이상입니다.