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

접미사배열

알고리즘/자료구조 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)이 걸린다.


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


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

KMP 알고리즘

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

예전에 KMP는 왜 KMP인가라는 문제를 보고 KMP이거 뭐지 장난하는건가 싶었는데;

문자열에 관한 알고리즘인걸 책을 보고 깨달았다.. 이렇게 심오하고 환상적인 알고리즘이 있었다니 ㄷㄷ


KMP알고리즘은 어떤 문자에서 특정 문자열이 존재하는지 확인하는 방법이다.

예를 들어 길이가 N인 문자열에서 M이라는 문자열이 있는지 없는지 확인하고 싶으면

N의 모든 위치에서 M의 시작문자와 비교해보는 방법이 있다. 이 방법은 O(MN)이 든다.


하지만 KMP알고리즘은 모두 비교하지 않고 접두사 접미사의 개념을 활용해서 푼다.


예를들어


abcabce -> 문자열 M

abcabcabcd -> 문자열 N


위의 M과 N을 비교했더니 abcabcabc까지는 같고 뒤에부터 달랐다.

그런데 다음 비교를 N의 두번째 문자열 부터 시작 하지 말고

abcabcabc의 접미사와 접두사가 같은 부분은 잘라서 하자는 것이다.

여기서 접두사 접미사가 같은 부분은 abc이다 따라서 N의 네번째 문자부터 탐색을 시작하면 효율적이다.


abcabcabcd

    abcabce

굵은a 부터 시작하라는것 왜냐면 앞에 있는 것들은 같은걸 아니까 따로 자료 구조를 만들어서 정리했으므로


문자열 N에 대하여 는 다음과 같은 자료 구조를 만들어야 한다


longestprefixsuffix[length];


length는 처음부터 length까지의 문자열 길이를 말하고

그 길이 까지 접미사와 접두사가 같은 부분의 최대 길이를 말한다.


구현은 다음과 같다.


#include<iostream>

#include<string>


using namespace std;



int p[1000];

int main()

{

string s;

cin>>s;


int begin=1, matched=0;


while(begin + matched < s.length())

{

if(s[begin + matched] == s[matched])

{

matched++;

p[begin + matched - 1] = matched;

}

else

{

if(matched == 0)

begin++;

else

{

begin += matched - p[matched-1];

matched = p[matched-1];

}

}

}


return 0;


}


접미사, 접두사 라는 개념을 사용하는건 이해가 가는데

이거를 깔끔하게 만드는 과정은 이해하기 어렵다.

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

2109

알고리즘/acmicpc 2015. 2. 22. 16:09 Posted by 아는 개발자

처음에 문제 이해못해가지고 왜 이런걸 틀리지 싶었는데 내가 틀렸다 ㅡㅡ

QnA에서 문제를 제대로 이해하고 다시 풀어서 맞았다.


이 문제의 핵심은 d 기간 내에는 어떤 날짜에 강연을 해도 상관 없다는거다


그래서 3 1 1 10 2 10 2 라는 인풋이 들어오면

정답으로 20을 출력해야한다.


어떤 강연을 할 지 말지 결정하는 과정은 다음과 같다.


기간내에 강연 할 수 있는 빈 시간이 있다면

강연을 하고


이미 강연이 다 차있다면 차있는 강연들 중에서 가장 돈을 조금 주는 강연과 비교 한 다음

하려고 하는 강연이 더 돈을 많이 주면 가장 돈을 조금 주는 강연과 바꾸면 된다.


생각 과정은 그리 어렵지 않은데 자료 구조를 어떤걸 쓸 것인지가 고민이었다.

최대 10000개의 강연이 있기 때문에 생각하기 쉬운 자료구조(n*n)을 사용하면 

시간초과가 뜬다.


1. 그래서 나는 먼저 강연들을 기간으로 오름차순 정렬한 다음


2. 그 기간내에 강연이 몇개 있는 지는 BIT를 이용해서 구했고(사실 이거는 안해도 되는디)


3. 그 기간내의 강연 중 돈을 가장 조금 주는 강연은 priority queue를 통해서 구현했다.


오름차순으로 정렬했기 때문에 기본적으로 dp로 차근차근 증가시켜 나가면 된다.


#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>


using namespace std;


const int SUM_MAX = 100000001;

int size_tree[11111];


struct Node{

int d, p;

};


bool compare(Node a, Node b)

{

return a.d < b.d;

}


int read(int idx)

{

int sum = 0;

while(idx > 0)

{

sum += size_tree[idx];

idx -= idx&-idx;

}

return sum;

}


void update(int idx, int val)

{

while(idx <= 11111)

{

size_tree[idx] += val;

idx += idx&-idx;

}

}


Node coll[11111];

int d[11111];


int main()

{

int n, piv= 0;

scanf("%d", &n);


priority_queue<int> pq;


for(int i = 1; i <= n; i++)

{

scanf("%d %d", &coll[i].p, &coll[i].d);

}

sort(coll+1, coll+n+1, compare);


for(int i=1;i<=n;i++)

{

if(read(coll[i].d) < coll[i].d)

{

piv++;

update(piv, 1);

d[piv] += coll[i].p + d[piv-1];

pq.push(-coll[i].p);

}

else

{

if(abs(pq.top()) < coll[i].p)

{

d[piv] -= abs(pq.top());

d[piv] += coll[i].p;

pq.pop();

pq.push(-coll[i].p);

}

}

}


printf("%d\n", d[piv]);


return 0;

}


728x90

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

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
2776  (0) 2015.02.21