본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 30961번 최솟값, 최댓값 https://www.acmicpc.net/problem/30961 30961번: 최솟값, 최댓값 수열의 힘은 수열의 최솟값과 최댓값을 곱한 값이다. 길이가 $N$인 수열 $A$가 주어질 때, 이 수열에서 길이가 $1$ 이상인 모든 부분수열 각각의 힘을 구하여 모두 XOR한 값을 구하여라. www.acmicpc.net 24/03/18 XOR의 성질을 이용한 간단한 수학 문제다. 문제 접근 방식: 문제의 요구 사항은 수열 $A$가 주어졌을 때, $A$의 부분 수열 $B$의 최댓값과 최솟값을 곱한 값을 $C$라고 하면, $A$의 모든 부분 수열에서 나오는 $C$의 값을 모두 XOR한 값을 구하는 것이다. 즉, 다음과 같은 수식으로 나타낼 수 있다. $$\bigoplus_{B \subset A} ( \max ..
[Python] 28692번 선형 회귀는 너무 쉬워 2 https://www.acmicpc.net/problem/28692 28692번: 선형 회귀는 너무 쉬워 2 주어진 점이 $(7, 32)$, $(18, 67)$, $(40, 137)$이므로, $n = 3$, $S_x = 65$, $S_y = 236$, $S_{xx} = 1\,973$, $S_{xy} = 6\,910$이다. 즉, $a_2 = \frac{3 \times 6\,910 - 65 \times 236}{3\times 1\,973 - {65}^2} = \frac{5\,390}{1\,694}=\frac{35}{11} www.acmicpc.net 23/08/21 선형 회귀는 너무 쉬워 시리즈의 두 번째 문제이다. 얼핏 보면 어려운 문제일 것 같지만, 문제만 잘 읽으면 쉽게 해결할 수 있다. 문제 접근 방..
[Python] 27295번 선형 회귀는 너무 쉬워 1 https://www.acmicpc.net/problem/27295 27295번: 선형 회귀는 너무 쉬워 1 유림이는 선형 회귀에 자신이 있다. 그래서 MatKor 동아리에서 선형 회귀에 관한 수업을 할 때 집중을 하지 않았다. 당시 강사였던 동우는 이를 못마땅하게 여겨 유림이에게 더 어려운 문제를 내 www.acmicpc.net 23/01/30 선형 회귀는 너무 쉬워 시리즈의 첫 번째 문제이다. 간단한 선형 방정식을 풀면 되는 문제다. 문제 접근 방식: 문제의 요구 사항은 $b$가 주어지고 각 데이터들이 주어질 때, $\sum_{i=1}^{n} (ax_i + b - y_i)$가 $0$에 가장 가깝도록 하는 $a$의 값을 구하는 것이다. 가능한 $a$의 값이 여러 개라면 EZPZ를 출력하면 된다. 식을 ..
[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 단순한 구현 + 문자열 문제이다. 사소한 실수로 두 번 정도 틀렸습니다를 받았다. 문제 접근 방식: 문제에서 요구하고자 하는 것은 로마 숫자로 주어진 두 수를 더하고, 그 결과를 하나는 아라비아 숫자로, 하나는 로마 숫자로 출력하는 것이다. 문제를 읽던 도중 생각난 방법은 아라비아 숫자와 로마 숫자 사이의 일대일 대응 표를 만들어서 각 자리 숫자 별로 매칭을 시키면 충분할 것이라는 방법이었다. 마침 문제 제한을 보았고, 두 수가 모..

티스토리툴바