본문 바로가기
반응형

전체 글 목록571

[최단 경로] 백준 11657번: 타임머신 / 골드 4** https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 아직은 생소한 벨만-포드 알고리즘이 필요한 문제다. 벨만-포드 알고리즘과 다익스트라의 차이점은 벨만-포드는 음수 가중치가 있는 경우에도 최단 경로를 찾을 수 있다. 공통점은 시작 노드를 특정하고 그 노드에서 다른 노드까지의 거리를 구한다는 것이다. 원리 자체는 플로이드-워셜과 비슷하다는 느낌을 받았다. 다만 벨만-포드는 음수 사이클에 빠.. 2021. 6. 2.
[최단 경로] 백준 1261번: 알고스팟 / 골드 4 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net import heapq y_lim, x_lim = map(int, input().split()) graph = [] visit = [] for i in range(x_lim): graph.append([x for x in input()]) visit.append([0]*y_lim) dx = [-1,1,0,0] dy = [0,0,-1,1] q = [] heapq.heappush.. 2021. 6. 1.
[최단 경로] 백준 13549번: 숨바꼭질 3 / 골드5 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net import heapq start, target = map(int, input().split()) visit = [] q = [] heapq.heappush(q, [0, start]) while q: time, n = heapq.heappop(q) if n == target: print(time) break if n not in visit: visit.append.. 2021. 6. 1.
[최단 경로] 백준 18352번: 특정 거리의 도시 찾기 / 실버2 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net import collections import heapq n,m,k,x = map(int, input().split()) graph = collections.defaultdict(list) for i in range(m): u, v = map(int,input().split()) graph[u].append([v,1]) di.. 2021. 6. 1.
[그리디] 백준 10775번: 공항 / 골드2 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) gate = [0]*(n+1) count = 0 for i in range(m): num = int(sys.stdin.readline()) docking = False for j in range(num,0,-1): if gate[j]==0.. 2021. 5. 31.
[그리디] 백준 1700번: 멀티탭 스케줄링 / 골드1 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net import collections n, k = map(int, input().split()) order = collections.deque(list(map(int, input().split()))) holes = [0]*n count = -n while order: elem = order.popleft() if elem not in holes: # one device should be pulled.. 2021. 5. 31.
반응형

티스토리툴바