kth990303의 코딩 블로그

그룹원 한분께서 요청해주신 문제를 해결하면서 degree sequence 라는 개념을 알게 됐다. Warming Up 요청해주셨던 문제는 아래와 같다. 한 번 풀어보도록 하자. (degree sequence 개념을 몰라도 해결이 가능하다.) https://www.acmicpc.net/problem/23578 23578번: 비 오는 날 피에스고등학교의 교장 이환이는 학교를 매우 사랑한다. 그래서 이환이는 매일 점심시간에 학교의 모든 건물을 돌아다닌다. 비가 오는 어느 날, 이환이는 학교 곳곳을 돌아다니고 싶었지만 비 www.acmicpc.net 불만을 최소화하기 위해서는 최소한의 다리로 건물을 연결해야 하며, 따라서 mst를 금방 떠올릴 수 있다. 그러나, 단순 mst 문제는 아니고, 차수에 따라 답이 달..

2009 KOI 고등부 1번 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/2487 2487번: 섞기 수열 A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 www.acmicpc.net 문제를 요약하자면, 섞기 전 index에 위치한 value값을 섞은 후의 index로 위치하게 할 때, 맨 처음 순서와 똑같은 순서로 놓이게 되는 때는 몇 번째인지 구하는 문제이다. 의식의 흐름 및 해설 섞기 전 index에 위치한 value가 섞은 후에는 index에 위치하게 된다. 이를 그림으로 나타내면 아래와 같다. 위 ..