알고리즘
-
2436알고리즘/acmicpc 2015. 2. 15. 23:27
공약수문제...너무 소수를 구하는데 얽매여서 에나로스의 체를 구해서 소수 만들고 하다보니 메모리 초과 뜨고 ㄷㄷㄷ너무 소인수분해 하는데에 얽매여서 문제를 풀었던 것 같다.좀 더 단순히 생각했어야 하는데 다른 사람이 푼 코드를 보니 아 이렇구나.... 6, 180이 주어져있으면180/6 = 30이 남는다결국 30을 어떻게 쪼개느냐가 중요한건데나는 30을 소인수 분해해서 2 3 5 를 어떻게 분해할 것인가로 문제를 풀었는데다른사람은 아예 1~30까지 탐사해서 각각의 경우에 최대 공약수가 원래의 값과 일치하는지를 보았다 ㄷㄷ 바보같이 쓸데 없느데 얽매이다보니 푸는게 너무 늦어졌다;;
-
2533알고리즘/acmicpc 2015. 2. 14. 17:05
다른 블로그 글을 읽고 도움을 받아서 풀긴했다.. 그런데..dp로 문제를 푸는 전략 자체는 블로그 글과 나의 알고리즘은 같았는데나는 왜 오답이고 블로그의 코드는 정답인건지.... 아직 나의 코딩 스타일에 문제가 있는 것 같다. 재귀 함수를 이용해서 만드니까지저분하고 속도도 오래 걸리고 블로그 글 처럼 최대한 간결하게 만들면 더 좋았을 텐데dp문제는 기본적으로 배열을 이용해야 깔끔한 것 같다int d[100001][2] 이런 식으로? 이중 배열이 속성을 의미하는 걸로 이해하자. 이 문제의 알고리즘은 다음과 같다자신의 early adapter가 되는 경우는 자식이 early adapter인 경우나 자식이 early adapter가 아닌 경우 중 최소값이고자신이 early adapter가 되지 않는 경우는 자..
-
2469알고리즘/acmicpc 2015. 2. 14. 13:48
사다리 문제는 간단하다가로획이 있으면 둘의 위치가 바뀌는 성질만 이용하면 된다.????가 나타나기 전까지는 ABCD에서 쭉 내려오고그 이후로는 목표로 한 문자열을 가지고 아래에서 위로 올라간 후서로 비교하면 된다.현재 문자열과 목표 문자열의 위치 차이가 2 이상으로 나면 사다리로 만들 수 없으므로xxxx를 출력하면된다. 문제만 생각하지 말고 사다리의 원리에 대해서 생각해보자내가 어떻게 가로획을 긋더라도 사다리는 항상 일대일 대응을 이루는데방금 위에서 설명한 사다리 가로획의 원리를 생각하면 이해하기 쉽다.두 세로획의 자리를 바꾸는 것이기 때문에 내가 어떻게 자리를 바꾸더라도1:1대응의 성질은 유지될 수 밖에 없다.