%2021. 12. 5. 23:18에 작성된 글입니다% 4357번: 이산 로그 소수 P(2 ≤ P < 231), 정수 B(2 ≤ B < P), 정수 N(1 ≤ N < P)가 주어졌을 때, 밑을 B, 나머지를 P로 하는 N의 이산 로그를 구하는 프로그램을 작성하시오. 즉, 다음과 같은 조건을 만족하는 정수 L을 찾으 www.acmicpc.net \(B^L\equiv N\mod P\)​ 를 만족시키는 \(L\)을 찾자. Babystep Giantstep으로도 알려진 Shanks’ Algorithm을 사용하면 된다. \(L=ax+b\)​ \(B^{ax+b}\equiv N\mod P\)​ \(B^{ax}\equiv B^{-b}N\mod P\)​ 페르마의 소정리에 따라 \(B^{-1}\equiv B^{P-2}\m..

%2021. 12. 3. 10:13에 작성된 글입니다% 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 분할 정복의 대표적인 예제로 많이 쓰이는 문제인 것 같던데 스위핑으로 푸는 게 아이디어 잡기도 구현도 훨씬 나은 듯. 약간의 데이터 처리와 이분 탐색 스위핑으로 그냥 풀린다. 분할 정복으로 풀면 P2-P1일지도 모르겠는데 스위핑으로 풀면 P2-P1 수준까지는 아닌듯... 내가 스위핑으로 풀었으니까 여기에는 스위핑 풀이 적음 ​ 전반적인 흐름: x 값이 작은 점부터 큰 점까지 ..

%2021. 12. 1. 22:47에 작성된 글입니다% 2595번: 배수 N은 30,000이하의 자연수이다. www.acmicpc.net 05KOI 지역본선 고등부 5번이랜다... 뻘짓을 좀 하긴 했는데 여튼 푸는 데만 거의 3시간을 갖다 박았으니 아직 KOI 지역 수준에도 못 미치는 것이다. 안타깝다. ​ 문제를 푸는 데 중요한 사실은, 조건을 만족하는 출력은 모두 숫자의 종류의 수(이하 cnt(x)로 씀)가 1 혹은 2라는 것이다. 증명은 모르겠다. ​ 1인 경우에는 당연히 1111, 33333333, 77777 따위의 수가 될 것이고, 2는 3333300000000, 44444440, 20220222220, 2882828, 5555555550 뭐 이런 식의 형태이다. ​ 1. 수에 10의 배수가 있..

%2021. 11. 30. 18:38에 작성된 글입니다% https://www.acmicpc.net/problem/17477 17477번: 수열과 쿼리 29 길이가 N인 수열 A1, A2, ..., AN이 주어지고, Bi = 0를 만족하는 길이가 N인 수열 B가 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = Ai + X를 적용한 www.acmicpc.net 한 9개월 전에 도전하다 때려치우고 오늘 다시 잡은 문제인데 결국 풀었다. 쿼리 꼴을 보아하니 '그들만의 웰노운' 세그비츠를 써야 할 것 같다. \(max, min, smax, smin, cmax, cmin\)과 함께 즐거운 세그트리를 짜자. 수열 B를 어떻게 할까 고민을 좀 했다...

%2021. 11. 20. 04:01에 작성된 글입니다% https://www.acmicpc.net/problem/12728 12728번: n제곱 계산 이 문제에서 숫자 (3 + √5)n 에 대한 소수점 앞에 마지막 세 자리를 찾아야합니다. 예를 들어, n = 5 일 때 (3 + √5)5 = 3935.73982 ... 이므로 답은 935입니다. n = 2 인 경우 (3 + √5)2 = 27.4164079 … 이므로, www.acmicpc.net 깡계산은 어림도 없다. 일단 \(3+\sqrt 5\)의 모양을 보아 하니 \(3-\sqrt 5\)도 같이 딸려나와야 뭐가 될 것 같아 보인다. 이차방정식 켤레근? 뭐 이런 느낌으로 탁 튀어나올 수 있기야 있겠다만서도 사실 처음부터 이걸 잡고 가야겠다는 생각이 바로..

%2021. 11. 11. 19:53에 작성된 글입니다% https://www.acmicpc.net/problem/1196 1196번: 잭 바우어 첫째 줄에 N과 K가 주어진다. N은 1018보다 작거나 같은 자연수이고, K는 N보다 작거나 같은 자연수이다. www.acmicpc.net \(H_n=\sum _{k=1}^n\frac{1}{k}\)​ \(f\left(n,\ k\right)=N\left(H_n-H_{n-k}\right)\)​ \(f(n, k)\)가 문제를 풀기 위해 코딩해야 하는 함수인데... naive하게 구현하면 시복도 \(O(N)\)이 나올 것이고 \(N\)의 범위는 \(10^{18}\) 이하 자연수니까 무리 없이 \(T\ L\ E\)를 받아낼 수 있으리라... 분명 근사가 가능할 것 같..

%2021. 11. 11. 16:04에 작성된 글입니다% https://www.acmicpc.net/problem/16282 16282번: Black Chain n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나는 무게가 정확히 1g 이다. 이 고리들을 이용하여 1g 부터 ng 까지 가능한 모든 무게를 생성하려고 한다. 이를 위해 고리를 일부 풀어 www.acmicpc.net 1. 고리를 \(n\)번 분리하면 \(w=1\)인 고리가 \(n\)개 생긴다. 2. \(w=1\)인 고리 뭉탱이로 만들 수 있는 최대 무게는 \(n\)이다. 3. 따라서 \(n+1\)짜리 고리가 있어야 그보다 더 무거운 무게를 구성할 수 있다. 4. \(w=n+1\)짜리 고리와 \(w=1\)인 고리를 모두 선택하면 무게..

%2021. 11. 10. 01:32에 작성된 글입니다% https://www.acmicpc.net/problem/10436 10436번: 무한 유리수 트리 무한 유리수 트리는 완전 이진 트리이며, 다음과 같이 정의된다. 루트는 1/1이다. p/q의 왼쪽 자식은 p/(p+q)이다. p/q의 오른쪽 자식은 (p+q)/q이다. 트리의 첫 세 층은 아래와 같이 구성된다. 이 무한 www.acmicpc.net 루트까지 올라갔다 내려와서 편하게 해결 보려는 생각은 꿈도 꾸지 말자. \(O(N)\)이라도 범위가 2147483647인지라... 주어진 값에서 바로 해결을 봐야 한다. 대단한 알고리즘은 없고 그냥 어디 종이 가지고 와서 트리 죽 적어본 뒤에 규칙을 찾으면 된다. 대부분의 경우에 간단하게 해결이 되고, 주..