📁문제 풀이

[Python] 프로그래머스 무지의 먹방 라이브 | Heap(힙) | 2019 KAKAO BLIND RECRUITMENT

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 가장 작은 시간이 걸리는 음식 부터 처리한다. (heapq 사용) - 만약 모든 음식의 개수 보다 k가 크다면 모든 음식을 먹고도 시간이 남는 것이므로 -1 반환 - 한번의 로테이션을 위해 필요한 음식 개수는, 0이 아닌 음식의 수이다.(length) - (다음 최소 음식 개수) - (이전에 처리한 음식 개수) = 현재 처리해야..

[Python] 백준 4485 녹색 옷 입은 애가 젤다지? | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 해결 포인트 - 다익스트라를 이용하여 각 위치별 (0, 0)에서 최소 비용을 계산 - dr, dc : 각 위치에서 아래, 위, 오른쪽, 왼쪽 위치를 방문 하기 위한 방향키 - graph : 각 위치 방문을 위해 필요한 비용 - distance : 각 위치에서 (0, 0)까지 가기위한 최소 비용, 초기는 무한수 작성 코드 imp..

[Python] 백준 1504 특정한 최단 경로 | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 해결 포인트 - v1 -> v2 순서 또는 v2 -> v1 순서 각각의 거리를 구하여 작은 값을 출력한다. (2번의 다익스트라) - 경로가 없는 경우(결과 값이 INF보다 크거나 같은 경우) -1을 출력 자세한 내용은 코드 주석 참고 작성 코드 import sys import heapq input =..

[Python] 백준 13549 숨바꼭질 3 | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 작성 코드 import heapq INF = int(1e9) N, K = map(int, input().split()) # 시작 위치, 도착 위치 distance = [INF]*100001 # 100001개의 떨어진 거리 def dijkstra(start): # 다익스트라 distance[start] = 0 # 시작..

[Python] 백준 1916 최소비용 구하기 | 다익스트라 | 시간초과

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 해결 포인트 - 받을 입력이 많으므로 sys.stdin.realine 을 사용한다. (시간 초과 해결) - 전형적인 다익스트라 문제 유형이다 - 우선순위 큐(최소힙)를 사용하여 최소 거리 노드를 선택 - distance : start 노드로부터 각 노드의 거리를 저장 (INF 로 초기화) - graph : 각 ..

[Python] 프로그래머스 가장 먼 노드 | BFS | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - BFS와 다익스트라 알고리즘 두 가지 풀이 방식으로 해결 (DFS도 가능하나 python은 DFS 효율이 좋지 못 함) 자세한 설명은 주석 참고 작성 코드 BFS 풀이 from collections import deque def solution(n, edge): que = deque() # BFS를 위한 큐 graph = [[]..

[Python] 백준 11404 플로이드 | 플로이드 워셜

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 해결 포인트 - 플로이드 워셜 알고리즘 - graph : 2차원 배열로 노드 별 각 노드까의 최소 거리를 저장한다. graph[i][j] 는 i에서 j로 가기 위한 최소 이동 거리를 의미함 - 각 간선 정보를 따라 무한수(INF)로 초기화 한 graph를 수정한다. 동일한 노선의 길이가 다른 간선이 있음으로 주의 필요 - a -> b 노선에 대..

[Python] 백준 18352 특정 거리의 도시 찾기 | 다익스트라 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 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 문제 해결 포인트 - 다익스트라(Dijkstra) 알고리즘 - distance : X로부터 각 노드의 가장 짧은 경로. 경로가 없다면 무한수(INF) - graph : 각 노드가 연결되어 있는 정보 (연결 리스트) - q : 지금까지 계산 된 거리 중 간선이 가장 짧은 것을 ..

[Python] 백준 1753 최단 경로 | 다익스트라 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 해결 포인트 - 대표적인 다익스트라(Dijkstra) 알고리즘 문제 - 시작노드부터 각 노드까지 최소 거리를 저장하는 배열(distance)을 무한수(INF)로 초기화 - 연결 리스트 graph를 선언하여 각 노드의 연결 여부와 무게를 튜블형태로 저장 : graph[i][0]은 i와 연결된 노드를 의미하고 ..