0. 문제 https://www.acmicpc.net/problem/29687 29687번: Игра Два игрока играют в новую настольную игру. На поле для игры есть города и дороги между ними, причем дороги между разными городами могут имет www.acmicpc.net 문제 해석 두 명의 플레이어가 새로운 보드 게임을 하고 있습니다. 경기장에는 도시와 도시 사이에 도로가 있으며, 도시마다 도로의 길이가 다를 수 있습니다. 또한 두 도시 사이의 도로 길이가 x라면 이 도로에는 (x-1)개의 마을이 연속적으로 있으므로 도시에서 도로의 가장 바깥쪽 마을로, 이 마을에서 이웃 마을로 갈 수 있습니다...
분류 전체보기
https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제 코드 import sys from collections import deque def bfs(x): queue = deque([x]) visited[x] = 1 cnt = 0 while queue: queue.popleft() for i in range(1, n + 1): if visited[i] == 0: queue.append(i) visited[i]..
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 너비 우선 탐색을 이용하여 구현한다. 최소 날짜를 저장할 cnt, 안 익은 토마토 수를 저장할 zero, 익은 토마토의 위치를 저장할 q를 정의한다. 이중 반복문을 통해 익은 토마토라면 q에 append 하고, 안 익은 토마토의 개수를 확인한다. 만약 안 익은 토마토가 없다면 0을 출력한다. 만약 안 익은 토마토가 있다면 dfs를 수행한다. - q가 빌 때까지 반복한다...
문제 https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 코드 #include #include #include #include #include using namespace std; int main() { deque dq; deque dqw; int n = 0; cin >> n; for (int i = 0; i 2) { int f = 0; while (dq.size() != 2) { dqw.push_back(dq.front()); dq.pop_fro..
[문제] https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net [소스코드] T = int(input()) for _ in range(T): N, M = map(int, input().split()) sizes_A = list(map(int, input().split())) sizes_B = list(map(int, input().split())) sizes_A.sort() sizes_B.sort()..
https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 시뮬레이션 너비 우선 탐색 문제 뿌요뿌요의 룰은 다음과 같다. 필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다. 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된..
1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 코드 import sys input = sys.stdin.readline dx= [0,0,1,-1] dy= [1,-1,0,0] t = int(input()) for _ in range(t): m,n,k=map(int,input().split()) #가로세로 배추개수 qocn=[[0]*(m+2) for i in range(n+2)] #배추밭배추위치 visitdi = {} #전체적으로이미방문했나 ans=0 for i in ran..
https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 문제 올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다. 금메달 수가 더 많은 나라 금메달 수가 같으면, 은메달 수가 더 ..
문제 설명 미로를 탈출하는 최단 거리를 구하는 문제이다. 최단 거리를 구해야 하기에 깊이 우선 탐색이 아닌 너비 우선 탐색을 사용하였고, 입력이 붙어서 들어오기에 먼저 string으로 받고 인덱스 하나 하나 집어 넣어주었다. bfs를 도는 중에는 상하좌우를 검사하여 인덱스를 벗어나지 않고/방문하지 않았고/이동할 수 있는 위치일 때 큐에 삽입하였다. 그리고 처음 알았는데 queue.push 대신 queue.emplace를 쓰면 속도도 더 빠르고 pair같은 구조체를 make_pair를 사용하지 않고 바로 집어 넣을 수 있어 편했다. 최단 거리를 구하는게 조금 어려웠는데, 그냥 2차원 배열을 새로 만들어서 기록해주는게 제일 편한듯 했다. 코드 #include using namespace std; int N,..
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 코드 import sys input = sys.stdin.readline n = int(input()) check = list() y = 1 count = list() flag = 0 for _ in range(n): num = int(input()) while y
문제 https://www.acmicpc.net/problem/1918 풀이 중위표기식에서 후위표기식으로 변환하는 것은 스택을 활용하여 풀 수 있다. 후위표기식의 방식에 따라, 계산할 문자를 먼저 문자열에 두고 기호는 스택에 넣어두었다가 출력하면 된다. 하지만, 연산자의 우선순위에 의해 추가적으로 고려해주어야 한다. 우선순위가 더 낮은 연산자가 나오면 더 높은 연산자를 먼저 처리해준다. 또한, 괄호가 나오는 경우 괄호가 닫히는 순간에 괄호가 시작되었던 부분까지 고려하여 변환하면 된다. 코드 formula = input() precedence = {'+': 1, '-': 1, '*': 2, '/': 2} stack = [] postfix = '' for c in formula: if c.isalpha():..
문제 https://www.acmicpc.net/problem/2789 2789번: 유학 금지 아주 멀리 떨어져 있는 작은 나라가 있다. 이 나라에서 가장 공부를 잘하는 학생들은 모두 다른 나라로 유학을 간다. 정부는 최고의 학생들이 자꾸 유학을 가는 이유를 찾으려고 했다. 하지만, www.acmicpc.net 소스코드 word = input() cambridge_letters = set("CAMBRIDGE") filtered_word = "" for letter in word: if letter not in cambridge_letters: filtered_word += letter print(filtered_word) 문제풀이 1. 사용자로부터 입력 단어를 받아 'word'변수에 저장 2. "CAMB..
