추측보다는 측정

문제:www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 이 문제를 풀었을 때 75%에서 도저히 개선이 안되서 결국 다른 분의 코드를 참고한 문제였다. import sys N = int(sys.stdin.readline()) graph=[[] for _ in range(N+1)] for _ in range(N-1): a,b=map(int,sys.stdin.readline().split()) graph[a].append(b) g..

문제:www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 import sys from collections import deque N = int(sys.stdin.readline().rstrip()) graph=[[] for _ in range(N+1)] for _ in range(N-1): a,b= map(int,sys.stdin.readline().rstrip()..

문제:www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net N,M=map(int,input().split()) arr=[list(map(str,input()))for _ in range(N)] visited = [[False]*M for _ in range(N)] dy=[0,0,1,-1] dx=[1,-1,0,0] flag=False def scope(y,x): if y>=0 and y=0 and x

문제:www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net import sys N=int(input()) parent=[0]*(N+1) ans=[0]*(N+1) graph=[[] for _ in range(N+1)] graphSize=[0]*(N+1) for _ in range(N): a,b=map(int,input().split()) graph[a].append(b) graph[b].append(a) graphSize[a]+=1 gra..

문제:www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이 문제는 처음에 문제 자체를 이해 못한 것이 컸다. 문제를 이해해도 어떻게 풀어야 할 지 막막해서 결국 다른 분들의 코드를 참조했다. from collections import deque import sys input = sys.stdin.readline k = int(input()) def bfs(start): bi[start] = 1 q = deque() q.append(start) wh..

문제:www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 이 문제는 비트마스크의 개념을 정확히 몰랐을 때라 그런지 감이 전혀 안왔다. 처음에는 그냥 우선 자릿수가 큰 게 더 크므로 가로로 싹 다 더한 값과 세로로 싹 다 더한 값 중 큰 거 아닐까 하는 생각을 했지만 역시 예외는 있었다. def bitmask(): global maxAns # 비트마스크로 2^(N*M)의 경우의 수를 따져본다 for i in range(1

문제:www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이 문제는 기존의 방식으로 모든 가능한 수열의 경우를 다 확인하는 식으로 코딩했었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import sys N,S=map(int,sys.stdin.readline().rstrip().split()) li = ..

문제:www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net import sys N=int(sys.stdin.readline()) ar=[] passing=[False]*(N) for _ in range(N): ar.append(list(map(int,sys.stdin.readline().split()))) li = [int(i) for i in range(N)] ret=10e9 def func(ans,celi,aim):..