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크루스칼과 프림이 뭔지 모른다면 위의 두 글을 읽고오자...

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

https://www.acmicpc.net/problem/21276문제를 보고 떠올린 방법은 다음과 같다.indegree를 측정하는데, 편하게 측정하기 위해 string -> int로 index를 가지고 있는 map list를 생성하였다.indegree가 0인 노드가 가문의 시조가 되고, 위상 정렬을 하면서 사전순으로 방문해야 한다.위상 정렬을 하면서 하나 방문하고 직계 자식을 구해야 하는데, 직계 자식은 indegree가 1이어야 한다. 즉, 현재 노드와 현재 노드와 연결된 간선을 제거했을 때 indegree가 0인 노드가 직계 자식이다.이 정도로 알고리즘을 생각해 두고 구현해 봤는데 정렬을 하면서 직계 자식을 구하고, 위상 정렬을 수행하고 하는 과정이 너무 번거롭고 시간 복잡도 상으로 비효율적이었다...

[실전 알고리즘] 0x1A강 - 위상 정렬안녕하세요, 이번 시간에는 위상 정렬을 다뤄보도록 하겠습니다. 위상 정렬이 무엇인지도 소개해드릴거고 구현과 연습 문제도 다룰 예정입니다. 위상 정렬의 본격적인 정의를 배워보기 전에 실blog.encrypted.gg바킹독님의 블로그를 보고 이해한 부분을 정리한 글입니다.위상 정렬이란 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 정렬하는 방법이다. 대표적인 예시로 교과 이수 제도가 있다. 선수 과목을 다 들어야 다음 과목을 이수할 수 있다는 것인데, 이 선수과목이 서로 겹치는 경우가 있다. 이게 실제 선수과목인데 이를 트리로 나타내보자. A -> B라면 A를 듣고 나서 B를 들어야 한다는 의미로 그려보았다.복잡한 부분만 나타내면 이렇게 될 텐데..

https://www.acmicpc.net/problem/2250예제 191 2 32 4 53 6 74 8 -15 9 106 11 127 13 -18 -1 -19 14 1510 -1 -111 16 -112 -1 -113 17 -114 -1 -115 18 -116 -1 -117 -1 1918 -1 -119 -1 -1ans :3 18depth와 col을 구하면 된다. depth는 dfs와 함께 부모의 depth + 1로 구할 수 있다. col이 문제가 되는데 col을 구하는 방법은 처음에 두 가지를 떠올렸다.각 레벨의 가장 왼쪽 노드와 가장 오른쪽 노드 사이의 노드 개수 구하기 -> widthdp로 푸는데, dp [k] = k 레벨의 width로 두고 dp [k+1] = dp [k] + k 레벨의 가장 왼쪽..