wonseok.log wonseok.log

이 글은 (https://m.blog.naver.com/ndb796/221234424646) 블로그 글을 참고하여 작성하였습니다. 다익스트라 알고리즘 다이나믹 프로그래밍(DP)을 활용한 대표적인 최단 경로 탐색 알고리즘입니다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 이전에 구했던 최단 거리를 사용한다는 특징때문에 다이나믹 프로그램을 활용한다고 볼 수 있습니다. 출발 노드를 설정합니다. 출발 노드에서 각 노드까지 가는 최소 비용을 배열을 만들어 저장합니다. 방문하지 않는 노드 중에서 가장 비용이 적은 노드를 선택합니다. 해당 노드를 거쳐서 각 노드로 가는 경우까지 비교하여 최소 비용을 갱신합니다. 위 과정에서 3~4번 반복합니다. 여기서 3번 과정에서 코딩 구현 시 배열을 완전 탐색해서 최소 ..

이 글은 (https://m.blog.naver.com/ndb796/221230994142) 블로그를 보고 작성하였습니다. Kruskal Algorithm 크루스칼 알고리즘은 연결된 그래프에서 가장 최소 비용을 사용하여 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 다른 말로는 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있습니다. 프로그래머스 (https://programmers.co.kr/learn/courses/30/lessons/42861?language=cpp) 이 문제를 예시로 들어 설명하도록 하겠습니다. 크루스칼 알고리즘을 쓰기 위한 핵심 개념은 크게 3가지가 존재합니다. 최소 비용 순서에 맞게 간선들을 정렬시킵니다. 정렬된 순서에 맞게 그래프에 포함시키는데 포함시..

이 글은 (https://m.blog.naver.com/ndb796/221230967614) 블로그를 보고 작성하였습니다. Union Find 유니온 파인드는 대표적인 그래프 알고리즘입니다. 여러 개의 노드가 있을 때 두 가지의 노드 하나의 그래프로 연결되어 있는지 판별하는 알고리즘입니다. 먼저, 배열을 만들어서 해당 노드번호로 부모 노드번호를 가리키게 합니다. 처음에는 당연히 연결된 그래프가 없기 때문에 각자 자신의 노드번호를 가리키게 됩니다. 1과 2를 연결하게 되면 합친다는 뜻에서 Union이라고 부르고 노드번호 중 작은 노드번호가 부모노드가 됩니다. 이렇게만 구현할 경우 2와 3이 연결하게 되면 부모노드가 2가 되는데 1과 3이 같은 그래프로 연결되어 있는지는 알 수가 없습니다. 따라서 재귀함수를..