Sims의 문제해결 저장소

이번에는 최소 신장 트리에 대해 공부하고 정리해보고자 한다. MST란?노드와 간선이 주어지고, 간선간 가중치가 존재했을때, 모든 노드가 간선으로 연결되어 하나의 그래프를 만드는데, 그중 가중치을 가장 낮게 하는 그래프 구조를 말한다.글로만 보면 무슨 의미인지 잘 이해할 수 없다. 아래 사진을 보자. 위처럼 노드,간선, 가중치가 제공되었을때 모든 노드를 연결하는 그래프를 그리는 방법은 아주 다양하게 그릴 수 있다.위처럼 간선을 연결하여 하나의 그래프를 그릴 수 있다.하지만, 가중치의 합은 간선의 가중치 값에 따라 서로 다르게 되고, 그래프당 가중치 합은 서로 다르게 된다. 이중 가중치 합을 가장 낮게 구성하여 모든 노드를 하나의 그래프에 연결하는것이 바로 MST - 최소신장트리 가 되는것이다. 여기서 몇가..

https://www.acmicpc.net/problem/4195 Union-Find는 크게 두가지 테스크를 진행 할 수 있다고 언급을 했다.1. Cycle 여부 확인2. 동일 그래프 소속 여부 크게 두가지를 알 수 있는데 지난번 테스크는 사이클 여부를 체크하는 문제를 풀어봤다.이번에는 동일 그래프에 속하는지 판단 + @로 조금 다른 find를 하는 문제이다. 이번 알고리즘은 두 사람의 이름이 "A B"와 같이 주어지면, A와 B는 친구 네트워크가 생성된다는 의미이다.이렇게 되면 단순하게 노드를 연결하는 방법(Union)이 된다. 즉, Union 방식으로 그래프를 생성해 나가면 된다. 하지만 한가지 다른점은 Find가 친구관계가 input으로 들어왔을때, 해당 그래프는 몇명의 친구와 연관이 있는지 바로바..

지난번 유니온파인드 개념에 대해 알아보았다. 각 노드들을 병합시켜 가리키고 있는 root-node로 업데이트를 진행시키는 방법이었다.그 후 병합된 정보를 바탕으로 find을 찾아 같은 그래프에 속해있는지, 사이클이 있는지 살펴 볼 수 있다고 하였다. 그럼 적용가능한 문제를 하나 풀어보고자 한다.https://www.acmicpc.net/problem/20040 '백준'사이트에 있는 '사이클 게임' 문제이다.문제를 간단하게 정리해보면, 노드간 간선을 하나씩 그리는 게임을 하게 되는데, 진행하다보면 어느순간에 cycle이 생기는 순간이 생길것이다. 이걸 판단해 줄 수 있는 프로그램을 만들어 달라는 것이다. 정확히 유니온 파인드 알고리즘만 알고 있으면 풀 수 있는 문제다. 이 문제의 핵심은 Find에 존재한다..

알고리즘 Union & Find 알고리즘에 관해서 정리하고자 한다.알고리즘 이름 그래도 합치고, 찾는 알고리즘이다. 대개 이 알고리즘은 노드별 연결이 되어있을때, 사이클이 존재하는가를 찾는데 많이 사용된다.   위 그림처럼 노드와 간선이 존재한다고 했을때, 해당 그래프에서 사이클이 존재하는가 아닌가를 찾아낼 수 있다.사람의 눈으로 보면 간단하게 1->2->5->1의 사이클이 보이지만 알고리즘으로는 어떻게 알게되는지 알아보자.  위와같은 과정을 거쳐 최종적으로는 모든 노드의 root는 1에 연결되어있는 결과를 얻을 수 있다. 천천히 살펴보면 1. (1-2)의 경우, 간선으로 연결되어 있어서 2의 root-node값을 1의 root-node로 바꿔준다.(여기서 1의 root-node로 변경해준 이유는 1과 ..

최단경로 알고리즘에는 다익스트라, 벨만포드, 플로이드 워셜 ... 이 가장 대표적인 알고리즘이다. 이번 포스팅은 벨만포드에 대해 알아보도록 하겠다. 이미 다익스트라 알고리즘을 알고있는 상태에서 왜 벨만포드 알고리즘이 따로 존재하고, 사용되는 것일까? 다익스트라 알고리즘와 벨만포드 알고리즘은 둘다 최단거리를 구할 수 있는 알고리즘임에 분명하다. 하지만 두 알고리즘에는 차이점이 존재한다. 다익스트라 알고리즘의 단점을 생각해보면 알 수 있다. 다익스트라 알고리즘은, 모든 간선의 길이가 양수(+)일때 최단거리를 보장한다. 혹여나 음수(-)의 간선이 존재한다면.. 최단거리를 구할 수 있지 못할 수도 있다. 벨만포드는 이러한 다익스트라의 단점을 해결할 수 있는 최단거리 알고리즘이다. 즉, 간선이 어떤 형태 ( 양수..