트라이

알고리즘/자료구조 2015. 2. 27. 14:35 Posted by 아는 개발자

요즘 운영체제에서는 단어 몇글자만 치면 자동완성 기능을 제공하는데

자동완성의 기본 알고리즘이 바로 트라이다.


자동완성을 만들려면 사전에 입력한 단어들을 저장하고 빠른시간안에 탐색 할 수 있어야 한다. 하지만 문자열은 숫자로 이루어진 이진트리와 달리 원소 비교를 상수시간 내에 할 수 없으므로 특화된 자료구조가 필요하다. 이때 유용한 자료구조가 트라이다.


구조는 다음과 같다.


만약 내가 TR, THE, TRY, TREE라는 단어를 저장해두었다고 하자. 그러면 다음과 같은 트리가 형성된다. 각각의 단어의 공통된 접두사를 부모로 두는 방법이다. 하지만 공통된 접두사가 내가 입력한 단어가 아니라면 bool 값을 이용해서 표현해야한다. 그림에는 하얀색 바탕으로 표현했다. 위 자료구조의 시간 복잡도는 트리의 높이로 볼수 있고 트리의 높이는 단어의 최대 길이와 같으므로 O(L)로 정의 할 수 있겠다.


예를들어 내가 TRY라는 문자가 있는 지 확인하고 싶다면 첫 문자 T로 비교를 한 후 존재하면 R을 비교, 그 후에는 Y를 비교해서 내가 찾으려 하는 노드가 존재하는지, 그리고 존재하면 사전에 입력된 단어인지를 확인하면 된다.


위 자료구조의 단점은 메모리를 너무 많이 잡아먹는다는 것이다. 나는 지금 TR, THE, TRY, TREE 이렇게 네개만 입력했는데 벌써 6개의 node가 필요하니 단어의 개수가 늘어나면 추가 메모리가 더 많이 필요할 것이다.


문자열에 특화된 자료구조는 이번이 처음이다. 자주 써먹어야겠다.

728x90

'알고리즘 > 자료구조' 카테고리의 다른 글

union find  (0) 2015.06.27
오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24
KMP 알고리즘  (0) 2015.02.24

9489

알고리즘/acmicpc 2015. 2. 26. 23:35 Posted by 아는 개발자

예전에는 왜 이렇게 많이 틀렸을까 보니...


입력이 1 2로 시작하는 경우를 생각 안해서 그런것 같다

이런 경우는 트리가 두개 생길 수 있는데 나는 그냥 하나의 트리로 놓고 문제를 풀었으니

틀릴수밖에...


조금은 불친절한 문제인것 같다, 이런 경우도 있다는걸 알려줘도 무방 할 것 같은데


뭐 이런것도 실력이니까;

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

2156  (0) 2015.02.28
10159  (0) 2015.02.28
9489  (0) 2015.02.26
2517  (0) 2015.02.26
2568  (0) 2015.02.25
2109  (0) 2015.02.22

2517

알고리즘/acmicpc 2015. 2. 26. 21:54 Posted by 아는 개발자

처음에 바로 BIT로 풀어야지 했다가 

정수의 범위가 1000000000까지인걸 단순히 BIT로 접근해선 안되겠음을 깨달았다.


이전까지 탐색한 정보들을 Heap에 넣어둘까 하다가 최악의 경우가 O(n*n)이라 별 소용이 없음을 생각하고 다른 방법을 강구...


그러다가 어차피 선수의 수가 500000이하니까 1~1000000000을 1~500000로 좁히는 방법을 생각했다.


방법은 1~1000000000의 data들을 정렬해서 그 data의 index값을 BIT에 쓰는 방법이다.

해당 index 값을 찾는 과정은 이진 탐색이니까 O(log(500000))으로 확 준다.


그러면 BIT에 index값까지의 합을 확인하고 현재까지 탐색한 선수의 수를 빼주고

그 index에 1만큼 update한다. 이 과정은 O(logN)


시간복잡도를 O(NlogN)으로 줄일 수 있었다.



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

10159  (0) 2015.02.28
9489  (0) 2015.02.26
2517  (0) 2015.02.26
2568  (0) 2015.02.25
2109  (0) 2015.02.22
1914  (0) 2015.02.22

2568

알고리즘/acmicpc 2015. 2. 25. 13:33 Posted by 아는 개발자

초등부의 전깃줄 문제에서 한발 나아간 문제.

기본적으로 LIS를 이용해서 풀 수 있는 것은 똑같지만 Input의 개수가 1000배이상 증가해서

O(N*N) 기본탐색 알고리즘을 사용하면 시간초과가 날게 틀림없으므로

좀 더 효율적인 자료구조를 활용해 속도를 높일 필요가 있었다.


나는 priority queue를 이용해서 풀었는데

priority queue는 이전 까지 탐색했던 line중에서 LIS값이 높은 순위로 저장되어있다.

priority queue는 pair<int, int>로 이루어져 있는데 pq가 pair.first를 통해서 정렬한다는 점을 알면 구현하기 편리하다


d값, value값, idx값 총 세가지 값이 필요한데 나는 pair.second로 idx값을 넣어서 value값은 넣지 않고 idx값을 통해서 참조 할 수 있게 만들었다.




728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9489  (0) 2015.02.26
2517  (0) 2015.02.26
2568  (0) 2015.02.25
2109  (0) 2015.02.22
1914  (0) 2015.02.22
9463  (0) 2015.02.21

트립(Treap)

알고리즘/자료구조 2015. 2. 25. 11:19 Posted by 아는 개발자

이름에서도 예측 할 수 있듯이 트립(Treap)은 Tree + Heap인 자료구조이다.


기존 이진 트리는 어떻게 내가 삽입(insert)하느냐에 따라서 트리의 높이가 O(N)이 될 수 있고 O(logN)이 될수도 있는 문제점이 있다. 트리구조의 기본적인 목표는 최대한 높이를 낮추어 탐색의 시간을 빠르게 하는 것이 목적인데 높이가 O(N)되면 선형 구조와 다를바가 없어진다. 즉 균형의 문제가 발생한다.


균형의 문제를 해결하기위한 자료구조로는 AVL Tree와 Red Black Tree가 있는데 이것들은 구현하기가 어렵다. 그래서 간단히 Heap의 성질을 이용해서 구현한것이 Treap이다. 방법은 다음과 같다.


1. 삽입할 노드들에게 난수값으로 우선순위를 부여한다.

2. 노드가 어떤 subtree의 루트가 될지의 기준은 우선순위이다.

3. 노드가 어떤 node의 우선순위보다 작으면 자식이 된다.

4. 이때 왼쪽 자식이 될지 오른쪽 자식이 될지는 부모의 value값과 자식의 value값을 비교해서 이루어진다.


value값으로 tree의 높이를 결정하는 것이 아니라 특정 난수들로 tree의 높이를 결정한다. 물론 난수값이 내림차순으로 결정되면 Treap자료구조도 O(N)이 될수도 있다. 하지만 위 확률은 매우 적어서 신경쓰지 않아도 된다. 


삽입하고 삭제하고 합치는게 좀 까다로울 수 있다.


728x90

'알고리즘 > 자료구조' 카테고리의 다른 글

오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24
KMP 알고리즘  (0) 2015.02.24
BIT(Binary Indexed Tree)  (0) 2015.02.21