문제https://www.acmicpc.net/problem/9205 풀이코드# 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.# 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.from collections import dequedef bfs(): que = deque() que.append((home_idx_x,home_idx_y)) while que: x,y = que.popleft() if ab..
Algorithm
문제https://www.acmicpc.net/problem/5567 풀이코드 from collections import dequedef bfs(start_num,depth): global answer que = deque() que.append((start_num,depth)) while que: start_num,depth = que.popleft() visited_list[start_num] = True for i in linked_list[start_num]: if visited_list[i] != True and depth 문제접근친구관계를 저장하기 위해 linked_list 를 사용하여 친구관계를 저장한다. 이때 a..
문제https://www.acmicpc.net/problem/17070 풀이 코드1(실패) (BFS탐색) from collections import dequen = int(input())mapp = [list(map(int, input().split())) for _ in range(n)]dx = [1, 1, 0] # 가로, 대각선, 세로 이동dy = [0, 1, 1]now = [0, 1, 2] # 0: 가로, 1: 대각선, 2: 세로dp = [[[0] * 3 for _ in range(n)] for _ in range(n)] # dp[y][x][방향] = 경로 개수 저장dp[0][1][0] = 1 # 처음 파이프 위치: (0,1)에서 가로로 시작que = deque([[0, 1, 0]]) # ..
문제https://www.acmicpc.net/problem/4179풀이 코드from collections import dequeimport sys# J와 F동시에 BFS시작# 탐색한 좌표를 담을 수 있는 변수 x 필요 # 해당 변수에 J와 F를 구분할 수 있는 변수 필요# 좌표를 담은 변수x를 pop하며 탐색 진행# 탐색을 한 후, 다시 x에 저장, 이때 카운티 1증가# J가 F랑 곂치면 임파서블 출력# J가 벽 외각에 도달하면 cnt 출력r,c = map(int,input().split())dx = [-1,1,0,0]dy = [0,0,-1,1]answer = "IMPOSSIBLE"def bfs(): global answer while que: # print(mapp) ..
경주로 건설문제 설명건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다. 제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다.설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다.경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽..
구현PCCP로 코딩테스트 역량을 보는 필기 시험이 있어서, PCCP를 준비하며 문제를 풀어봤습니다. https://programmers.co.kr/app/with_setting/tests/131575/challenges/algorithms/20179?language=python3 문제 풀이def solution(bandage, health, attacks): now_health = health # 최대 체력 attack_time = [i[0] for i in attacks] dealing = [i[1] for i in attacks] max_time = max([i[0] for i in attacks]) # 최대시간 bandage_time = bandage[0] # 시전 시간 ..
전력망을 둘로 나누기 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 2 이상 100 이하인 자연수입니다. wires는 길이가 n-1인 정수형 2차원 배열입니다. wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 ..
문제 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 풀이 코드 # 다음과 같은 우선순위를 차례로 적용하여 만들어진다. # # 자주 나오는 단어일수록 앞에 배치한다. # 해당 단어의 길이가 길수록 앞에 배치한다. # 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 # # M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다..
문제 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 코드 풀이 import heapq n,m = map(int,input().split()) INF = int(1e9) linked_list = [[] for _ in range(n+1)] for i in range(m): node1,node2,cost = map(int,input().split()) linked_list[node1].append((node2,cost)) linked_list[node2].append((node1,cost)) distance = [INF..
