본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 12850번 본대 산책2 https://www.acmicpc.net/problem/12850 23/03/21  예전에 이 문제에 대한 풀이 글을 작성한 것 같았는데, 지금 검색해보니 작성하지 않아서 오랜만에 작성하려고 한다. 그래프를 인접 행렬로 나타낼 수 있는지에 대한 지식과, 그 행렬을 거듭제곱하면 경로의 개수가 나온다는 지식을 요구하는 문제다.  문제 접근 방식:  본대 산책1이 있고 본대 산책2가 있는데, 둘은 제한만 다른 문제다. 본대 산책2는 본대 산책1에 분할 정복을 이용한 거듭제곱 태그가 들어가서 난이도가 더 뛰어버렸다. (사실 그 정도로 어려운가 싶지만, 그렇다고 하자.) 문제에서 주어진 그래프를 인접 행렬의 형태로 바꿔보자.matrix = [[0, 1, 1, 0, 0, 0, 0, 0], [1, ..
[Python] 2600번 구슬게임 https://www.acmicpc.net/problem/2600 24/05/13  단순한 님 게임의 변형으로 해결할 수 있는 문제다. 스프라그-그런디 정리를 배우면서 님버에 대한 개념을 익혔다면 쉽게 해결할 수 있는 문제다. 그 외에도 이차원 DP로도 해결할 수 있다. 문제 접근 방식:  나는 이 문제를 스프라그-그런디 정리를 공부하며 얻은 지식인 님버를 활용하여 문제를 해결했다. 결국 이 문제는 님 게임의 변형이고, 처음 두 통에 들어 있는 구슬의 수가 최대 $500$개로 제한되어있기 때문에 충분히 빠른 시간 안에 님버를 구할 수 있다. 또한, 내 차례 때 할 수 있는 행동의 가지 수가 최대 $3$가지이기 때문에 각 숫자 별로 구하는 님버가 최대 $3$까지임을 확인할 수 있다. 현재 게임 판의 님버를..
[Python] 2118번 두 개의 탑 https://www.acmicpc.net/problem/2118 24/05/14  간단한 누적 합 + 두 포인터 연습문제이다. 문제 접근 방식:  두 지점을 $i$와 $j$라고 하고, 편의 상 $i \leq j$라고 가정하자. 원의 둘레를 $T$라고 한다면, 두 지점 사이의 거리는 다음과 같이 정의된다. $$\text{min}(D[j]-D[i] , T-D[j] + D[i])$$ 여기서 $D$는 두 지점의 위치를 나타낸다. 예제 입력을 통해 왜 투 포인터를 써야하는지에 대한 이야기를 해보자.예제 입력에 대한 그림을 그리면 다음과 같다.빨간 지점에서 시작하여 빨간 지점과 가장 멀리 떨어져 있는 곳을 반시계 방향 순으로 찾아보자.그림을 보면 확인할 수 있듯이, 빨간 지점과 가장 멀리 떨어진 지점을 찾을 때까..
[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. 두..

티스토리툴바