분류 전체보기79 백준 16398번: 행성 연결 (C++) 문제링크 https://www.acmicpc.net/problem/16398 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자. https://www.youtube.com/watch?v=4wA3bncb64E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=28 코드 #include using namespace std; #define X first #define Y second int n; vect.. 2024. 2. 3. 백준 9372번: 상근이의 여행 (C++) 문제링크 https://www.acmicpc.net/problem/1368 풀이방법 해당 문제는 신장 트리 알고리즘의 원리를 이용해서 바로 답을 구할 수 있다 신장 트리의 원리는 다음과 같다. 신장 트리란? 신장 트리(Spanning Tree)는 그래프의 최소 연결 부분 그래프 이다. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 따라서 위 이론을 문제에 적용하면 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수는 즉, N개의 노드(비행기가) 있을 때 가능한 최소의 간선 수.. 2024. 2. 3. 백준 1368번: 물대기 (C++) 문제링크 https://www.acmicpc.net/problem/1368 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 다만, 이 문제를 해결하는데 가장 중요한 점은 그래프를 목적에 맞게 변형하는 것이다. 그 이유는 직접 논에 우물을 파는 경우를 그래프로 표현할 수가 없기 때문이다. 바로 방법을 알려주면 직접 논에 우물을 파는 경우를 추가적인 노드를 만들어서 추가된 노드에 가중치를 주는 방식으로 구현할 수 있다. 아래 그림을 보면 이해가 될 것이다. 5번 노드를 추가해서 해당 노드로 직접 논에 우물.. 2024. 2. 3. 백준 1197번: 최소 스패닝 트리 (C++) 문제링크 https://www.acmicpc.net/problem/1197 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자. https://www.youtube.com/watch?v=4wA3bncb64E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=28 코드 #include using namespace std; #define X first #define Y second int v, e; ve.. 2024. 2. 2. 이전 1 ··· 4 5 6 7 8 9 10 ··· 20 다음
