Hoon222y

MST 는 Minimum Spanning tree 인데 용어를 간략히 정리하자면 스패닝 트리 : 그래프에서 일부 간선을 선택해 만든 트리최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리 (트리의 정의 : 정점이 N개라면 간선은 N-1개인 경우 ) MST를 구현하는 방법에는 크게 3가지로 나누어 볼 수 있는데1) 프림 (Prim) - 정점을 중심으로 2) 크루스칼 (Kruskal) - 간선을 중심으로 3) 솔린 알고리즘 (sollin's algorithm)으로 나누어 볼 수 있다. 근데 보통은 같은 시작 복잡도를 가지고 있으므로 간단한 크루스칼을 많이 사용하는것 같다. 해당 포스팅에서는 크루스칼까지만 언급을 하도록 하겠다. 먼저 프림(Prim algorithm)의 경우1. 그래..

간간히 문제를 풀다보면 주어진 수열을 전부 검색해봐야 하는 경우가 있다. 혹은 그 다음의 배열을 구해야 하는 경우가 있는게 STL에 있는 next_permutation, 혹은 prev_permutation을 통하여 쉽게 구할수 있다. https://www.acmicpc.net/problem/10972 문제 혹은 https://www.acmicpc.net/problem/10973 해당문제가 가장 간단한 예가 될 것이다. 1234567891011121314151617181920212223#include #include #include #include using namespace std; int n;vector v;int main(){ scanf("%d" , &n); v.resize(n); for(int i=..

이번 시간에는 Set 과 MultiSet 에 대해 알아보도록 하겠다. Set과 Multiset을 사용하는 가장 큰 이유는 Binary Tree로 구현되어 있기 때문에, Search를 O(logN)에 할 수 있다는 이유로 사용을 하게 된다.하지만 차이점은 Set은 중복을 허용하지 않고 , Multiset은 중복을 허용하기 때문에 중복시 MultiSet 을 통해 구현해야 한다. 12345678910111213141516171819202122232425262728293031#include #include #include using namespace std; set s;int main(){ s.insert(10); s.insert(20); s.insert(5); s.insert(7); auto it = s.be..

LIS(Longest Increasing Subsequence) 알고리즘이란 번역하자면 최장 증가 수열이다.예를들어 1,4,6,2,3,4,9,8 이런 수열이 있다고 하면 이 수열의 LIS는 1,2,3,4,8이 될 것이다. 이러한 LIS알고리즘을 구현하는 방법은 크게 2가지가 있는데 1) O(N^2)의 방법2) O(N*logN)의 방법 으로 나누어 볼 수 있다. 먼저 O(N^2)의 방법이다. 가장 간단하고 직관적으로 알 수 있는 방법으로 자기 자신을 기준으로 자신 앞에 있는 모든 수를 다 확인해보는 방법이다. 주어진 수열에서 개수를 x는 1~x-1까지의 모든 수열중 자신보다 작은 개수의 최대값 +1을 해주는 과정이다. 또한 최장 증가 수열에 포함되는 수들을 확인하기 위해서는 해당 그림처럼 각각의 개수를 저..

https://www.acmicpc.net/problem/1201 N,M,K가 주어졌을때 1~N까지의 수중에서 최대 부분 증가 수열의 길이가 M이고, 최대 부분 감소 수열의 길이가 K인 수열을 구하는 문제이다. 먼저 적어도 M개는 증가수열이 될것이고 , K는 감소수열이 될것이며 , 최대 겹칠수 있는 경우의 수는 1가지 경우이므로 N>=M+K-1의 전제조건을 만족 해야한다.이후에 접근 방법을 생각한다면1) 1~N까지의 숫자를 오름차순으로 정렬 후 해당 배열을 M개의 그룹으로 나눈다.2) 이 때, 각 그룹에 들어있는 수의 개수는 K보다 작거나 같아야 하며 , 주어진 조건을 만족시키기 위해서 한 그룹은 K개의 수를 가지고 있어야 한다. 3) 그 후 각 그룹을 뒤집어 주면 된다. 예를들어 5 3 2 라는 입력이..