문제 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)$입니다. 매칭한 결과를 저장할 수 있는 효율적인 방법을 생각해보도록 합시다. 처음에 저는 벡..
- Total
- Today
- Yesterday
- 2-SAT
- spring boot
- kmp
- bfs
- 동적계획법
- sorting
- DP
- Fenwick
- hld
- 세그먼트트리
- union find
- sweeping
- 이분탐색
- SCC
- 이분매칭
- dfs
- Segment tree
- knapsack
- Suffix Array
- dijkstra
- 정렬
- string
- 좌표압축
- 스위핑
- implementation
- 트라이
- spring
- 펜윅트리
- greedy
- Oracle
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |