2.18 PS: 도전
www.acmicpc.net/problem/10098 10098번: 양분 섬을 합동인 두 다각형으로 나누는 선분이 존재하면, 선분의 두 끝점이 (x1, y1), (x2, y2)일 때 x1, y1, x2, y2를 나타내는 4개의 정수를 한 줄에 출력하면 된다. x1=x2이거나 y1=y2여야 한다. 선분은 다 www.acmicpc.net 백준 10098 양분.. 아이디어는 대강 생각해 놓았다.진짜 풀어보고 싶다. 대충 세 단계 정도면 풀 수 있다. (아마?) 1. 합동이면 넓이가 같으므로, 넓이를 이등분하는 x축, y축에 평행한 직선을 이분 탐색으로 빠르게 찾는다.이 "빠르게" 는 x축 기준, y축 기준으로 블록들을 나눈 뒤에 부분합 배열을 만들어서 할 수 있다. 2. 교점을 구해서 새로운 다각형 두 개를 ..
유클리드 호제법 알고리즘의 시간복잡도 예측하기
UPD: 자기 전에 생각해보니, 유클리드 호제법은 끝나기 직전을 제외하고 무조건 2 이상의 수로 나눌 수밖에 없어서 log의 밑이 2보다는 크다. 따라서 아래 글은 전부 헛짓이다.. 오늘 학원에서 공부를 하다가 굉장히 재밌는 논의를 발견했다. 그걸 이용해서 유클리드 호제법 연산 횟수의 상한을 알아내 보았다. 0. 유클리드 호제법 알고리즘 & 왜 이걸 증명하는가 유클리드 호제법은 다음 사실에 기반한다: $a, b$가 $a\geq b$를 만족하는 정수이고, $a=bq+r$이 성립할 때, $gcd(a, b) = gcd(b, r)$이다. 그런데, $gcd(a, 0)=a$임을 알고 있고, $r$은 $b$보다 작으므로 $min(a, b)$는 자연수의 감소수열이 되고, 언젠가 0이 되므로 저 방식을 계속 쓰다 보면 ..
