전체 글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. 백준 1766번: 문제집 (C++) 문제링크 https://www.acmicpc.net/problem/1766 백준 1766번 문제는 "문제집"이라는 제목으로 알려진 위상 정렬 문제입니다. 주어진 문제들을 풀기 위해 반드시 풀어야 하는 선행 문제들의 순서를 구하는 문제입니다. 풀이방법 이 문제는 위상 정렬 알고리즘을 사용하여 해결할 수 있습니다. 위상 정렬은 그래프의 노드들을 방향성을 유지하면서 정렬하는 알고리즘으로, 선후 관계가 있는 작업들을 순서대로 수행해야 할 때 유용하게 사용됩니다. 문제의 조건에 따르면 "문제를 풀기 전에 반드시 풀어야 하는 문제가 있다"는 조건이 있습니다. 이는 위상 정렬을 통해 문제를 풀어야 함을 의미합니다. 따라서 다음과 같은 접근 방법으로 문제를 해결할 수 있습니다. 입력으로 주어진 문제들의 선행 관계를 그.. 2024. 2. 2. 백준 2623번: 음악프로그램 (C++) 문제링크 https://www.acmicpc.net/problem/2252 풀이방법 해당 문제는 바킹독님 풀이를 참조하였다. 바킹독님 풀이 설명은 아래와 같다. 이 풀이에서는 출연자 순서를 그래프로 추상화한다. 가수 번호를 순차적으로 입력 받는데, 이들을 u에서 v로 가는 간선이라 가정하여 indegree 값을 계산한다.(indegree 배열: 다른 노드에서 해당 노드로 들어오는 간선의 수) 예제 입력 중 한 줄인 3 1 4 3에서 간선의 정보를 아래와 같이 설정한다. 1 -> 4 / 4 -> 3 (1에서 4로 가는 간선 / 4에서 3으로 가는 간선) 이 경우 4와 3의 indegree를 각각 1씩 증가시킨다. indegree는 0인 정점은 자신에게 들어오는 간선이 없다는 것이므로, 해당 정점들은 현재 .. 2024. 2. 2. 백준 2252번: 줄 세우기 (C++) 문제링크 https://www.acmicpc.net/problem/2252 풀이방법 해당 문제는 기본적으로 위상 정렬 알고리즘을 이용하여 쉽게 해결하였다. 학생 A가 학생 B앞의 서야 한다는 것은 A노드가 B노드를 가르키고 있다고 생각하여 그림을 그려보면 쉽게 이해가 갈 것이다. 그렇게 그린 그래프를 바탕으로 위상 정렬 알고리즘을 구현하면 된다. 위상 정렬 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자 https://www.youtube.com/watch?v=Th-gLZUrd04&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=27 해답 코드는 다음과 같다. 코드 #include using namespace std; vector adj[32005]; int deg[.. 2024. 2. 2. 백준 1240번: 노드사이의 거리 (C++) 문제링크 https://www.acmicpc.net/problem/15681 풀이방법 해당 문제를 해결한 sequence는 다음과 같다. 기본적으로 bfs를 사용했고 bfs를 통해서 각 노드를 탐색해 나가면서 시작 노드로부터의 거리를 전부 구하면 된다. vector adj[1005]; 변수를 통해서 특정 두 노드의 번호와 거리를 입력받는다. int bfs(int start, int end) 함수를 통해서 말그대로 start지점을 트리의 루트로 생각하고 탐색을 시작하여 end 지점까지의 거리를 구하기 위해서 dist 배열을 통해서 탐색해나가는 노드와의 거리를 계산해나간다. 최종적으로 dist[end]를 return하여 입력받은 두 노드 사이의 거리를 출력한다. 코드 #include using namespa.. 2024. 2. 2. 이전 1 2 3 4 5 6 7 ··· 10 다음
