러닝머신 하는 K-공대생

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 만약 연결 그래프라면 노드 1에서 부터 탐색을 시작해서 총 2가지 색을 이용해 인접 노드를 자신과 다른 색으로 색칠한다. 이때 이분 그래프를 만들때는 색깔을 기준으로 노드를 분류하면 된다. 만약 어떤 노드의 색과 그 노드의 인접 노드의 색이 같은 것이 있다면 이분 그래프는 불가능하다. 연결 그래프가 아니라면 색칠된 수와 전체 노드의 수를 비교했을 때 이 둘이 다를 경우이다. 따라서 이때는 노드 1에서 시작하지 말고 다른 노드들에서 시작해서 동일한 색..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제의 조건에 맞는 A,B,C,D,E 가 존재한다는 것은 각 사람들을 노드로 두고, 친구관계를 갖는 두 사람을 연결하는 간선으로 그래프를 생각하면, 어떤 한 노드에서 시작해서 다른 노드로 이동할때 탐색 깊이가 4 이상이라는 것이다. 즉 DFS를 이용해 어느 한 노드에서부터 시작해 다른 노드를 탐색할 때 깊이가 4 이면 조건을 만족한다고 볼 수 있다. 따라서 처음에 아래와 같이 DFS 코드를 작성했다. def dfs(v,graph,visited,depth): visited[v] = True # 만약 탐색 깊이가 4이면 가능 if depth == 4: print(1) ex..

https://www.acmicpc.net/problem/89728972번: 미친 아두이노요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net단순(?! 조금은 깐깐한) 구현 문제이다. 문제에서 제시된 게임 순서대로 꼼곰히 구현을 하면 된다. 다만 게임을 종료시키거나 로봇을 제거하는 부분을 어떻게 구현할지 적절한 아이디어를 떠올리는 것이 중요하다. 이번 글에는 내가 풀기 위해 떠올린 2개의 아이디어를 설명하고자 한다. 각 아이디어를 보면서 속으로 아이디어의 구현 가능성/명확성/타당성을 확인해보자. 참고로 1번 아이디어는 구현할 때 생각할 점..

19939번: 박 터뜨리기 $N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 www.acmicpc.net 간단한 수학문제이다. 바구니가 k개, 공이 n개인데 최소한 1개 들어가야하고 바구니 속 공의 개수는 다 달라야한다. 공의 개수의 최소는 높이가 1,2,3,..,k일 때 이므로 k(k+1)/2 > n 이면 불가능. n-k(k+1/2)는 1,2,3,..,k 개를 만들고 남은 공의 개수, 이때 가장 많은 공의 개수와 가장 적은 공의 개수의 차는 k-1개가 나올 수 있는 가장 최소임. 이때의 조건은 a+1,a+2,a+3,...,a+k, 즉 남은 공의 개수가 k의..