내가 기억하려고 만든 블로그 내가 기억하려고 만든 블로그

문제 설명, 조건 ● 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. ● 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다. ● 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. ● 각 도시의 번호와 통로가 ..

답안 예시 INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)을 만들고, 무한으로 초기화 graph = [[INF] * (n+1) for _ in range(n+1)] # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1, n+1): for b in range(1, n+1): if a == b: graph[a][b] = 0 # 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화 for _ in range(m): # A에서 B로 가는 비용은 C라고 설정 a, b, c = map(int, input().split()) g..

답안 예시 import heapq import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(n+1)] # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) # 모든 간선 정보를 입력받기 for _ in range(m): a, b, c = map(int, input().split()) # a번 노드에서 b번 노드..

우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 힙(Heap) 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나 최소 힙(Min Heap)과 최대 힙(Max Heap)이 존재 최소 힙 최대 힙 출처 : https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7

답안 예시 import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(n+1)] # 방문한 적이 있는지 체크하는 목적의 리스트를 만들기 visited = [False] * (n+1) # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) # 모든 간선 정보를 입력받기 for _ in range(m): a, b, c..

문제 설명, 조건 ● N명의 병사가 무작위로 나열되어 있습니다. 각 병사는 특정한 값의 전투력을 보유하고 있습니다. ● 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 합니다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 합니다. ● 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용합니다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 하고 싶습니다. ● 입력 조건 첫째 줄에 N이 주어집니다. (1

문제 설명, 조건 ● n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. ● 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요. ● 입력 조건 첫째 줄에 테스트 케이스 T가 입력됩니다. (1

문제 설명, 조건 ● N가지 종류의 화폐가 있습니다. 이 화폐들이 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 합니다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다. ● 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수입니다. ● M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요. ● 입력 조건 첫째 줄에 N, M이 주어진다. (1