최단 경로 탐색3 [Programmers] 배달 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 1번 마을에서부터 시작하여, 1, 2, $\cdots, N$ 번 마을까지의 최단 경로를 모두 구하여 $K$ 시간보다 적게 걸리는 마을의 수를 카운트하여 문제를 해결하기 위해 플로이드-워셜(Floyd-Warshall) 알고리즘을 활용하여 문제를 해결하고자 하였다. 구현 $i, j \space (1 \le i, j \le N)$ 번 마을 사이의 최단 경로로 이동할 때의 가중치의 .. 2023. 12. 21. [Baekjoon] 11404번: 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 해결 과정 착안 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)에 따라 문제에서 요구하는 도시 간 거리를 계산하고자 하였다. 음수 가중치 간선이 없기 때문에 일반적인 방법으로 문제를 해결하고자 하였다. 구현 알고리즘을 구현함에 있어서, 삼중 반복문의 루프 변수 배치 순서 및 시작 도시와 도착 도시 사이의 연결이 없는 경우를 0으로 표시하는 부분에 유의하여 프로그래밍 하였.. 2023. 7. 25. [Baekjoon] 1916번: 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 해결 과정 착안 음의 가중치 간선이 존재하지 않으며 방향이 있는 그래프에 대한 최단 경로 탐색을 요구하는 문제이므로, 최단 경로 탐색 알고리즘 중 하나인 데이크스트라 알고리즘(Dijkstra's algorithm)을 사용하여 문제를 해결하고자 했다. 구현 데이크스트라 알고리즘을 정상적으로 구현했음에도 불구하고 시간 초과가 발생하여 한참 고민하다가 질문 게시판.. 2023. 7. 7. 이전 1 다음
