https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 난이도: 골드5 소요시간: 45분, hint 문제자체는 다익스트라 유형의 기본문제이다. 다만 제한시간이 0.5초로 매우 짧다. 처음 풀었을 때는 메모리초과가 떴다. 이 문제는 약간 수정하니 해결되었다. 정말 문제는 시간 초과이다. 이 문제를 해결하기 위해서 리스트에서 인덱스접근하는것을 변수로, 중간에 조건으로 브랜치 등을 하였지만 해결이 되지 않았다. 결국 해결한..
Problem Solving/최단 경로
https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 난이도: 실버1 소요시간:45분 관련 알고리즘: 다익스트라(데이크스트라) DFS,BFS,다익스트라,이분검색은 조금 더 익숙해질 필요가 있는 것 같다. 예상치 못하게 오류를 만나 시간을 많이 소비했다. 손에 익어서 깊게 생각안하고도 구현할 정도로 연습을 해야겠다. 아래는 나의 코드다. 고속도로는 전부 이어져 있기 때문에 거리값을 1,2,3,...으로 초기화 했다. 그리고 i+1노드와 전부..
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 난이도: 실버2 소요시간: 30분 다익스트라를 쓰면 풀리는 문제이다. 거리가 1로 고정인 점을 생각하여 다익스트라 알고리즘을 조금 수정 하면된다. import sys import heapq N,M,K,X = map(int,sys.stdin.readline().split()) INF=1e9 dist = [INF]*(N+1) g..
이 문제는 이것이 코딩테스트다 262페이지 문제이다. 최단 거리문제는 전부 똑같은 유형이다. 정답이 거의 동일하고 출력부분만 다른 경우가 많다. 이 문제는 입력의 값이 크기에 우선순위큐다익스트라 알고리즘을 이용하여야 한다. 다익스트라 구현 방식을 이해를 하여야 한다. 그리고 거리비용이 현재보다 커질 때는 가지치기(branch and bound)를 미리 해주어야 한다.는 것을 알아야 한다. https://yunzae.tistory.com/94 최단경로(다익스트라,플로이드워셜) 최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립 yunzae.tistory.com 아래는 나의..
이 문제는 이것이 코딩테스트다. 259페이지 문제이다. 이 문제는 E,V(간선,노드)가 100이하로 작다. 전형적인 플로이드 워셜문제이다. 일반적으로 500정도면 플로이드워셜을 사용하여도 된다. 아래는 나의코드이다. import sys INF = int(1e9) companyNum,wayNum = map(int,sys.stdin.readline().split()) myMap= [[INF]*(companyNum+1) for _ in range(companyNum+1)] for i in range(1,companyNum+1): myMap[i][i]=0 for _ in range(wayNum): temp=list(map(int,sys.stdin.readline().split())) myMap[temp[0]][..
