Sims의 문제해결 저장소

이번에도 MST 알고리즘 문제를 하나 풀어보고자 한다.https://www.acmicpc.net/problem/6497 해당문제도 MST 관련된 문제여서, 여기까지 풀어본다면 MST에 대한 개념은 충분히 잡을 수 있을 것이라 생각이 든다.해당 문제도 오리지널 MST 알고리즘을 통해서 풀 수 있는 문제다. MST 알고리즘에 관련해서 다시한번 기억해보자. 1. node, edge , value가 각각 주어지는 상황에서, 최소한의 value을 이용하여 모든 노드를 하나의 그래프에 속하도록 만드는 테스크이다.2. edge의 총 개수는 node - 1로 MST를 구성할 수 있다.3. 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과 ..

다익스트라, 벨만포드, 플로이드 워셜 ... 다 최단거리를 구하는 대표적인 알고리즘이다. 하지만 '최단거리'를 구한다는 공통적인 목표가 있지만, 각자 서로 다른 특징이 있기에 여러 알고리즘이 나눈다. 1. 다익스트라 장점 : 양의 간선이 존재할때 빠르게 최단거리를 구할 수 있다. 단점 : 음의 간선이 존재할때는 최단거리를 보장할 수 없다. 2. 벨만포드 장점 : 음의 간선이 존재할때 최단거리를 구할 수 있다. 단점 : 음의폐로가 존재할 수 있다. / 시간이 오래걸린다. 3. 플로이드 워셜 장점 : 하나의 정점에서 시작하여 다른 정점의 최단거리를 구하는 것이 아닌, 모든 정점을 기준으로 각 정점에 최단거리를 구한다. 단점 : 시간이 오래 걸린다. 위처럼 장/단점이 존재하기에 여러 최단거리 알고리즘이 있는데..

백준 1450번 (냅색문제)를 풀기위해 학습한 Meet in the middle 알고리즘을 정리하고자 한다. https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net Meet in the middle, 말 그대로 중간에서 만나자! 그럼 왜 중간에서 만나야 하며, 어떻게 중간에서 만날까? 위 문제를 바탕으로 한번 소개해 보겠다. 위 냅색 문제는 세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다. N개의 물건..