C++66 백준 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. 백준 1766번: 문제집 (C++) 문제링크 https://www.acmicpc.net/problem/1766 백준 1766번 문제는 "문제집"이라는 제목으로 알려진 위상 정렬 문제입니다. 주어진 문제들을 풀기 위해 반드시 풀어야 하는 선행 문제들의 순서를 구하는 문제입니다. 풀이방법 이 문제는 위상 정렬 알고리즘을 사용하여 해결할 수 있습니다. 위상 정렬은 그래프의 노드들을 방향성을 유지하면서 정렬하는 알고리즘으로, 선후 관계가 있는 작업들을 순서대로 수행해야 할 때 유용하게 사용됩니다. 문제의 조건에 따르면 "문제를 풀기 전에 반드시 풀어야 하는 문제가 있다"는 조건이 있습니다. 이는 위상 정렬을 통해 문제를 풀어야 함을 의미합니다. 따라서 다음과 같은 접근 방법으로 문제를 해결할 수 있습니다. 입력으로 주어진 문제들의 선행 관계를 그.. 2024. 2. 2. 이전 1 ··· 4 5 6 7 8 9 10 ··· 17 다음
