본문 바로가기

알고리즘

(368)
[Python] 30510번 토마에 함수 https://www.acmicpc.net/problem/30510 30510번: 토마에 함수 첫째 줄에 두 양의 정수 $P$, $Q$가 공백으로 구분되어 주어진다. $(1\le P\le Q\le 100\, 000)$ www.acmicpc.net 24/03/07 이전에 SASA컵을 검수한 적이 있었다. 사실 그때 너무 바빴어서 풀이만 생각하고 정해 코드를 짜지 않았었는데, 이 문제의 해설을 작성해보고자 한다. 문제 접근 방식: 문제를 요약하면 다음과 같다. $x$가 무리수면 $f(x) = 0$ $x$가 $0$이면 $f(x) = 1$ 그 외 $x = \frac{p}{q} ; \mathrm{gcd}(p, q) = 1$이면 $f(x) = \frac{1}{q}$ 임의의 유리수 $\frac{P}{Q}$가 주어질 ..
[Python] 31540번 도박 문제 전문 상담은 국번없이 1336 https://www.acmicpc.net/problem/31540 31540번: 도박 문제 전문 상담은 국번없이 1336 첫 번째 줄에 대회 참가자의 수 $n$, 배당의 총합을 결정할 정수 상수 $m$, $t$가 공백으로 구분되어 주어진다. $(1\le n, m, t\le 10^6)$ 두 번째 줄에 베팅 결과 각 참가자에게 걸린 금액을 나타내는 $n$개 www.acmicpc.net 24/03/10 내가 검수했던 MatKor컵의 한 문제로, 전형적인 수학 문제이다. 두 가지 방법으로 풀 수 있는 좋은 문제이다. 여기서는 의도했던 정해를 중점으로 서브태스크 순으로 따라가며 설명해보고자 한다. 문제 접근 방식: 문제를 요약하면, 준혁이는 도박을 운영하는 도박 운영자고, 사람들에게 받은 돈이 총 $S$원이다...
[Python] 10166번 관중석 https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 24/02/13 실버 1치고는 많은 고민을 하게 한 문제이다. 각 코드 별로 어떠한 흐름을 가지고 생각했는지 적어보고자 한다. 문제 접근 방식: 처음으로 생각한 것은, 보이는 관중석이 어떤 일정한 규칙을 가지고 있어서, 그 규칙이 수식으로 표현 될 것이라는 생각이 들었다. 그 이후에 바로 보인 사실은, $i < j$일때, 반지름 $i$가 반지름 $j$인 원을 가린다면, 그 가리는 관중석의 개수는 ..
[Python] 13705번 Ax+Bsin(x)=C https://www.acmicpc.net/problem/13705 13705번: Ax+Bsin(x)=C 첫째 줄에 정수 A, B, C가 주어진다. (0 < B ≤ A ≤ 100,000, 0 < C ≤ 100,000) www.acmicpc.net 24/02/14 아주 유명한 문제다. 사용하는 알고리즘은 매우 단순하다. 그냥 이분 탐색에 약간의 수학적 지식. 이 문제가 그렇게 악명이 높은 이유는 매우 높은 정밀도를 요구하기 때문이다. 파이썬을 사용하면 쉽게 구현할 수 있다. 문제 접근 방식: 함수 $f(x) = Ax + B\mathrm{sin}(x) - C$이 $B \leq A$조건 하에서 단조 증가함수임을 보이기만 한다면, 일단 이분 탐색을 사용할 수 있는 조건이 성립된다. 함수 $f$를 미분한 결과는 ..
[Python] 2608번 로마 숫자 https://www.acmicpc.net/problem/2608 2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net 24/02/27 단순한 구현 + 문자열 문제이다. 사소한 실수로 두 번 정도 틀렸습니다를 받았다. 문제 접근 방식: 문제에서 요구하고자 하는 것은 로마 숫자로 주어진 두 수를 더하고, 그 결과를 하나는 아라비아 숫자로, 하나는 로마 숫자로 출력하는 것이다. 문제를 읽던 도중 생각난 방법은 아라비아 숫자와 로마 숫자 사이의 일대일 대응 표를 만들어서 각 자리 숫자 별로 매칭을 시키면 충분할 것이라는 방법이었다. 마침 문제 제한을 보았고, 두 수가 모..
[Python] 11037번 중복 없는 수 https://www.acmicpc.net/problem/11037 11037번: 중복 없는 수 중복 없는 수는 각 숫자(1, 2, 3, ..., 9)가 최대 한 번씩 등장하고, 숫자 0은 포함하지 않는 수이다. 따라서 중복 없는 수는 최대 9자리로 이루어질 수 있다. 중복 없는 수의 예시로는 9, 32, 489, 98761, 98 www.acmicpc.net 24/02/20 원래는 파이썬으로 통과해서는 안되는 문제인데, 파이썬이 점점 빨라짐에 따라 쉽게 통과할 수 있게 된 문제 같다. 정확한 시간 복잡도는 계산해보지 못했다. 문제 접근 방식: 문제에서 요구하고자 하는 것은 주어지는 수보다 크면서 가장 작은 중복 없는 수를 구하는 것이다. 중복 없는 수란, 각 숫자가 최대 한 번씩만 등장하고, 숫자 $0..
[Python] 12445번 バクテリアの増殖 (Small) https://www.acmicpc.net/problem/12445 12445번: バクテリアの増殖 (Small) 微生物の研究者であるパスカルは、特殊な増殖の傾向を示すバクテリアを発見した。どうやらそのバクテリアは、ある時点で x 個存在したとすると、理想的な環境下では1時間後に xx 個に増 www.acmicpc.net 24/02/09 아주 아주 간단한 문제로, 파이썬으로 해결하기에 아주 적절한 문제다. 문제 접근 방식: 이 문제는 Small버전이 존재하고 Large버전이 존재한다. Large버전의 경우, Power tower류의 문제로, 정수론을 배워야 풀 수 있는 문제다. https://www.acmicpc.net/problem/13970 13970번: Power towers In this example, as M =..
[Python] 27114번 조교의 맹연습 https://www.acmicpc.net/problem/27114 27114번: 조교의 맹연습 첫 번째 줄에 각각 좌로 돌아, 우로 돌아, 뒤로 돌아에 들어가는 에너지를 나타내는 세 정수 $A, B, C$와 사용하고자 하는 총 에너지양을 나타내는 정수 $K$가 공백으로 구분되어 주어진다. $(1\leq A,B www.acmicpc.net 24/02/26 간단한 DP문제로, 처음엔 BFS로 잘못 접근했던 문제이다. DP테이블 정의와 점화식 유도는 빠르게 할 수 있었지만, 자잘한 실수가 있어서 아쉬웠다. 문제 접근 방식: $K$만큼의 에너지를 소모하여 처음 바라보고 있던 방향으로 제식 연습을 끝마쳤을 때 제식 수행 횟수의 최솟값을 구하는문제이다. 처음에는 BFS로 접근하고, 과도한 루프 방지를 위해 일정 ..