문제 난이도GOLD III  문제 링크https://www.acmicpc.net/problem/1238   풀이 [알고리즘] 다익스트라(Dijkstra) 알고리즘다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로,mag1c.tistory.com 위의 다익스트라 알고리즘을 사용해서 구현한 문제이다.    문제 예시를 그림으로 표현해보았다.목적지로의 최단거리만 구하면 됐던 기본적인 다익스트라 알고리즘 구현 문제에서, 반대로 2에서 각 노드의 최단 경로를 한번 더 구해주기만 하면 된다. (A -> X, X -> A) private static int[] dijkstra..

다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, 음의 가중치(음의 값)가 없어야한다.음의 가중치가 존재하게 되면, 최소 비용의 음의 무한대값이 생성될 수 있으며 그리디 알고리즘을 적용할 수 없다. 인접 행렬로 표현된 그래프의 경우 O(n^2)의 복잡도를 가지며, 우선순위 큐를 사용하여 시간복잡도를 O(m logn)까지 낮출 수 있다.  매커니즘(1) 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다 (그리디)(2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 (DP)  예시https://mag1c.tistory.com/451 [백준 1916번..

https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 뭔가 낯설지 않은 문제였는데 예전 단속 카메라문제와 유사했다 아니 똑같았다.. 1. 폐구간 별로 오름차순 정렬을 진행 2. 미사일 좌표는 개구간이라고 했기 때문에 이전 구간의 끝지점과 같을 때에도 answer++처리 개구간 (a,b)일 때, a < x < b인 구간 import java.util.*; class Solution { public int solution(int[][] targe..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해당 문제는 프로그래머스에서 탐욕법(Greedy) 카테고리 안에 있는 문제이다. 탐욕 알고리즘은 정리해 두었던 내용이다 ( 링크 ) 문제 풀이 아직 익숙치않은 Comparator 인터페이스로 이중배열인 costs의 값을 cost순으로 오름차순 했다는 것 정도다 Comparator의 사용법은 간단히 정리 해 두었다 ( 링크 ) 알고리즘 활용에 미숙해서인지 모르겠지만 내 생각엔 탐욕법이나 기타 알고리즘들을 사용해서 푼 것 같지는 않다 물론 이게 어떤 알고리즘이라고 한다면 공부를 더 깊게 해야 할 것 같다 1. 섬..