내가 보려고 만듬

https://prpn97.tistory.com/63 [다이나믹 프로그래밍] LCS, LCSS 란? 그리면서 이해하기 - 1 처음 문제를 접하며 도무지 이해가 안되서 정리해서 포스팅하며 되새기기 위해, 또한 나처럼 헤매고 있는 사람들이 있다면 답을 알기보다 과정들을 통해 이 알고리즘에 대해 이해하는데 도움이 prpn97.tistory.com 1편에 설명이 있으니 참고해도 좋을 것 같다. Longest Common Subsequence 바로 최장 공통 부분수열에 대해 알아보려 한다. 먼저 최장 공통 부분수열의 길이에 대해 배워보자. 이번에는 LCS[i-1][j-1] 이전에 확인해야 하는 것이 있다. 두 문자가 다르다면 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰값을 표시하고, 두 문자가 같..

처음 문제를 접하며 도무지 이해가 안되서 정리해서 포스팅하며 되새기기 위해, 또한 나처럼 헤매고 있는 사람들이 있다면 답을 알기보다 과정들을 통해 이 알고리즘에 대해 이해하는데 도움이 될까 싶어 하나하나 써내리려 한다. 구글링해보면, 많은 자료들이 있고, 함수로도 그림으로도 그려서 설명하는데, 바보인 나에겐 너무 어려워서, 초보의 시선에서 이해한대로 그려보려 한다. 먼저 LCS란 무엇인가. Longest Common Substring혹은, Subsequence 이다. 최장 공통 문자열 혹은 최장 공통 부분수열 이다. 문자열 ABCDEF / GBCDFE가 있다고 하자. 최장공통 문자열은 BCD / 최장 공통 부분수열은 BCDF, BCDE가 될 수 있다. 말 그대로 문자열을 비교해서 공통된 가장 긴 문자열 ..