글 (385) 썸네일형 리스트형 [Python] 1160번 Random Number Generator https://www.acmicpc.net/problem/1160 24/04/15 분할 정복을 이용한 거듭제곱 문제이다. 식 정리하는 과정이 조금 까다롭다. 문제 접근 방식: 점화식이 $a_{n+1} = \alpha a_n + \beta$의 꼴이기 때문에, 이를 잘 정리하면 일반항을 얻어낼 수 있다. 식을 다음과 같이 정리해보자. $$\begin{align} X_{n+1} &= aX_n + c \\ X_{n+1} - \alpha &= a(X_n - \alpha) \end{align} $$이때, $X_n - \alpha = Y_n$으로 치환해보자.$$\begin{align} Y_{n+1} &= aY_n \\ Y_n &= a^{n-1} Y_1 \\ X_n - \alpha &= a^{n-1}(X_1 - \.. [Python] 30912번 위잉위잉 https://www.acmicpc.net/problem/30912 24/05/11 각도 정렬을 "잘" 구현해야 되는 문제이다. 문제 접근 방식: 처음으로 접근했던 방식은 파이썬 math모듈의 atan2함수를 이용한 정렬이다. 파이썬 공식 도큐먼트에 나와있는 atan2함수의 설명은 다음과 같다.math.atan2(y, x)Return atan(y / x), in radians. The result is between -pi and pi. The vector in the plane from the origin to point (x, y) makes this angle with the positive X axis. The point of atan2() is that the signs of both inp.. [Python] 11668번 파이프 청소 https://www.acmicpc.net/problem/11668 24/05/12 기하학 + 그래프 이론 관련 문제이다. 좋은 문제인 것 같아서 풀이를 남겨보려고 한다. 문제 접근 방식: 문제에서 요구하고 있는 바를 정리해보자. 1. 파이프는 수원지와 도시를 잇는다.2. 두 파이프는 서로 교차할 수 있으며, 한 교차점에는 세 파이프가 동시에 교차하지 않는다.3. 교차점에는 이물질이 끼는데, 한 파이프에 로봇을 넣으면 그 파이프의 교차점을 모두 청소해 줌.4. 로봇이 충돌하는 일을 방지하기 위해 교차점에는 오직 하나의 파이프에만 로봇이 있어야 함.5. 어떤 파이프의 부분 집합을 잡아서 동시에 로봇을 투입했을 때, 두 로봇이 충돌하는 일이 없으면서 모든 교차점을 청소할 수 있는지를 판단해야 함.6. 두.. [Python] 20302번 민트 초코 https://www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 24/02/13 자잘한 실수를 많이 해 애를 많이 먹었던 문제입니다. 제가 잘못 접근했던 순으로 문제를 설명하고자 합니다. 문제 접근 방식: 문제에서 주어지는 정보는 간단합니다. 주어진 수식을 순서대로 계산하고, 그 결과가 정수인지 유리수인지 판별하는 것입니다. 파이썬을 사용하고 있다면 가장 흔하게 저지를 수 있는 실수는, 너무 간단한 풀이를 떠올려 구현하는 것입니다. 1. 파이썬에는 eval()이라는 함수가 존재해서, 주어진 수식의 값을 계산해줍니다. 이를 사용하.. [Python] 5069번 미로에 갇힌 상근 https://www.acmicpc.net/problem/5069 5069번: 미로에 갇힌 상근 상근이는 오른쪽 그림과 같은 미로에 갇혀있다. 미로는 육각형 모양의 방이 계속해서 붙어있는 모양이고, 이러한 방은 무수히 많이 있다. 또, 인접한 방은 문으로 연결되어 있어서, 한 방에서 다 www.acmicpc.net 24/02/01 DP문제로, 골드 4보다는 훨씬 어렵다고 느껴졌던 문제입니다. 문제 접근 방식: 처음에 접근했던 방식은, 초기 몇 개의 항을 문제에서 주어진 그대로 브루트포스+백트래킹을 사용하여 구한 뒤, OEIS를 이용해 답을 구한 방식이었습니다. 이 문제에 대한 OEIS링크는 아래에 있습니다. https://oeis.org/A002898 A002898 - OEIS A002898 Number.. [Python] 31532번 선형 회귀는 너무 쉬워 3 https://www.acmicpc.net/problem/31532 31532번: 선형 회귀는 너무 쉬워 3 첫 번째 줄에 $f_3(a)$의 값이 $0$에 가장 가깝게 하는 $a$, 즉, $a_3$을 출력한다. 답이 여러 가지라면 그중 아무거나 하나 출력한다. 가능한 정답 중 최소 하나 이상과의 절대오차 또는 상대오차가 $10 www.acmicpc.net 24/03/12 지난 겨울 MatKor Cup에 나왔던 문제로, 단순한 수치해석 문제입니다. 선형 회귀는 너무 쉬워 시리즈의 3번째 문제에 해당됩니다. 서브태스크 별로 문제 해설을 해보겠습니다. 문제 접근 방식: 서브태스크 1 ($b = 0;y_i = 0$) 모든 데이터(점)들의 $y$값 들이 $0$이고, 직선의 $y$절편이 $0$으로 주어져 있습니다... [Python] 31478번 포니 양은 놀고 싶어! https://www.acmicpc.net/problem/31478 31478번: 포니 양은 놀고 싶어! 첫 번째 줄에 정수 $A$, $B$, $C$가 주어진다. ($1\leq A < 7$, $1\leq B, C \leq 10^{9}$, $B^C$는 $A$의 배수) 두 번째 줄에 정수 $K$와 $L$이 주어진다. ($0\leq K,L < 7$) www.acmicpc.net 24/04/15 간단한 정수론 문제입니다. 분할 정복을 이용한 거듭제곱에 관한 지식과, 페르마의 소정리에 관한 지식이 있어야 해결할 수 있습니다. 문제 접근 방식: 결국 $A^{B^C}$와 $B^C / A$를 빨리 구하는 문제로 귀결됩니다. 후자는 빠르게 구할 수 있습니다. 결국 $7$일이라는 범위 안에서만 따지는 것이기 때문에 $7$.. [Python] 13987번 Six Sides https://www.acmicpc.net/problem/13987 13987번: Six Sides Print, on a single line, a floating-point value representing the probability that the first player wins, rounded and displayed to exactly five decimal places. The value should be printed with one digit before the decimal point and five digits after the dec www.acmicpc.net 24/04/06 간단한 확률론 + 사칙 연산 문제입니다. 저의 경우는 무한 등비 급수를 활용하여 해결했습니다. 문제 접근 방.. 이전 1 ··· 8 9 10 11 12 13 14 ··· 49 다음
