D - New Friends (atcoder.jp) D - New Friends AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제를 요약하자면... 어떤 노드 X에서 직접적으로 연결되어 있지는 않지만, 다른 노드들을 거쳐서 도달할 수 있는 노드 Z가 존재한다면 그러한 경로의 개수를 구하는 문제 예를 들어 위 그래프에서 1번 노드에서 2,4번은 직접 연결되어 있고, 3번 노드는 직접 연결되어 있지 않은데, 1 > 2 > 3으로 갈 수 있으므로 1개 2번 노드에서 1,3번은 직접 연결되어 있는데 4번은 직접 연결되어 있지..
https://atcoder.jp/contests/abc348/tasks/abc348_d D - Medicines on Grid AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 자체는 어디서나 많이 보던 기본적인 BFS/DFS 셋팅이다 2차원 맵에 특정 위치에 약이 있는데, 이 약을 먹으면 에너지가 E로 된다. 이동할때마다 에너지가 1씩 감소한다 약은 먹어도 되고 먹지 않아도 되는데, 단 1번만 먹을 수 있고 먹으면 사라진다 에너지 0부터 시작한다고 할때, 목표로 하는 지점에 도착할 수 있는가? 그냥 기본적인 BFS..
1. 틱택토 게임 3*3 게임판에서 O와 X를 서로 번갈아 둔다. 가로나 세로, 대각선으로 1줄(3개)이 서로 같게 만들면 승리 3*3 게임판에서 각각의 cell은 O, X, '.' 3가지중 한가지가 들어갈 수 있으므로.. 모든 가능한 게임판의 경우는 $3^{9} = 19683$가지로 몇가지가 없다 이 경우 중간에 게임이 끝나서 더 이상 둘 수 없는 경우가 있기 때문에 그런 경우를 고려해서 제외하면 된다. BFS를 이용해서 모든 가능한 경우를 조사할 수 있다. 1) deque에 (['.']*9, (첫 시작이 두는 수))를 먼저 넣고 BFS를 수행 특히 배열이 9칸이기 때문에 배열을 deepcopy해도 시간이 그렇게 오래걸리지 않는다. 2-1) 큐에서 하나씩 뽑은 다음, 게임판 배열을 순회해서 둘 수 있는..
1. 문제 10159번: 저울 (acmicpc.net) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 2. 풀이 그냥 보면 어떻게 해야할지 감 잡기가 쉽지 않다.. 하지만 "2 > 3, 3 > 4로부터 2 > 4라는 것을 알 수 있다"를 봤을때, 1 > 2, 2 > 3, 3 > 4, 5 > 4, 6 > 5를 마치 방향 그래프에서 간선으로 보면 2에서 4로 도달할 수 있는가? 아닌가를 체크하면 되는 문제이다. 사실 뭐 최단 거리를 묻는 것은 아니므로 BFS나 DFS로 탐색하면 해결할 수..
1. 문제 28069번: 김밥천국의 계단 (acmicpc.net) 28069번: 김밥천국의 계단 첫 번째 줄에 계단 개수에 해당하는 $N$, 계단을 오르는 횟수 $K$가 주어진다. $(1 \leq N, K \leq 1\,000\,000)$ www.acmicpc.net 2. 풀이1 그냥 보면 두가지 행동중 하나를 할 수 있는 전형적인 BFS문제 1) 한칸을 올라간다 2) $\left \lfloor \frac{i}{2} \right \rfloor$만큼 올라간다 0번부터 시작한다고 명시되어 있으니 BFS처럼 풀어보면.. 정확히 K번 행동해야하면서 매 행동마다 queue의 길이만큼 순회시키는데 해당 좌표 i가 i+1과 i+i//2를 이동할 수 있으면 queue에 넣어주고.. K번 행동한 후에 n이 queue에 ..
1. 문제 25418번: 정수 a를 k로 만들기 (acmicpc.net) 25418번: 정수 a를 k로 만들기 7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다. www.acmicpc.net 정수 a에 1을 더하거나 2를 곱해서 k를 만들때, 연산 횟수의 최솟값을 구하는 문제 2. 풀이1(BFS) 이 문제의 기본은 BFS로 푸는 것이다 정수 a에서 시작해서, delta 배열은 1,2가 있고 1이 나오면 a + 1에 가서 범위를 벗어난건지, 이미 방문했는지 검사 2가 나오면 2a에 가서 범위를 벗어난건지, 이미 방문했는지 검사 from collections import deque def bfs(..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
