다이나믹 프로그래밍 유형

길이 $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

계속 읽기

인덱스트리(Indexed Tree)

1월 07, 2015

어떤 구간의 최대,최소를 O(lgN)에 알게 해주는 자료구조 정의되는 연산 1.) 원소값 갱신 2.) a~b의 최대 또는 최소값 반환 완전이진트리를 배열로 구현 ( 들어갈 원소 숫자만큼의 단말노드를 가질 수 있도록 크기를 조정 , 편의상 그냥 4 * N으로 잡으면 된다. 값은 단말노드를 통해서만 들어간다. 예 : 들어갈 원소가 9개라고 한다면 최소한 단말노드가 9개 여야 하므로 비단말노드 15개, 단말노드 16개를 가지는 완전이진트리 형태가 되어야 할것이다. ) 원소값 갱신: 원소가 하나 추가될때마다 부모노드와 비교하여 최대, 최소 ( 또는 다른 그 구간을 대표할만한)을 갱신한다. a~b의 최대,최소 반환: a (왼쪽끝 노드)에 있는 노드가 오른쪽노드일때 그 부모노드가 구간을 대표하는 값을 가질 수 없다는점을 이용하여 노드의 위치가 오른쪽일때는 그 오른쪽에 에 위치하는 왼쪽노드 (이 두 노드는 서로 다른 부모노드를 가진다.) 로, 왼쪽노드일때는 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 반대로 b(오른쪽끝 노드) 노드는 왼쪽노드일때 그 노드의 왼쪽에 있는 오른쪽노드, 오른쪽 노드일때 그 부모노드로 위치를 옮겨가면서 리턴값을 갱신한다. 두 위치가 교차되거나 겹칠때 루프를 종료한다. const int INF = 2e9 ; struct Tree { int first; vector<int> tree; Tree (int n) { for(first=1;first<n;first<<=1); tree = vector<int>( n<<2, INF); } void update (int pos, int val) { pos += first;

계속 읽기

블로그 검색

algoshipda의 블로그

다이나믹 프로그래밍 유형

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

인덱스트리(Indexed Tree)