프론트 산악회🌾 프론트 산악회🌾

다익스트라

• [프로그래머스] 등산코스 정하기(JavaScript)

  Problem-Solving/Problem 2022. 9. 7. 17:34

  🍀 목차 문제 설계 구현(JavaScript) 최종 코드 훔쳐보기 문제 https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설계 코딩 테스트에서 이 문제를 마주쳤을 때는 DFS로 접근했었는데, 테스트 케이스에서 틀리고 시간 복잡도도 엄청났던 코드였다. 몇 개월 뒤 다시 보니 시작 정점에서 목적 정점까지의 최소 거리를 구하는 다익스트라알고리즘으로 접근할 수 있는 문제라고 생각했다. 그러나 몇 시간 동안 헤맸지만 테스트 케이스 3개에서 계속 시간 초..

• [최단경로] 다익스트라(Dijkstra) 알고리즘

  Problem-Solving/Algorithm 2022. 5. 4. 15:21

  🍀 목차 다익스트라 알고리즘 같은 목적을 가진 알고리즘 최단경로 알고리즘과 MST와의 차이점은 뭐지? 기본 이해 구현(JavaScript) 왜 음수 가중치에서는 사용이 불가능한 것일까? 시간 복잡도 따라서... 다익스트라 알고리즘 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 최단 경로를 찾기 위한 알고리즘 중 하나. 기본적으로 그리디 알고리즘을 바탕으로 하고 있다. 거리를 기록하며 이미 최단 경로를 구한 곳은 다시 구할 필요가 없기 때문에 다이나믹 프로그래밍으로 보기도 한다. 항상 최단 경로를 찾고 탐욕적으로 선택한다. - 그리디 이미 계산된 경로를 저장후, 그를 활용해 중복된 하위 문제를 푼다. - DP 다익스트라 알고리즘은 음수 가중치가 포함된 그래프에서는 사용할 수 없다. 이유 알아..