1. 문제 1504번: 특정한 최단 경로 (acmicpc.net) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1번부터 n번까지 최단 경로로 이동하고 싶은데, 특정한 정점 v1,v2를 반드시 거쳐서 최단 경로로 가고 싶다면 어떻게 해야할까? 2. 풀이 다익스트라는 어떤 정점에서 나머지 정점까지 도달하는 최단 경로를 제공하는데, 여기 중간에 어떤 정점을 거칠지는 말해주지 않는다... 근데 어떤 정점을 반드시 거쳐가게 할려면 어떻게 해야할까? 생각보다 간단하다 1번..
1. 최단경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에서 가중치의 합이 최소인 경로 최단경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 다양한 종류가 있지만 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다 예를 들어 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우", "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우" 최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 "노드"로 표현되고, 지점간 연결된 도로는 그래프에서 "간선"으로 표현된다. 2. 다익스트라 최단경로 알고리즘 그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 시작 정점에서..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return하도록 solution ..
그래프에서 최단경로를 탐색하는 알고리즘 특정 하나의 node에서 다른 모든 node로 가는 최단 경로를 알려줌 link의 가중치가 음수인 경우는 고려하지 않음 하나의 최단 거리를 그 이전까지 구했던 최단 거리 정보를 사용하여 구함 --------------------------------------------------------------------------------------------------------------------- 1. 출발노드를 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 5. 위에서 3.과 4.번을 반복 ----------..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
