Search

'분류 전체보기'에 해당되는 글 290건

  1. 2015.02.25 2568
  2. 2015.02.25 트립(Treap)
  3. 2015.02.24 접미사배열
  4. 2015.02.24 KMP 알고리즘
  5. 2015.02.22 2109
  6. 2015.02.22 1914
  7. 2015.02.21 9463
  8. 2015.02.21 BIT(Binary Indexed Tree)
  9. 2015.02.21 2776
  10. 2015.02.21 ASYMTLING
  11. 2015.02.21 NUMB3RS
  12. 2015.02.17 2631
  13. 2015.02.17 1958
  14. 2015.02.17 9252
  15. 2015.02.17 9251
  16. 2015.02.15 2599
  17. 2015.02.15 2436
  18. 2015.02.14 2533
  19. 2015.02.14 2469
  20. 2015.02.14 2467

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

1914

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

옛날에 못풀었던걸 풀면 기분이 상쾌한데 이번꺼는 뭔가 찜찜하다... 왜 예전에는 못풀었지?


내 예전 코드들은 스택을 통해서 위치를 찾아가는 방법이었다.

재귀함수를 쓴 현재 코드 보다는 훨씬 속도가 빠를 것 같은데

시간초과가 난 원인은 역시 printf와 cout의 차이인듯 하다..


또 2^100을 해결하는 문제가 있었는데

이거는 long long 두개를 써서 해결할수 있었다.

728x90

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

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
2631  (0) 2015.02.17

9463

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

자력으로 해결하지 못했다. 다른사람이 푼 해설지 보고 어찌어찌 풀었는데

음... 시간 문제는 BIT를 이용해서 해결하는 거로 하고 여기서 명심해야할 거는

간선의 개수를 구하는 방법인데... 놀라웠다.


지금까지 나는 기를 쓰고 어케 풀어볼려고 생각했는데

간단히 현재까지의 간선의 개수 - 연결된 간선의 위치 까지의 간선수로 한번에 해결


음 그니까


read(N) - read(v[i].second)라는 코드로 한번에 해결했다.


왜 나는 이런게 떠오르지 않을까


지금 생각해보면 정말 간단한 원리인데 원래 N*N에 얽매여서 자력으로 해결하지 못하고ㅠ


또 신기한거는 시간차인데


출력형식이 시간에 영향을 많이 준다.

그런데 int보다는 long long이 출력할 때 빠르다.


printf("%d") 로 출력하면 시간초과가 뜨는데

printf("%lld")로 출력하면 시간 내에 들어온다.

출력 형식이 중요하긴 하나 보다. 다른 사람들도 모두 이렇게 출력하고 있다.

728x90

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

2109  (0) 2015.02.22
1914  (0) 2015.02.22
9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17

BIT(Binary Indexed Tree)

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

어려운거 많이 가르치기로 소문난 양교수님께서 왜 BIT를 설명 안해주셨을까

이렇게 감탄스러운 자료구조가 있는 줄 몰랐다.

RB Tree, AVL, 24 Tree이런거는 구현이 어려운데

이거는 구현도 어렵지 않고 편리하다


간단히 소개를 하면

기본적으로 어떤 data를 추가 할 때 O(1) 

그리고 그 data의 총 합을 구할 때는 O(n)이 걸린다.


하지만 BIT는 추가 할때도 O(logn) 총 합을 구할 떄도 O(logn) 시간이 걸리는

신기한 자료구조이다.


http://183.106.113.109/30stair/bindexedtree/bindexedtree.php?pname=bindexedtree

개념 설명이 내가 너무너무 부족하니 여기 있는 글을 통해서 이해하길...


나는 이것을 어떻게 응용할 것인지를 생각해보면...

위 사이트에서도 이미 응용 했지만


부분 합을 구하는 자료 구조 뿐만 아니라

부분 최소 값을 구하는 자료 구조로도 이용 할 수 있지 않을까 한다.


1차원을 사용하면 원래 값들을 모두 잃어버리겠지만

만약 내가 최소값을 찾길 원한다면 모두 다 돌아다니지 않아도 O(logn)시간에 찾을 수 있으니

효율적이다. 


LIS에서도 이 방법을 적용 할 수 있다고 하니

응용할 수 있는 방법이 무궁무진한 자료구조이다.




#include<iostream>

using namespace std;


int tree[20];

#define MaxVal 16

int read(int idx)

{

int sum = 0;

while(idx > 0){

sum += tree[idx];

idx -= (idx & -idx);

}


return sum;

}


void update(int idx, int val)

{

while(idx <= MaxVal)

{

tree[idx] += val;

idx += (idx & -idx);

}

}


int main()

{

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

update(i, i);


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

cout<<tree[i]<<endl;

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

2776

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

암기왕 문제..

예상외로 쉽게 풀릴수 있는 문제인데 괜히 어렵게 풀었다.

속도도 내 알고리즘이 더 빠를 줄 알았는데 오히려 더 느렸고 메모리도 더 많이 잡아먹고..

모두 한꺼번에 모아서 sort함수 때리고 앞의꺼랑 뒤에꺼가 같으면 ok라 놓고 풀었는데

계속 오답이 나왔다..


오답의 원인을 찾으니까 내 알고리즘은 검사를 두 번 실시하면 안에있는 거로 간주하는 문제가 있었다.. 아 진짜 이런 찐따가 따로없다..


binary_search라는 stl이 있어서 빠르게 해결 할 수 있었다... 이런거는 빨리 알아야 하는데

아 그리고 왠만하면 cin, cout을 쓰지 말고 #include<cstdio>에서 printf, scanf를 사용하는 습관을 들여야 겠다. cin, cout이 5배나 더 느리다니... 이것도 cin, cout 썼으면 분명 시간초과 떴을꺼다 ㄷㄷ


이 글 거의 읽는 사람은 내가 무슨 말 하는지 모를거다. 나도 다시 읽으면 모르겠다.

728x90

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

1914  (0) 2015.02.22
9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17

ASYMTLING

알고리즘/algospot 2015. 2. 21. 12:31 Posted by 아는 개발자

내가 스스로 풀때는 n개를 채울 때 대칭인 경우와 비대칭인 경우로 나누어서

접근하려고 했는데 그렇게 풀 필요가 전혀 없었다.

책에서 양 끝에서부터 채워가는 방식을 읽고 정말 놀랬다 ㄷㄷㄷㄷ

이렇게 생각하면 정말 쉽게 풀리는 구나... 

재귀함수의 매력에 놀랬고 저자의 천재성에 감탄하고 나의 부족함을 다시한번 깨달았다 ㅠㅠ

양끝이 대칭이면 내부는 비대칭이어야 하고

양끝이 비대칭이면 내부는 대칭이어야 한다. 이 경우로 모든 경우의 수를 만들 수 있었다...

dp로 문제를 해결하는 두 가지 조건

- 모든 경우의 수를 포함해야 하며

- 중복되는 경우가 있어선 안된다

를 다시 한번 실감하는 순간이었다


728x90

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

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

NUMB3RS

알고리즘/algospot 2015. 2. 21. 12:15 Posted by 아는 개발자

동적 계획법을 이용하면 풀기 편하다.

d[마을수][지난날수]로 자료형을 잡고

if(connected[현위치][마을])

d[현위치][날짜] += d[마을][날짜-1]/deg[마을]로

구할 수 있다.

그런데 제출하면 왜 틀리다고 나오는지 모르겠다;

책에있는데로 그대로 따라하는데... 

알고스팟 뭔가 좀 이상하다.... 물론 나한테 문제가 있는거지만 ㅠ

728x90

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

카쿠로  (0) 2016.12.11
회전초밥  (0) 2016.08.01
블록게임  (0) 2016.08.01
조합게임  (0) 2016.07.25
ASYMTLING  (0) 2015.02.21
NUMB3RS  (0) 2015.02.21

2631

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

알고리즘 문제들은 서로 다른 문제 같아도 같은 개념을 사용하고 있음을 이해하면

문제풀기가 편하다.

줄세우기문제는 앞으로 옮기고 뒤로 옮기고 해서 어려워 보이지

사실은 증가하는 순열중 가장 긴 순열을 찾으라는 문제와 같다.

옮기는 횟수는 전체 배열의 크기에서 증가하는 순열중 가장 긴 순열의 개수를 뺀 것과 같다.

아.. 이렇게 빠르게 이해됫으면 얼마나 좋을까

728x90

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

9463  (0) 2015.02.21
2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17

1958

알고리즘/acmicpc 2015. 2. 17. 18:38 Posted by 아는 개발자

세개의 문자에 대해서 LCS를 찾는것

d[][][] 3차원배열을 만들고 점화식은 같다

사실 공간에 취약해서 왜 이렇게 답이되는지 증명하라면 좀 시간 걸릴것 같다

하지만 LCS 문제를 푸는데 착안해서 풀었다.

728x90

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

2776  (0) 2015.02.21
2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15

9252

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

LCS 살짝 변형한 문제다

문자열에대한 dp[][]배열을 만들어주면 된다.


728x90

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

2631  (0) 2015.02.17
1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15

9251

알고리즘/acmicpc 2015. 2. 17. 17:18 Posted by 아는 개발자

LCS문제

모두의 부부수열이 되는 수열중 가장긴것을 찾는문제

전형적인 dp문제인데 이때 d배열을 2차원으로 해야한다는 점이 중요

점화식만 잘 만들면 어렵지 않게 해결 할 수 있다.

현재 위치의 dp값을 지정해주려면


if(A[i] == B[i]) dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])

else dp[i][j] = max(dp[i][j-1], dp[i-1][j])


요렇게

728x90

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

1958  (0) 2015.02.17
9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14

2599

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

이런문제는 틀리면 안된다.

728x90

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

9252  (0) 2015.02.17
9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14

2436

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

공약수문제...

너무 소수를 구하는데 얽매여서 

에나로스의 체를 구해서 소수 만들고 하다보니 메모리 초과 뜨고 ㄷㄷㄷ

너무 소인수분해 하는데에 얽매여서 문제를 풀었던 것 같다.

좀 더 단순히 생각했어야 하는데 다른 사람이 푼 코드를 보니 아 이렇구나....


6, 180이 주어져있으면

180/6 = 30이 남는다

결국 30을 어떻게 쪼개느냐가 중요한건데

나는 30을 소인수 분해해서 2 3 5 를 어떻게 분해할 것인가로 문제를 풀었는데

다른사람은 아예 1~30까지 탐사해서 

각각의 경우에 최대 공약수가 원래의 값과 일치하는지를 보았다 ㄷㄷ


바보같이 쓸데 없느데 얽매이다보니 푸는게 너무 늦어졌다;;

728x90

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

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14

2533

알고리즘/acmicpc 2015. 2. 14. 17:05 Posted by 아는 개발자

다른 블로그 글을 읽고 도움을 받아서 풀긴했다.. 그런데..

dp로 문제를 푸는 전략 자체는 블로그 글과 나의 알고리즘은 같았는데

나는 왜 오답이고 블로그의 코드는 정답인건지.... 

아직 나의 코딩 스타일에 문제가 있는 것 같다. 재귀 함수를 이용해서 만드니까

지저분하고 속도도 오래 걸리고 블로그 글 처럼 최대한 간결하게 만들면 더 좋았을 텐데

dp문제는 기본적으로 배열을 이용해야 깔끔한 것 같다

int d[100001][2] 이런 식으로? 이중 배열이 속성을 의미하는 걸로 이해하자.


이 문제의 알고리즘은 다음과 같다

자신의 early adapter가 되는 경우는 자식이 early adapter인 경우나 자식이 early adapter가 아닌 경우 중 최소값이고

자신이 early adapter가 되지 않는 경우는 자식이 early adapter인 경우이다.


코드로 쓰면

d[v[now][i]][0] += d[now][1];

d[v[now][i]][1] += min(d[now][0], d[now][1]);

v[now][i]는 현재 위치에서 부모를 나타낸다.

(지금와서 다시생각해보니 부모만 찾아다니면 되는거였네;;)


블로그 코드에서 소름돋았던거는 degree를 이용해서 다음 큐에 들어갈 노드를 찾았던 거다

자료구조시간에 degree 공부했는데 이렇게 쓰일줄일야... 기본 개념이 중요한걸 다시 한 번 느꼈다..


728x90

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

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14

2469

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

사다리 문제는 간단하다

가로획이 있으면 둘의 위치가 바뀌는 성질만 이용하면 된다.

????가 나타나기 전까지는 ABCD에서 쭉 내려오고

그 이후로는 목표로 한 문자열을 가지고 아래에서 위로 올라간 후

서로 비교하면 된다.

현재 문자열과 목표 문자열의 위치 차이가 2 이상으로 나면 사다리로 만들 수 없으므로

xxxx를 출력하면된다.


문제만 생각하지 말고 사다리의 원리에 대해서 생각해보자

내가 어떻게 가로획을 긋더라도 사다리는 항상 일대일 대응을 이루는데

방금 위에서 설명한 사다리 가로획의 원리를 생각하면 이해하기 쉽다.

두 세로획의 자리를 바꾸는 것이기 때문에 내가 어떻게 자리를 바꾸더라도

1:1대응의 성질은 유지될 수 밖에 없다.

728x90

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

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14

2467

알고리즘/acmicpc 2015. 2. 14. 12:42 Posted by 아는 개발자

처음에는 binary search로 접근해서 푸려고했는데

런타임에러가 자꾸 난다... 이유는 모르겠다


그래서 음수 양수를 하나의 배열에 넣고 절대값으로 정렬한 다음

붙어있는 거끼리 음수 양수를 복원한 값으로 더해서

그 중 최소의 값을 구하는 방식으로 문제를 해결했다.


런타임 에러 찾느라 시간이 너무 오래걸렸다... 찾지도 못했으면서 ㅠ

728x90

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

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14