전체 글79 백준 1504번: 특정한 최단 경로 (C++) 문제링크 https://www.acmicpc.net/problem/1504 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 우선 solve라는 함수를 만들고 int st, int en을 추가해서 st 부터 en까지 최단 거리 값을 알려주는 함수를 만든다. 1~N까지의 경로 중에 v1과 v2를 반드시 지나는 경우는 딱 두 가지 케이스가 존재한다. (~~~ 중간에 다른 경로를 의미한다. 중간에 다른 경로가 없을 수도 있다.) (1) 1~~~V1을 지나고 V1부터 ~~~ V2를 거쳐서 V2~~~n에 도달하는 방법 (2) 1~~~V2를 지나고 V2부터 ~~~ V1을 거쳐서 V1~~~n에 도달하는 방법 위 두 케이스만 존재한다. 두 케이스에서 작은 값을 최종 결과 .. 2024. 2. 3. 백준 11779번: 최소비용 구하기 2 (C++) 문제링크 https://www.acmicpc.net/problem/11779 풀이방법 해당 문제는 다익스트라 알고리즘을 이용하여 해결할 수 있다. 풀이 방법은 다음과 같다. 위 설명의 시퀀스를 바탕으로 코드를 구현하여 시작점 st로부터 특정 인덱스를 가진 노드까지 최단거리를 모두 구한다. 추가적으로 위 그림처럼 시작 지점부터 끝 지점 까지 경로를 찾기 위해서 pre 배열을 선언해서 pre배열을 채우고 해당 테이블을 이용해서 경로까지 출력한다. 문제 풀이는 아래 바킹독님 강의 영상을 참고하자. https://www.youtube.com/watch?v=o9BnvwgPT-o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=30 코드 #include using namespace.. 2024. 2. 3. 백준 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. 백준 11404번: 플로이드 (C++) 문제링크 https://www.acmicpc.net/problem/11404 풀이방법 해당 문제는 플로이드 알고리즘을 이용하여 각 노드에 대한 최단 경로를 모두 구하여 한번에 출력하는 문제이다. 해당 문제에 대한 상세 풀이나 플로이드 알고리즘에 대한 이해가 필요하면 아래 영상을 참고하자. https://www.youtube.com/watch?v=dDDy2bEZRA8 코드 #include using namespace std; const int INF = 0x3f3f3f3f; int d[105][105]; int n, m; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i > a >> b >> c; d[a].. 2024. 2. 3. 백준 1647번: 도시 분할 계획 (C++) 문제링크 https://www.acmicpc.net/problem/16398 풀이방법 해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자. https://www.youtube.com/watch?v=4wA3bncb64E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=28 우선 마을 하나하나를 그래프의 노드라고 생각한다. 그 상태로 최소 신장 트리를 만든다. 그럼 모든 마을이 연결되어있고 가중치의 합이 최소인.. 2024. 2. 3. 이전 1 2 3 4 5 6 ··· 10 다음
