![]()
- 개요다익스트라 알고리즘은 '그래프의 한 정점에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘' 이다. (최단 경로 문제 | Shortest Path Problem) 시작점 부터 순차적으로 최단 거리를 구하는 방식으로 진행된다. - 예시를 이용한 알고리즘 설명위와 같은 경로맵이 있다.시작점은 "정점 4" 이다. '정점 방문 여부' 와 '각 정점 별 최단 거리' 테이블을 통해 순차적으로 최단 거리를 구한다.시작점인 '정점 4' 는 이미 방문한 것으로 표시하고, 시작점이기 때문에 최단 거리는 0 으로 설정한다. [탐색 정점 : 정점 4]정점 4 와 인접한 정점 2, 1, 6 에 대해 최단 거리를 갱신한다. [탐색 정점 : 정점 1]미방문 상태인 정점 (1, 2, 3, 5, 6) 중 출발점으로 부터 ..
![]()
[백준 1753번 최단경로]https://www.acmicpc.net/problem/1753[접근 방법]'그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘' 인 다익스트라 알고리즘 반복 학습을 위해 이 문제를 선택하였다.다익스트라 알고리즘을 이용하여 문제를 해결하고자 한다. 문제를 해결하는 동안 고려할 사항은 다음과 같았다.1. 다익스트라 알고리즘을 사용한다.2. 2차원 배열을 이용한다면 '메모리 초과' 문제가 발생한다.3. 이를 해결하기 위해, 우선순위 큐를 사용한다. [JAVA 코드 - 2차원 배열 -> "메모리 초과"]import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;impor..
![]()
[ 2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금 ]https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [ 접근 방법 ]최소 금액(Cost)을 구하는 문제이다.다익스트라 알고리즘을 사용하여 문제를 해결하였다. 기존 다익스트라 알고리즘 문제에서 '합승' 이라는 새로운 조건이 추가 되었다.이 부분은 - '시작점' ~ '합승 목적지' (StartToK)- 'A 목적지' ~ '합승 목적지' (AToK) - 'B 목적지' ~ '합승 목..
