9489

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

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


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

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

틀릴수밖에...


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


뭐 이런것도 실력이니까;

'알고리즘 > 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)으로 줄일 수 있었다.



'알고리즘 > 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값을 통해서 참조 할 수 있게 만들었다.




'알고리즘 > 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)이 될수도 있다. 하지만 위 확률은 매우 적어서 신경쓰지 않아도 된다. 


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


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

오일러회로  (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

접미사배열

알고리즘/자료구조 2015. 2. 24. 21:23 Posted by 아는 개발자

문자열로 나오는 문제들은 접미사 배열을 이용해 어려운 문제들도 간단히 해결이 가능하다.

접미사 배열은 말 그대로 어떤 문자들의 접미사들을 모아놓은 묶음이다.

예를 들면 


Algorithm이면 접미사들로는

m, hm, thm, ithm, rithm, orithm, gorithm, lgorithm, Algorithm,이 있을 건데

이것들을 사전 순데로 정리해서


Algorithm

gorithm

hm

ithm

m

orithm

rithm

으로 나타낸 것이다.


어떤 점에서 유용하냐 그냥 정렬만 해두었으면서 라 할수도 있다


하지만 이게 사전순으로 정리되어 있다는 점을 주목할 필요가 있다.

우리가 어떤 문자열을 찾는다면

처음부터 모두 뒤져보는 원시적인 방법을 써야하지만 O(N*N)


위 처럼 정리해두면 O(N*logN)이 걸린다.


단순하면서도 나중에 써먹을 곳이 많은 자료구조이다.


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

오일러회로  (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