2021/03/11

[Python] 프로그래머스 지형 이동

문제 programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 계속 틀려서 다른 사람의 풀이를 보고 푼 문제이다. 어떻게 이런생각을 떠올리지...? heap을 사용해서 풀었다. 상,하,좌,우 칸 중에 방문하지 않은 칸과의 길이가 height보다 크다면 heap에 차이와 점을 기록한다. height보다 작다면 0과 점을 기록한다. 이를 이용해서 min heap으로..

[Python] 프로그래머스 합승 택시 요금

문제에 대한 자세한 설명은 아래 링크 참조 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr Dijkstra 알고리즘을 사용해서 풀었다. (최단거리..

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

다익스트라 알고리즘은 A에서 B까지의 최단 경로를 찾고자 할 때 사용한다. 먼저, 알고리즘을 직관적으로 살펴보자 다음과 같은 그래프에서 A->C로 가고자 할 때 최단 경로를 구해보자. 우선 출발지로부터 인접한 노드들과의 거리를 갱신한다. (빨간색) 그 다음 노드로 이동한다. 해당 노드에서 인접한 노드들 중에 방문하지 않은 노드들 과의 거리를 갱신한다. 다음과 같이 D의 거리가 5에서 3으로 갱신 되었다. (최단 거리) C가 5에서 4로 갱신되었다. 현재 방문한 노드가 도착지라면 알고리즘을 종료한다. 그림처럼 A->C의 최단경로는 4가 된다. 위와 같이 동작하는 알고리즘이 다익스트라 알고리즘이다. 📌 Rule 1. 출발 노드로부터 인접한 노드들 사이의 거리를 갱신한다. 2. 다음 노드로 방문하여 인접 노드..