구사과

Motivation 계산기하에서 장애물을 포함하지 않는 가장 큰 도형을 찾는 것은 핵심적인 문제 중 하나이다. 다양한 거리계, 그리고 도형의 모양에 따라서 서로 다른 알고리즘들이 존재한다. 예를 들어서, 다음과 같은 문제들을 생각할 수 있다. A) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 원은 무엇인가? B) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 직사각형은 무엇인가? C) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으면서 $x, y$ 축에 평행한 가장 큰 정사각형은 무엇인가? D) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으면서 $x, y$ 축에 평행하고, 한 변이 $x$ 축에 포함되는 가장 큰 직사각형은 무엇인가? E) $..

소인수 분해 문제는 합성수가 주어졌을 때 이를 소수들의 곱으로 표현하는 방법이다. 대한민국 초등학교 교과 과정에도 있을 정도로 잘 알려진 이 문제는 계산적인 관점에서 보았을 때 매우 어려운 문제 중 하나이다. 소인수 분해는 입력 크기에 대해 (숫자의 크기를 $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를 메모이제이션하는 느낌으로 해결할 수 있..