longest common subsequence (1) 썸네일형 리스트형 [백준] 9251번 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 수열이 주어졌을때, 모두의 부분 수열이 되는 수열중 가장 긴 것을 찾아서 길이를 구하는게 문제의 목표이다. 해당 문제는 부르트포스 방법으로 문제를 해결 할 수 있으나 문자열의 길이가 N, M 일때 시간복잡도가 O(NM)이 걸린다. 하지만 다이나믹 프로그래밍을 적용하여 풀면 O(NM)으로 문제를 해결 할 수 있다. 1) 브루트포스 방식으로 문제 접근 .. 이전 1 다음
