CS(Computer Science)지식/[C++][코딩 테스트] 자료구조 및 알고리즘55 백준 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. 이전 1 ··· 4 5 6 7 8 9 10 ··· 14 다음
