다이나믹 프로그래밍 적용단계
1. 최적해의 구조와 특징을 찾는다.
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 계산한다.
4. 계산된 정보들로부터 최적해를 구성한다.
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 계산한다.
4. 계산된 정보들로부터 최적해를 구성한다.
BOJ 11478 - 서로 다른 부분 문자열의 개수
길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) : http://ideone.com/bugbDy 코드 (해싱) : http://ideone.com/hkjw5n
댓글
댓글 쓰기