1. 문제 23286번: 허들 넘기 (acmicpc.net) 23286번: 허들 넘기 첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의 www.acmicpc.net 2. 풀이 출발 정점에서 도착 정점으로 가는 길에 가중치가 가장 큰 간선의 가중치가 최소가 되는 경로를 찾는 문제 경로에서 가중치가 가장 큰 간선을 bottleneck path라고 부른다 이 bottleneck path의 가중치를 최소로 만드는 문제가 minimum bottleneck path problem 여러가지 방법이 있는것 같기는 한데.. 가장 기본은 다익스트라 알고리즘을 살..
1. 문제 1238번: 파티 (acmicpc.net) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 2. 풀이 이 문제의 핵심은 x번 마을에서 다시 i = 1,2,...번 마을로 되돌아오는 최단 거리가 필요하다는 점이다. 다익스트라 알고리즘은 출발 정점 start에서 다른 정점 1,2,...,n번 까지 가는 최단 경로를 구해주는 알고리즘이지 1,2,...,n번 각각의 정점에서 start로 되돌아오는 최단 경로를 구해주는 알고리즘은 아니다 이걸 할려면 다익스트라를 n번 해야하는데..
1. 문제 24463번: 미로 (acmicpc.net) 24463번: 미로 첫 번째 줄에는 미로의 크기 $N, M$이 주어진다. $(3 \le N, M \le 2,001$, $N, M$은 홀수$)$ 두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 $N$줄에 거쳐 각 줄에는 길이가 $M$이고 .과 +만으로 이 www.acmicpc.net 입구에서 출구로 가는데, 최단 경로가 아닌 경로는 모두 @로 바꿔서 표시하는 문제 2. DFS 풀이 최단 경로가 아닌 경로를 찾는게 그냥 찾을려하면 생각보다 까다롭다 아이디어의 핵심은 이동할 수 있는 모든 위치 .을 먼저 @로 바꿔놓는다 n,m = map(int,stdin.readline().split()) maze = [list(stdin.readline()...
1. 문제 8347번: Bug (acmicpc.net) 8347번: Bug The first line of input contains two integers n and m (2 ≤ n ≤ 200 000, 0 ≤ m ≤ 500 000), separated by a single space and denoting the number of cities and the number of roads in Byteland. The cities are numbered from 1 to n; Bytetown has number www.acmicpc.net 2. 풀이 목적지까지 최단경로를 구해야하는데 문제는 홀수길이를 가지는 최단 경로를 구해야한다 그냥 사용하면 2를 답을 내는데.. 문제에서 원하는건 7로 가는 경로이다 쉬..
1. 개요 다익스트라 알고리즘은 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우"에 사용할 수 있는 최단 경로 알고리즘이다. 플로이드 워셜 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우"에 사용할 수 있는 알고리즘이다. -------------------------------------------------------------------------------------------------------- 다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하면서 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘은 또한 단계마다 "거쳐 가는 노드"를 기준으로 ..
1. 문제 1249. [S/W 문제해결 응용] 4일차 - 보급로 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2차원 배열에서 (0,0)에서 (n-1,n-1)로 가는데, 경로에 쓰이는 숫자들의 합이 최소가 되도록 갈때, 그 최솟값을 구하는 문제 2. 풀이 2차원 배열에서도 다익스트라 알고리즘을 사용할 수 있을까? 그대로 사용하면 된다 2차원 배열을 하나의 그래프로 바꿀려고 시도한 적이 있었는데 그럴 필요도 없다 다익스트라 알고리즘이 distance 배열을 무한으로 초기화하고, 출발 위치는 0으로 시작한 다음에 현재 위치에서 인접한 곳으로 이동을 해보고, 거리가 최소가 되면 di..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
