취준생의 코딩테스트 연습기

# 문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net # Soultion 최소 시간을 구하기위해 bfs를 사용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 from collections import deque n,k = map(int,input().split()) queue = deque([n]) visited = [0]*100001 visite..

# 문제 링크 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net # Soultion 최소 일수를 구하는 문제는 bfs를 이용한다. 7576번의 토마토 문제와 동일하지만, 3차원 배열만 신경써주면 된다. 또한 10줄에서 입력을 input()으로 받으면 시간초과가 발생한다. -> sys.stdin.readline()으로 사용해주기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..

# 문제 링크 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net # Soultion BFS를 이용하여 최단거리를 푸는 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 from collections import deque n,m = map(int,input().split()) graph = [] for _ in range(n): graph.append(list(map(int,input()))) dx = [-1,1,0..

# 문제 링크 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net # Soultion bfs 사용시 recursionError가 발생하므로, 2줄에서 재귀 최대깊이를 설정해주어야한다. 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 import sys sys.setrecursionlimit(10000) t= int(input()) for _ in range(t): ..

# 문제 링크 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net # Soultion DFS를 이용하여 푼 문제이다. 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 n = int(input()) graph = [] for _ in range(n): graph.append(list(map(int,input()))) grp = [] cnt ..

# 문제 링크 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net # Soultion DFS를 이용하여 푼 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 n = int(input()) m = int(input()) graph = [[]*n for _ in range(n+1)] for _ in range(m): a,b = map(int,input().split()) graph[a].append(b) ..

# 문제 링크 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net # Soultion dfs와 bfs에 대해 알면 쉽게 풀 수 있는 문제이다. 주의) 인접한 노드가 작은 순으로 방문한다고 했으므로, 13,28번째 줄처럼 sorted()를 이용하여 오름차순 정렬해준다. 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 ..

# 문제 링크 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net # Soultion 여러가지 경우의 수를 잘 생각해야 하는 문제이다. 나는 test case가 '(()([())])'인 경우에 0이 나와야하는데 28이 나오는 반례를 해결했다. 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 s = ..

# 문제 링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net # Soultion 예제3번의 나눗셈부분을 신경써서 처리하면 간단한 문제이다. 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 from itertools import permutations n = int(input()) o..

# 문제 링크 www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net # Soultion 1 2 3 4 5 6 7 8 9 10 11 n = int(input()) path = list(map(int,input().split())) price = list(map(int,input().split())) answer = 0 liter = price[0] for i in range(len(path)): answer = answer + path[i]*liter..