알고리즘 (368) 썸네일형 리스트형 [Python] 31529번 2024년에는 혼자가 아니길 https://www.acmicpc.net/problem/31529 24/03/09 맷코 컵의 검수진으로 검수를 했던 문제 중 하나이다. 단순한 기하학 문제이다. 문제 접근 방식: 원점에서 $A$까지 떨어진 거리를 $a$, 원점에서 $B$까지 떨어진 거리를 $b$, 마찬가지로, $c, d$가 있다고 하자. 그러면 $\overline{AC}^{2} + \overline{BD}^{2} = X = a^2 + b^2 + c^2 + d^2$으로 나타낼 수 있다. 마찬가지로, $Y = (a+b)^2 + (c+d)^2 = a^2 + b^2 + c^2 + d^2 + 2ab + 2cd$으로 표현할 수 있다. $M$과 $N$의 좌표는 $\frac{a-b}{2}$와 $\frac{c-d}{2}$이므로, $\overline.. [Python] 31531번 공들의 리듬게임 https://www.acmicpc.net/problem/31531 24/03/10 풀이 아이디어가 제법 알려져 있는 문제로, 이전에 비슷한 문제를 해결했다면 쉽게 해결 할 수 있는 애드혹 문제다. 문제 접근 방식: 이 문제의 아이디어는 아래 문제에서 얻을 수 있다.https://www.acmicpc.net/problem/4307또는 아래 문제에서도 얻을 수 있다.2023.09.02 - [알고리즘/백준 문제 풀이] - [Python] 13249번 공의 충돌 [Python] 13249번 공의 충돌https://www.acmicpc.net/problem/13249 13249번: 공의 충돌 무게가 모두 같고, 크기가 0인 공 N개가 일직선 위에 놓여져 있다. 오른쪽으로 굴러가는 공과 왼쪽으로 굴러가는 공.. [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$으로 주어져 있습니다... 이전 1 ··· 7 8 9 10 11 12 13 ··· 46 다음
