아롱이의 PS하는 블로그

"파이썬으로 구현하는"시리즈 6다익스트라(Dijkstra) 가중치가 있는 그래프에서 최단 경로를 찾으려면 어떻게 해야 할까?PS 및 경진 프로그래밍에서 쓰이는 최단 경로 알고리즘은 크게 3가지가 있다. 1. 플로이드-워셜 알고리즘 $O(N^3)$, 직접 모든 노드를 거쳐가는 경우 다 살펴보는 알고리즘.장점으로는 딱 한 번 실행해서, 모든 노드 쌍 간 최단거리를 바로 알 수 있다는 점이다. 2. 벨만-포드 알고리즘$O(N^2)$, 음수 간선에서의 최단거리를 찾아내는 알고리즘.음수 사이클이 있다면 찾아낼 수도 있다. 3. 다익스트라 알고리즘$O(N^2)$, 우선순위 큐를 이용해 최적화하면 $O(N log N)$가장 널리 쓰이는 최단거리 알고리즘. 단 음수 간선이 있으면 못쓴다. 오늘은 다익스트라 알고리즘의..

https://www.acmicpc.net/problem/13460 들어가기에 앞서...오랜만에 복귀하였다.길고 긴 공백기간(브론즈 4, 5만 품)을 지나고, 12년간 달려왔던 입시의 길도 이제 모두 마무리되었다. 대학 발표만을 기다리고 있는 상황이다.입시에 전념하느라 PS를 그만두는 동안 정말 많은 일이 있었다.일단 코딩 실력이 너무 많이 줄어들었다.전성기때 NYPC 2라운드를 합격해놓고, 본선에서 망쳤다. (간단한 실수 하나를 못봐서 자존심 상해서 그냥 4시간동안 그문제만 들이팠다. 근데 1~2달 쉬었다고 그렇게 못 할 일인가...?) 어쨌든 이제 입시가 끝났고, 학교에서는 모두가 고등학교의 마지막 시절을 만끽하는 중이다.나는 PS 실력을 다시 쌓아올리기로 결심하고 다시 백준을 켰다. 눈에 가장 먼저..

https://www.acmicpc.net/problem/18940풀이먼저 지난번에 올린 스프라그-그런디 정리(이하 스그정리)에 관한 글을 읽어보고 오면 도움이 많이 된다. 13034번 문제와 비슷하다.먼저 N = 0일때는 그룬디 수가 0(패배상태이므로)N = 1, 2일때는 그룬디 수가 1이다. 단 한번의 행동으로 무조건 패배상태로 만들 수 있으므로 이 경우는 마음대로 그룬디 수를 1로 잡아도 좋다. N이 3 이상일때는, 어떤 임의의 부분에서 연속된 최대 3개의 카드를 제거함으로 인해 보드판이 두 개로 나뉜다.가령 다음과 같다.N = 6일때 3을 골랐다고 해보자. 이제 보드판은 (1) 부분과 (5, 6) 부분 두 개로 나누어졌다. 이 상태는 grundy[1]과 grundy[2]의 님 합으로 표현할 수 있..

https://www.acmicpc.net/problem/20544풀이풀고 나서 보니까 많은 분들이 2차원, 혹은 4차원(!) dp를 구현하여 고통을 호소하고 계셨다.허나 이 문제는 단순 수학 점화식 풀듯이 일차원 dp로 쉽게 풀 수 있다.(이걸로 숏코딩도 쉽게 할 수 있다)아래에서는 그 풀이를 소개하고자 한다. 구하고자 하는 값을 $a_n$이라고 하자.$a_n$은 마지막 부분에 어떤 종류의 장애물이 오느냐에 따라 아래와 같이 점화식으로 표현 할 수 있다.근데 그냥 단순히 $a_{n}=a_{n-1}+2\times a_{n-2} +3\times a_{n-3}$ 라고 표현하면 빨간 글씨처럼 '누락되는 부분'이 있다. 바로, 0101101.....02와 같이 마지막 부분 전까지는 0과 1과 나오는 상황이다. ..

https://www.acmicpc.net/problem/11717풀이바로 이전에 스프라그 - 그런디 정리 소개글을 쓰고 왔다.이 문제도 스그정리를 써서 풀 수 있다. 하나 깨달은 점은, 기존과 달리 2차원 게임에서, 각각의 '칸'에 그룬디 수를 정의할 수 있을 뿐만 아니라, 그냥 어떤 게임판의 일부분 그 자체가 그룬디 수 화 될 수 있음이다. 일단 한 가지 간단한 관찰을 하고 들어가보면, 벽과 x를 따로 구분하기 어려우니까 그냥 벽이 설치되는 것이 아니라 x가 설치되는 것이라고 생각해도 좋다.(사실 근데 크게 별로 상관은 없다.) 4차원 dp에다가 각 보드의 부분의 그룬디 수를 저장할 수 있다.dp 형식은 #dp[x1][y1][x2][y2]는 (x1, y1)부터 (x2, y2)까지의 보드의 Grundy..

서론게임 이론에서 게임의 현재 상태를 분석하기 위해 쓰는 스프라그 - 그런디 정리.백준에서 날먹이라는 말이 있다. 어떤 이론이길래 그렇게 쉽게 되는 것일까? 솔직히 말해서 완벽하게 이 이론을 이해하려면 어렵다고 본다.....구현 자체가 쉽기 때문에 날먹이라는 말이 있는 것 같다.따라서 오늘 이 글에서는 스프라그 - 그런디 정리를 내가 이해한 바에 따라 쉽게 설명해보고자 한다. 게임 상태가장 먼저, 게임의 '상태'라는 것을 이해하고 넘어가자.여러분들은 모두 어릴 적 '베스킨라빈스 31'이라는 게임을 들어본 적이 있을 것이다.게임의 규칙은 다음과 같다.선공과 후공이 번갈아가며, 1부터 시작하여 연속한 자연수를 1~3개 부른다. 31을 부르게 되는 사람이 진다. 수학을 좀 해본 사람들이라면(꼭 굳이 그렇지는 ..

https://www.acmicpc.net/problem/8481 소요시간: 3일풀이이 문제를 왜 만들었을까?아주 간@단한 문제이다! 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 주어지면 그에 걸맞는 출력만 하면 된다!! 0번 #구현더보기ONTAK 2010를 출력하면 된다. 소요바이트: 19바이트1번#압축 #구현 #파싱더보기10개의 데이터들 중에서 길이가 가장 길다.같은 알파벳이 반복되므로, G#2932#o#2931....과 같이 해당 문자와 등장 횟수를 미리 계산해서 문자열로 만든 후 출력하였다. 여담으로 반복을 줄인 원문은 해당 대회의 Godzilla라는 문제이다. + 반복되는 횟수가 계차수열이다. 숏코딩할 때 이용할 예정이다. 소요바이트: 13922바이트2번#구현더보기피보나치 수열을..

https://www.acmicpc.net/problem/1533풀이인접 행렬의 특징으로는,A[i][j]가 정점 i에서 정점 j로 갈 수 있는 길의 개수라고 하면A를 t번 거듭제곱한 행렬의 [x][y]는, 길을 t개 거쳐서 정점 x에서 정점 y까지 가는 경로의 개수이다.여기서 알 수 있다 다만 이 문제에서는 길에 가중치가 있다. 단순히 주어진 행렬을 T번 곱한다고 해서 답이 나오지 않는다. 12850처럼 문제를 해결해주기 위해서, 인접행렬의 모든 원소를 1로 만들어주는 전략을 세우기 위해그래프의 형태를 조금 바꿔주자! 길을 가는데 걸리는 시간이 1, 2, 3, 4, 5중 하나이므로 우리는 다음과 같은 전략을 세울 수 있다. 예를 들어 정점 2에서 1로 가는데 3분이 걸린다고 하자.정점 1을 이제 1, 1..

https://www.acmicpc.net/problem/18122https://www.acmicpc.net/problem/27743풀이충분히 찍어서 맞출 수 있는 문제이다. 일단 일반적으로 하노이 탑 N개를 옮기는 최소 횟수는 $2^{N} - 1$회임이 잘 알려져있다.그런데 18122번 문제와 같은 경우는 어떻게 하면 좋을까? 일단 N = 1일 때를 살펴보자. 그림과 같이 3회를 옮기면 됨을 알 수 있다. N = 2일 때는 어떨까? 일단 위에 쌓여있는 쪼그만 놈들은 무시하고, 큰 1, 2번 판이 어떤 움직임을 보여야 하는지 생각해보자. 그러면 N = 1일때와 마찬가지의 방법으로 3번 움직여야 함을 알 수 있다. 이제 쪼그만 놈들의 움직임을 보자. 큰 판들이 위와 같이 잘 움직일 수 있게 쪼끄만 놈..

이 글은 주기적으로 계속 업데이트 될 예정입니다. 역학탄성충돌 속도 공식 $v_{1}'=\frac{m_{1} - m_{2}}{m_{1}+m_{2}}v_{1}+\frac{2m_{2}}{m_{1}+m_{2}}v_{2}$ $v_{2}'=\frac{2m_{1}}{m_{1}+m_{2}}v_{1}+\frac{m_{2}-m_{1}}{m_{1}+m_{2}}v_{2}$전자기학 직선도선 근처의 자기장$B = \frac{ \mu _{0}I}{2\pi r}$ 광학/현대물리 드브로이 파장$ \lambda =\frac{h}{mv}$ 운동량$p=\frac{h}{\lambda }$ eV(전자볼트)헷갈리지 말자. 에너지(J) 단위이다!전자 1개가 1V를 거슬러 올라갈 때의 에너지이다. 보어의 원자모형$L = mvr = n\frac{h..