devbelly

문제 www.acmicpc.net/problem/3257 알고리즘 다이나믹 프로그래밍 풀이 문자열 A,B와 그들을 섞은 C가 주어졌을 때 C의 문자들이 A에 속한 문자인지 B에 속한 문자인지 찾는 문제입니다. 단 C에서 문자열 A와 B는 원래 문자열의 순서를 유지합니다. C에서 A와 B가 원래 순서를 유지하므로 C[1:]로 문제가 작아졌을 때 주어진 A,B 또한 A[1:],B 또는 A,B[1:]로 좁혀나갈 수 있습니다. 부분구조가 성립하므로 다이나믹 프로그래밍을 사용하도록 합시다. $cache[i][j]$ = A문자열을 $i$번째까지 해결하고 B문자열을 $j$번째까지 해결했을 때, 해야하는 선택 즉 $cache[i][j]$값에 1이 들어있다면 $cache[i-1][j]$에서 A를 선택한 것이고, 반대로 ..

문제 https://www.acmicpc.net/problem/2401 알고리즘 KMP, 동적 계획법 풀이 직관적인, 나이브한 방법으로 생각을 해봅시다. 짧은 문자열들을 긴 문자열의 각 위치마다 일일이 매칭을 시도해보는 방법을 떠올릴 수 있습니다. 긴 문자열 $L$에서 짧은 문자열$I$이 시작할 수 있는 위치를 찾는데 한 개가 아닌 $N$개의 문자열에 대해서 해야 합니다. 우리는 이 방법을 최적화할 수 있는 방법을 알고 있습니다. 긴 문자열에서 짧은 문자열을 찾는 알고리즘. 즉 KMP입니다. 매칭은 빠르게 했으니 일일이 시도하는 문제는 동적 계획법을 통하여 풀 수 있습니다. 시간 복잡도는 $O(N(L+I)+NL)$입니다. 매칭한 결과를 저장할 수 있는 효율적인 방법을 생각해보도록 합시다. 처음에 저는 벡..