본문 바로가기

파이썬

 (320)
[Python] 32232번 엉엉이의 저주 탈출 https://www.acmicpc.net/problem/32232 24/09/13  맷코컵 검수 당시 검수했던 문제 중 하나이다. 문제 해석을 잘 한다면 막혔던 부분이 뚫리면서 쉽게 문제를 해결할 수 있을 것이다. 문제 접근 방식:  먼저 많은 관찰을 통해 다음과 같은 두 가지 사실을 발견해야 한다.(물론 오일러 지표를 통해 직접 유도하고 증명해도 충분하다.) 1. 엉엉이와 현철이가 지금까지 뽑은 서로 다른 점의 개수가 짝수 개라면 면이 홀수 개로 분할되고, 홀수 개라면 면이 짝수 개로 분할 된다. 2. 현철이는 자신이 이전에 뽑았던 점을 다시 뽑음으로써 홀짝성을 조정할 수 있다. 내가 이 문제에서 가장 어렵다고 느꼈던 점은 현철이와 엉엉이 모두 동일한 "확률"로 정수를 뽑는 상황, 즉, 게임에 랜덤이..
[Python] 32233번 토러스 게임 조작하기 https://www.acmicpc.net/problem/32233 24/09/12  오일러 지표 + 스프라그 그런디 + 가우스 소거법의 세 가지 태그가 잘 맞물리는 좋은 문제이다. 맷코컵 검수했을 때의 기억을 되살려서 꼼꼼하게 해설을 적어보고자 한다. 문제 접근 방식:  이 문제를 해결하기 위해서는 다음과 같은 세가지 지식을 알고 있어야 한다. 1. 오일러 지표에 대한 지식 2. 스프라그-그런디 정리에 대한 지식 3. 가우스 소거법, 특히, 2진법 위에서의 가우스 소거법에 대한 지식.  먼저, 하나의 토러스 또는 구 위에서 간선을 교차하지 않도록 잇는 게임을 하나의 님 게임으로 치환할 수 있다는 사실을 알아야 한다. 이는 스프라그-그런디 정리 관련 문제를 많이 푼 사람이라면 쉽게 파악할 수 있을 것이다..
[Python] 32213번 래빗 홀 https://www.acmicpc.net/problem/32213 24/09/05  간단한 스프라그-그런디 문제이다. 관찰의 아이디어가 좋아서 작성해본다. 문제 접근 방식:  두 사람이 할 수 있는 행동은 동일하다. 둘 중 하나이다. 1번 행동은 일반적인 님 게임이다. 근데 걸리는 점은 2번 행동이다. 2번 행동이 1번 행동에 영향을 줄 수 있을까, 곰곰히 생각해보면 아니다. 얼핏 생각하면 영향을 줄 수 있을 것 같지만 2번 행동이 전체 XOR의 합에 영향을 끼치지 못하므로 1번 행동과 독립이다. 결국 2번 행동은 홀짝성에 관한 게임을 개별적으로 하는 것과 동치이다. 즉, 님 게임과 홀짝 게임을 동시에 하고 있는 것과 동치이다. 처음에는 이러한 사실 때문에 님게임 XOR값과 홀짝성 모두 만족하면 후공 ..
[Python] 32230번 현대모비스 첨단 운전자 보조 시스템 https://www.acmicpc.net/problem/32230 24/09/10  내가 출제한 문제고, 에디토리얼이 나오려면 좀 걸릴 것 같아서 미리 내 문제만 먼저 해설을 작성해보고자 한다.  문제 접근 방식:  문제의 요구 사항은 안전 영역의 최솟값을 구하는 것이다. 서브태스크별로 할 수 있는 풀이를 적고자 한다. 서브태스크 1문제를 잘 읽고 $N \geq 3$일때 볼록 다각형이 만들어지고, 그렇지 않은 경우 볼록 다각형이 만들어지지 않음을 파악한다. 따라서, $0$을 출력하면 받을 수 있다. 서브태스크 2 문제의 핵심 부분이다. 문제에서 유의 깊게 관찰할 수 있는 부분들은 $10^{-9}$과 같은 빡빡한 오차, $1$초와 같은 수상한 제한, 수상하게 큰 좌표 제한 등이 존재한다. 가장 나이브하게..
[Python] 1199번 오일러 회로 https://www.acmicpc.net/problem/1199 24/09/01  오일러 경로 기본 문제이다. 알고리즘은 간단했으나 시간이 좀 빡빡해서 몇 번의 최적화를 거친 후에야 맞았습니다를 받을 수 있었다. 문제 접근 방식:  무방향 연결 그래프에서 오일러 경로는 정점의 차수가 홀수인 정점이 $0$개이거나 $2$개일 때 만들어 질 수 있다. 차수가 홀수인 정점이 $0$개인 경우, 어느 점에서 시작을 하던 간에 다시 그 점으로 돌아오는 오일러 "회로"를 만들 수 있다. 차수가 홀수인 정점이 $2$개인 경우, 차수가 홀수인 $A$ 정점에서 시작하여 차수가 홀수인 $B$ 정점으로 도착하는 오일러 경로를 만들 수 있다. 이 문제는 오일러 "회로"가 만들어지는 조건을 물어보고 있으며, 그것이 가능한 경우 ..
[Python] 19171번 Euclid https://www.acmicpc.net/problem/19171 24/07/29  어제부터 잡았던 문제인데, 사실 개뻘짓을 하고 있음을 깨달아서 그냥 어이 없어서 적어본다. 문제 접근 방식:  문제에서 요구하는 것은, 세 점 $p_1, p_2, p_3$가 주어지고 어떤 점 $p$에 대하여, $p$와 세 점 사이의 거리의 합이 최소가 될 때, 그 거리의 합을 구하는 것이다. $p_1, p_2, p_3 = (x_1, y_1, z_1), (x_2, y_2, z_2), (x_3, y_3, z_3)$라고 둔다면 다음과 같은 함수를 최소화하는 문제로 바뀐다. $$\begin{align} f(x, y, z) &= \sqrt{(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2} \\ &+ \sqrt{(x-..
[Python] 2389번 세상의 중심에서... / 13708번 모든 점을 포함하는 원 / 2626번 헬기착륙장 / 11930번 Smallest Enclosing Sphere / 9158번 Super Star / 21182번 Weird Flecks, But OK https://www.acmicpc.net/problem/2389https://www.acmicpc.net/problem/13708https://www.acmicpc.net/problem/2626https://www.acmicpc.net/problem/11930https://www.acmicpc.net/problem/9158https://www.acmicpc.net/problem/21182 24/07/27  경사 하강법(Gradient Descent)으로 백준에 있는 최소 외접원 문제들을 해결할 수 있다. 내가 볼 땐 경사 하강법만 알고 있다면 이를 통해 최소 외접원 문제를 해결하는 코드를 짜는 건 굉장히 쉽다고 생각하기 때문에 글을 작성해본다. (경사 하강법만 알고 있다면 다이아 5 4문제를 먹을 수 ..
[Python] 9027번 Stadium https://www.acmicpc.net/problem/9027 24/07/22  지난 주 주간 연습 문제 중 하나로 뽑았던 문제인데, 개인적으로 누적 합 알고리즘을 적용하기에 좋은 문제인 것 같아서 쉽지만 해설을 작성해보고자 한다. 문제 접근 방식:  먼저 문제에서 요구하는 바를 보자. $N$개의 마을 중 한 곳을 선택하여 돔 구장을 짓고자 하고, 각 마을마다 팬이 몇 명 살고있는지, 각 마을의 위치가 어떠한지 또한 주어진다. 각 마을의 위치는 오름차순으로 주어진다.이때 문제에서 요구하는 것은 모든 팬들이 돔 구장으로 모일 때의 이동 거리의 합이 최소가 되도록 돔 구장을 지을 때, 돔 구장의 위치를 출력하는 것이다. 문제 설명의 편의 상 $i$번째 마을의 위치를 $v_i$, 돔 구장의 위치를 $d$,..

티스토리툴바