LCS 알고리즘

이번 포스팅에서는 LCS 알고리즘에 대해 아래의 백준 문제를 예제로 소개해보겠습니다.https://www.acmicpc.net/problem/9251 Longest Common Subsequence / Longest Common Substring LCS란 최장 공통 부분 수열(Longest Common Subsequence) 혹은 최장 공통 부분 문자열(Longest Common Substring)을 뜻합니다. LCS를 구하는 알고리즘은 다이나믹 프로그래밍(DP) 알고리즘의 대표적인 유형으로, 어째서 DP인지는 글의 마지막 부분에서 설명하겠습니다.   먼저 최장 공통 부분 수열( Longest Common Subsequence ) 란 두 개 이상의 시퀸스[ACAYKP, CAPCAK]가  주어졌을 때, 가..

2024.05.24