https://www.acmicpc.net/problem/5904N이 10^9 개로 N번째 글자를 구한다는 것이 몇 번째 수열을 구해야 하는지 감도 안잡히고 굉장히 큰 수여서 long long으로도 담지 못한다.즉, 재귀적으로 길이가 n 이상인 수열을 구해서 n번째 문자를  찾으려 한다면 절대 풀 수 없다.조금 다르게 생각해서 n번째 글자만 알면 되므로 어떤 수열에 대해 n번째 글자를 알아내는 과정을 재귀로 생각하여야 한다. 사실 다 풀고 나서야 이렇게 명료하게 말할 수 있지만 풀 때는 다음과 같은 과정을 거쳤다.수열의 길이가 n 이상인 moo 수열 구하기 -> 구현을 다 하고 보니 n이 얼마 이상 커지면 오류k번째 moo 수열 S(k)에 대해 S(k-1)의 길이를 알면 S(k)를 알 수 있음. 그럼 길..

https://www.acmicpc.net/problem/1647예제7 121 2 31 3 23 2 12 5 23 4 47 3 65 1 51 6 26 4 16 5 34 5 36 7 4ans : 8문제의 요구사항은 다음과 같다.도시를 2개로 분할하라.분할된 2개의 도시 사이에는 간선이 존재하지 않는다.각 도시의 마을은 MST로 구성되어 있다.일단 3번 조건을 보면 MST를 구현해야하긴 하는데 어떻게 2개로 분할해야 가장 Minimum한 MST를 만들 수 있을지가 고민된다.N이 100개정도면 완전탐색으로 구현해도 될테지만 N은 10만... 완전탐색은 아니다. 만약 도시 분할 조건이 없다면 바로 MST를 구해도 된다. 그렇다면 MST를 구하는 과정에 Union-Find를 하게 되고 이 부분을 응용해서 2개의 ..

[알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Sjun-n.tistory.com  [알고리즘] 최소 스패닝 트리 - 프림 알고리즘이전 글에 이어지는 글입니다. [알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트jun-n.tistory.com크루스칼과 프림이 뭔지 모른다면 위의 두 글을 읽고오자...

예제454430 2 2 22 0 3 32 3 0 42 3 4 0출력 : 9MST 문제인데 MST 문제는 구현도 어렵지만 왜 MST인지 잘 판단해야 한다. 논을 파는 방법은 직접 논에 우물을 파거나 다른 논에서 끌어오는 방법이 있다.당장 떠오르는 방법은 그리디 하게 가장 싼 우물을 파되, 불필요하게 사이클이 생겨서는 안 되고 최소한의 개수만큼 파야 한다. 사이클이 생겨서는 안 되고 최소한의 개수만큼 파야한다는 점에서 MST를 떠올렸고 프림 알고리즘을 선택했다. 알고리즘은 다음과 같다.우물을 파는 비용을 모두 우선순위 큐에 넣는다.우선순위 큐에서 논을 하나 빼서 MST에 포함시킨다.MST에 포함된 논의 간선 중 MST가 아닌 논과 연결된 간선을 우선순위 큐에 넣는다.N개의 논에 대해 N-1개의 간선이 MST..

이전 글에 이어지는 글입니다. [알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Sjun-n.tistory.com크루스칼 알고리즘에 이어서 프림 알고리즘을 알아보자. 임의의 정점을 선택해 최소 신장 트리에 추가최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가최소 신장 트리에 V-1 개의 간선이 추가될 때까지 2번 과정을 반복방법 자체는 크루스칼과 유사..

[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Spanning이나 신장 이 단어가 너무 낯설지blog.encrypted.gg바킹독님 블로그를 참조하여 쓴 글입니다. 신장 트리란?신장 트리는 무방향 그래프의 부분 그래프들 중에서 모든 정점을 포함하는 트리이다. 사진의 왼쪽 그래프에서 오른쪽 그래프는 모두 신장 트리이다. 신장 트리라 하면 당연히 연결 그래프가 되겠고, 트리이므로 당연히 사이클이 존재해선 안된다. 최소 신장 트리는 신장 트리 중에서 간선의 합이 최소인 트리를 말한다. 최소 신장 트리는 동일한 그래프에서 여러 개 존재할..