CS(Computer Science)지식/[C++][코딩 테스트] 자료구조 및 알고리즘55 백준 1753번: 최단경로 (C++) 문제링크 https://www.acmicpc.net/problem/1753 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 위 설명의 시퀀스를 바탕으로 코드를 구현하여 시작점 st로부터 특정 인덱스를 가진 노드까지 최단거리를 모두 구하여 배열에 넣는다 아래 강의를 참고하자. https://www.youtube.com/watch?v=o9BnvwgPT-o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=30 코드 #include using namespace std; #define X first #define Y second int v,e,st; // {비용, 정점 번호} vector adj[20005]; const int IN.. 2024. 2. 3. 백준 21940번: 가운데에서 만나기 (C++) 문제링크 https://www.acmicpc.net/problem/21940 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 쉽게 해결할 수 있다. 풀이 방법은 다음과 같다. 플로이드 알고리즘을 통해서 각 노드 사이의 최단 거리를 계산 해 놓는다. 우선순위 큐를 활용하여 를 넣어서 왕복 시간이 가장 적은 도시를 바로 꺼낼 수 있게 만든다. 왕복 시간이 가장 작은 것이 가장 위쪽에 존재하므로 우선 해당하는 도시의 번호를 출력한다. 왕복 시간이 가장 작은 것이 여러 개라면 해당 도시 번호까지 전부 출력한다. 위 설명의 시퀀스를 이해하고 아래 코드를 참고하자. 코드 #include using namespace std; int n, m, a, b, c, k, num, ans_min; vector friends.. 2024. 2. 3. 백준 1238번: 파티 (C++) 문제링크 https://www.acmicpc.net/problem/1238 풀이방법 해당 문제는 플로이드 알고리즘 및 다익스트라 알고리즘 모두 사용하여 해결 할 수 있다. 플로이드 알고리즘 플로이드 알고리즘을 이용하여 쉽게 해결할 수 있다. 풀이 방법은 다음과 같다. 플로이드 알고리즘을 통해서 각 노드 사이의 최단거리를 계산 해 놓는다. 단 방향이므로 특정 노드에서 특정 노드로 갈 때와 올 때 거리가 다를 수 있으므로 그 두 개를 더한 값을 MAX값과 비교하고, 더 큰 값을 다시 MAX에 저장한다. 위 설명의 시퀀스와 그래프 그림을 통해서 문제를 이해하고 아래 코드를 참고하자. 다익스트라 알고리즘 solve 함수를 만들어서 st,en인자를 받아서 st부터 en까지 최단 경로를 바로 구할 수 있게 만든다... 2024. 2. 3. 백준 11780번: 플로이드2 (C++) 문제링크 https://www.acmicpc.net/problem/11404 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 각 노드에 대한 최단 경로를 모두 구하여 한번에 출력하고 단순히 최단 거리 뿐만 아니라 특정 노드에서 노드로 이동하는 최단 경로가 어떻게 진행되는지도 출력해야 하는 문제다. 따라서 경로 복원에 필요한 nxt배열을 추가로 삽입하여 문제를 해결할 수 있다. 해당 문제에 대한 상세 풀이는 아래 바킹독님 영상을 참고하자. 또한 플로이드 알고리즘이나 경로 복원에 대한 개념이 부족하면 아래 영상을 통해 알고리즘에 대한 개념을 익히자. https://www.youtube.com/watch?v=dDDy2bEZRA8 코드 #include using namespace std; const int I.. 2024. 2. 3. 이전 1 2 3 4 5 6 7 8 ··· 14 다음
