이번 포스팅에서는 최소 신장 트리(MST) 알고리즘을 알아보겠습니다. 최소 신장 트리는 난이도가 높은 알고리즘에 속합니다. 따라서 그래프 이론, 트리의 개념, 서로소 집합(Union-Find), 정렬, 우선순위 큐에 대한 이해가 선행되어야 합니다. 따라서 기본적인 알고리즘을 먼저 이해한 후에 공부하는 것을 권장합니다.최소 신장 트리 알고리즘은 크게 크루스칼 알고리즘과 프림 알고리즘이 있습니다. 이 글에서는 크루스칼(Kruskal's algorithm), 프림 알고리즘을 소개하고 활용에 대해서 알아보겠습니다. 1. 최소 신장 트리란?V개의 정점과 E개의 간선이 양방향 그래프 형태로 연결되어 있다고 가정해봅시다. 또한 이 그래프는 연결그래프입니다. (연결그래프란 소외된 정점이 없다는 것을 의미합니다. 즉, ..

1. 문제https://www.acmicpc.net/problem/30237코드포스 Round899 B번 문제입니다.2. 풀이차집합 계산하기U = S1 ∪ S2 ∪ S3 ∪ ... ∪ Sn 이라고 해봅시다. 먼저 우리가 구하는 S는 완전탐색으로 생각해볼 수 있습니다. S₁부터 Sn까지 모든 부분집합을 Subset이라고 하면, 모든 Subset에 대해서 U - Subset을 비교하는 방법입니다. 즉,  전체합집합과의 차집합을 비교하는 것으로 생각할 수 있습니다. 하지만 Subset을 모두 탐색하면 O(2ⁿ)이므로 시간초과가 발생합니다.따라서 전체집합에서 원소를 하나씩 빼보는 방식을 생각했습니다. x ∈ U인 임의의 x에 대해 U - x를계산하면  x를 가지고 있는 모든 Si도 빠져야 합니다. 예를 들어 t..

이번 포스팅에서는 이산수학의 한 개념으로써 조합에서 중복을 확인하는 방법이다. 알고리즘에서는 완전탐색의 경우에서 시간복잡도를 줄이는 기법으로 많이 활용된다.  예시문제: 세 사람의 심리적 거리,

1. 문제https://www.acmicpc.net/problem/1562 1562번: 계단 수첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net 2. 풀이DP적 접근비슷한 문제로 [백준 18044] 쉬운 쉬운 계단수가 있습니다. 이 문제를 먼저 이해해야 합니다. 이 문제는 기본적으로 [18044 쉬운 계단수]와 동일하게 최적 부분구조와 반복되는 부분문제를 가집니다. 하지만 쉬운 계단 수와는 다르게 "0부터 9까지 숫자가 모두 포함되어야 한다"는 조건이 추가되었습니다. 기존의 두 가지 정보를 이용한 DP 테이블로는 원하는 답을 얻을 수 없습니다. 따라서 부분문제를 해결할 때 "현재 구성된 계단수의 숫자의 조합"이라는 정보도 추가되어야..

1. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 DP적 접근 문제를 읽고 세번째까지는 구조도를 그려봤습니다. 구조를 보면 결국 완전탐색을 통해 모든 경우의 수를 찾는 문제입니다. 그런데 다음 자리로 늘어나는 과정에서 완전탐색의 시간복잡도는 O(2ⁿ)이 됩니다. 따라서 DP나 그리디를 써야 하는데 아까 그린 구조도를 살펴보면 두 가지 특징을 가집니다. 반복되는 부분문제(Overlapping Subproblems) 다음 자리로 늘어나는 과정에서 같은 부분문제들이 반복됩니다. 최적 부분구조(Optimal Substructur) 위의 부분문제들..