구사과

페북에 굴러다니던건데http://tncks0121.tistory.com/ 블로그 주인장 분의 "강력한" 건의로 인해 블로그에도 올리게 되었다.덧붙이고 싶은 내용들을 조금 추가했다. 문제 후기 말고 대회 후기도 써야 하는데 안썼다.아마 안쓸듯. 나새끼.. boxes 제일 쉬워보였고 실제로도 쉬운 문제였습니다. 일단 O(nk) dp를 빠르게 코딩하고, 그리디 전략과 섞어서 O(n)에 해결했습니다. n이 천만으로 매우 큰데 나름 시사하는 바가 있다고 생각합니다. (소스 : http://oj.uz/submission/16536) scales 빠르게 머지소트 55점 풀이를 코딩하고 3번으로 넘어갔습니다. 71점 풀이는 처음반때 decision tree 배울때 생각했던 풀이로 애석하게도 바로 떠오르진 않았습니다 (..

nCr = n! / (n-r)! * r! 일 때, nCr mod prime을 빠르게 계산하는 방법에 대해서 얘기하려 한다. nCr 한 쿼리는 O(1)에 처리되어야 한다고 가정한다. (즉 전처리 한번 한 이후 nCr을 하나 계산하는데 O(1)) 1. O(n^2)위에 저 식을 그냥 구현만 해도 O(n) 인데..! 하지만 컴퓨터의 메모리는 한정되어 있으니 수를 그대로 들고 갈 수는 없고, mod p는 나눗셈을 하기 썩 좋은 상황은 아니다.그래서, nCr = (n-1)C(r-1) + (n-1)Cr 이라는 점화식(파스칼의 삼각형)을 사용해서 n^2에 계산하는 게 잘 알려져 있다. N^2 크기의 배열을 잡고 서서히 계산해 나가는 것이다. 이 방법은 나눗셈을 완전히 우회하는 방법으로써 사실 여러모로 제일 안정적인 방..

http://evenharder.tistory.com/