구사과

소인수 분해 문제는 합성수가 주어졌을 때 이를 소수들의 곱으로 표현하는 방법이다. 대한민국 초등학교 교과 과정에도 있을 정도로 잘 알려진 이 문제는 계산적인 관점에서 보았을 때 매우 어려운 문제 중 하나이다. 소인수 분해는 입력 크기에 대해 (숫자의 크기를 $N$ 이라고 하면, $\log N$ 에 대해) 다항 시간 복잡도 알고리즘이 존재하지 않는다. 이러한 "어려운" 성질 때문에 소인수 분해는 다양한 암호 알고리즘에 자주 사용된다. 소인수 분해는 간단한 $O(N^{1/2})$ 알고리즘이 존재하지만, 이보다 빠른 알고리즘을 찾는 것은 쉽지 않다. 일반적으로 가장 자주 사용되는 알고리즘은 Pollard-rho라는 알고리즘이다. 이 알고리즘은 대회에 사용될 수 있을 정도로 복잡하지 않고, 평균 $O(N^{1/..

추석에 BOJ에서 13문제 연습 셋을 만들고 풀기로 결심했다. 아직은 그렇다 ㅋㅋ! 문제 A. Bridge Park B. Kangaroos C. Hotline D. Justice for All E. Farm and Factory F. Longest Rivers G. Conquer The World H. Uncrossed Knight's Tour I. Hashigo Sama J. 빛의 왕과 거울의 미로 1 K. 빛의 왕과 거울의 미로 2 L. Celtic Knots M. Farm Village 9월 9일 K. 빛의 왕과 거울의 미로 2 비트 DP와 비슷한 식으로 한 줄에 대한 상태를 저장하는데, 단순한 불리언 변수로는 부족하니까 연결 상태에 대한 union-find를 메모이제이션하는 느낌으로 해결할 수 있..

IOI 2019 Day 2 대회가 종료되었다. 한국 학생들의 성적은 다음과 같다. 김세빈, 100 / 100 / 40 / 72.30 / 66 / 57, 435.30점, Day2 27등, 전체 18등, 금메달. 윤교준, 72 / 100 / 40 / 90.97 / 66 / 57, 425.97점, Day2 16등, 전체 22등, 금메달. 임유진, 72 / 100 / 40 / 61.41 / 66 / 57, 396.41점, Day2 40등, 전체 37등, 은메달. 이온조, 38 / 100 / 64 / 50.61 / 52 / 24, 328.61점, Day2 120등, 전체 83등, 동메달. 미국의 Benjamin Qi는 작년과 같이 이번에도 Day 2에서 조금 노는 (?) 모습을 보였고 1등 성적을 받지 못하였으나..