LCS(최장 공통부분 수열) 알고리즘은 두 개의 문자열에서 가장 긴 공통부분 수열을 찾는 알고리즘이다. 예를 들어 ACAYKP와 CAPCAK의 LCS는 ACAK로 길이는 4이다. LCS 알고리즘은 동적 프로그래밍으로 효율적으로 구현할 수 있다. dp[i][j]는 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지의 LCS 값이다. 알고리즘의 동작 단계는 다음과 같다. 1. 초기 조건 설정 각 문자열 앞에 0을 두어서 초기 조건을 설정한다. 이런 식으로 초기 조건을 설정하는 이유는 효율성이나 안정성 같은 측면에서는 영향이 없지만, 가독성과 코드 이해에 도움이 된다. dp [0][j] = 0, dp [i][0] = 0으로 설정한다. 초기 조건을 설정함으로써 다음에 나올 점화식을 초기 조건 ..

5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 예제 ABRACADABRA ECADADABRBCRDARA ans : 5 ------------------------------ UPWJCIRUCAXIIRGL SBQNYBSBZDFNEV ans : 0 LCS와 유사하지만 이 문제는 공통부분 문자열이 연속되어야 한다는 점이 다르다. 예를 들어 ABCD와 ABDC의 공통부분 문자열 중 BD는 존재하지 않는다. 풀이는 처음부터 LCS를 고려하고 생각했다. 그 외의 방법은 떠오르지도 않아서 일단 LCS처럼 2차..