2599

알고리즘/acmicpc 2015.02.15 23:35 Posted by 아는 개발자

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

'알고리즘 > 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.02.15 23:27 Posted by 아는 개발자

공약수문제...

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

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

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

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


6, 180이 주어져있으면

180/6 = 30이 남는다

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

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

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

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


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

'알고리즘 > 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.02.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 공부했는데 이렇게 쓰일줄일야... 기본 개념이 중요한걸 다시 한 번 느꼈다..


'알고리즘 > 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.02.14 13:48 Posted by 아는 개발자

사다리 문제는 간단하다

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

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

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

서로 비교하면 된다.

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

xxxx를 출력하면된다.


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

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

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

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

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

'알고리즘 > 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.02.14 12:42 Posted by 아는 개발자

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

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


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

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

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


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

'알고리즘 > 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