생각하는 아져씨

https://school.programmers.co.kr/learn/courses/30/lessons/49189문제 정의n개의 노드가 있고 간선에 대한 정보가 주어진다.간선은 양방향이며, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 한다.가장 멀리 떨어진 노드란? → 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다. 접근 방법가장 멀리 떨어진 노드의 개수를 구하는데 최단 경로로 이동했을 때 가장 멀리 떨어진 노드이다.따라서 가장 멀리 떨어진 노드까지 최단경로로 이동 했을 때 얼만큼 떨어져있는지?를 알아야 한다. 예를 들면 소요된 거리 또는 비용이라던가? 여기서는 간선에 대한 비용이 주어져있지 않으므로, 간선의 비용을 1로 설정해서 소요 비용을 구할 수 있다.문제에서 최단경로..

4485번: 녹색 옷 입은 애가 젤다지?https://www.acmicpc.net/problem/4485문제 정의주인공 링크는 현재 도둑루피가 가득한 N*N 크기의 동굴안에 젤 안쪽에 있다. ([0][0]에 위치)동굴의 반대편으로 가야하는데, 도둑루피를 지나면 도둑루피의 크기만큼 소지금을 잃게된다.한번에 상하좌우 1칸씩 이동할 수 있다.이 때 잃는 금액을 최소로 하여 동굴을 이동하려고 한다. 링크가 잃을 수 밖에 없는 최소 금액을 구하면 된다. 접근 방법‘잃을 수 밖에 없는 최소 금액’ = 동굴의 마지막 [N-1][N-1] 로 가는데 드는 비용을 최소화하는 경로로 가야한다.따라서 최단경로, 다익스트라로 풀 수 있다.다익스트라는 노드와 간선의 정보가 있어야 하는데, 이 문제에서는 다음과 같다.노드: 도둑루..

다익스트라(Dijkstra)다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 특정한 하나의 정점 → 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선은 포함할 수 없다. (현실세계에 사용하기 매우 적합한 알고리즘 중 하나이다.) 👉 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는?최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. 작은 문제가 큰 문제의 부분집합에 속해있다. 👉 그리디 알고리즘의 일종인 이유는?매번 ‘가장 비용이 적은 노드’를 선택하기 때문이다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 다음의 그래프에서 노드 1에서 2,3,4 ..