기록일지

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제요약: 2차원의 크기n이 주어지고 2차원 배열이 주어진다. 왼쪽위부터 0,0이라고 할때 0,0부터 n-1,n-1 까지 가는 길에 있는 경로의 값의 합중 가장 작은 값을 출력하라. 난이도: 골드4 소요시간: 45분 +15분 제출횟수: 2회 1차 코딩: import sys input = sys.stdin.readline sys.setrecursionlimit(int(1e6)) d..

코딩테스트/최단 경로 2023. 11. 22. 20:52

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제요약: 마을개수, 도로개수(단방향), 파티가 열리는 마을 세개가 주어지고 도로마다 걸리는 시간들이 주어졌을때, 각 마을에서 출발하는 사람들중에 파티하는마을에 들렸다가 집에 가는 시간이 가장 오래걸리는 사람의 이동시간을 구하여라 난이도: 골드3 소요시간: 15분 제출횟수: 2회 1차코딩: import sys import heapq as hp input = sys.s..

코딩테스트/최단 경로 2023. 10. 20. 10:05

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제요약: 도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다. 난이도 : 골드4 소요시간: 20분 제출횟수: 1회 코딩: import sys input = sys.stdin.readline v,e = map(int,input().split()) INF = int(1..

코딩테스트/최단 경로 2023. 9. 15. 09:45

https://school.programmers.co.kr/learn/courses/30/lessons/132266 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제요약: 지도와(위치간 거리는 1) 병사들의 현재 위치를 담은 리스트가 주어졌을때 , 병사들이 목표지점까지 돌아오는데 걸리는 시간을 반환하라 (못돌아오면 -1) 소요시간: 20분 +A 난이도 3 1차코딩: from collections import deque def solution(n, roads, sources, destination): graph = [[] for _ in range(n+1..

코딩테스트/최단 경로 2023. 7. 15. 16:34

https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제설명: 노드와 엣지가 주어지고 출발지는 같고 목적지가 두개이다. 이때 택시를 타는것처럼 중간까지 같이가는경우는 한번만 비용을 낸다고 할때 목적지까지 도달하는 최소금액을 구하여라. 소요시간: 15분 난이도3 코딩: def solution(n, s, a, b, fares): #플로이드로 전구간 이동경로 구하기 INF = int(1e9) graph = [[INF]* (n+1) for _ in ran..

코딩테스트/최단 경로 2023. 7. 6. 18:42

문제 요약: 이문제는 이코테 책 Q38번 문제로 학생수n, 그리고 성적비교 결과개수 m개 가 주어진 뒤, 성적이 두명중에서 누가 위인지만 m개의 결과를 알려준 후, 성적 순위를 정확히 알 수 있는 학생은 모두 몇 명인지 계산하는 프로그램을 작성 이코테 난이도 2 소요시간 : 18분 1차시도: import sys input = sys.stdin.readline n,m = map(int,input().split()) INF = int(1e9) arr = [[INF]*n for _ in range(n)] for _ in range(m): s,e = map(int,input().split()) arr[s-1][e-1] = 1 #플로이드 워셜 for k in range(n): for y in range(n): f..

코딩테스트/최단 경로 2023. 6. 13. 19:31

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제설명: 가장 기본적인 플로이드 워셜 문제이다. 소요시간: 10분 1차시도: import sys input = sys.stdin.readline n = int(input()) m = int(input()) #플로이드 INF = int(1e9) graph = [[INF] * n for _ in range(n)] for i in range(n): graph[i][i] = 0 for _ in rang..

코딩테스트/최단 경로 2023. 6. 9. 09:31

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 문제설명: 대표적인 다익스트라 문제, x으로 부터 거리가 k 인 지점을 찾아라 실버2 소요시간: 16분 1차 시도(정답): #한곳에서 다른곳들 까지 최소거리 다익스트라 import sys from collections import deque input = sys.stdin.readline n,m,k,x = map(int,in..

코딩테스트/최단 경로 2023. 6. 2. 19:00