LCS(Longest Common Subsequence, 최장 공통 부분 수열) LCS (Longest Common Subsequence)최장 공통 부분 수열두 문자열이 주어졌을 때, 두 문자열 모두에 순서를 유지하며 등장하는 가장 긴 부분 수열ex ) ACAYKP와 CAPCAK의 LCS는 길이가 4인 ACAK만약 brute force로 길이가 N인 문자열에 대해서 부분 수열을 구한다면? - > 2^N의 시간복잡도이를 다시 길이가 M인 문자열에 대해 확인해본다면 대략 O(2^N × M) .. 시간 초과DP (동적 계획법, Dynamic Programming) LCS는 문자열 각 문자의 위치에 대한 연산이 반복됨DP는 작은 문제의 답을 저장해두고, 이를 이용해 큰 문제의 답을 빠르게 구하는 방식ACAYKP..