PROGRAMMING/알고리즘
-
(백준 1956번 운동) (라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)PROGRAMMING/알고리즘 2024. 6. 13. 11:23
최단거리 알고리즘 복습 2탄 - 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘이 제일 심플하다..ㅎㅎ 백준 1956번https://www.acmicpc.net/problem/1956 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int arr[400][400]; int V, E; cin >> V >> E; for (int i = 0; i > a >> b >> c; arr[a - 1][b - 1] = c; } for (int k = 0; k
-
(백준 1238번 파티) 라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)PROGRAMMING/알고리즘 2024. 6. 13. 10:59
최단거리 알고리즘 복습 1탄 - 다익스트라 알고리즘 백준 1238번https://www.acmicpc.net/problem/1238 풀이에 중복이 있어 제거하는 풀이를 chatgpt에게 부탁했는데, 두번째 풀이도 바로 챗gpt 풀이다.(gpt가 틀렸길래 디버깅 좀 했쑴ㅎㅎ) 첫번째 풀이다익스트라 알고리즘을 사용해서 all node -> X로 가는 최단 경로를 구한 후(N-1번의 다익스트라 알고리즘 사용) X -> all node로 가는 최단 경로를 구했다.(1번의 다익스트라 알고리즘 사용) 다익스트라 함수를 구현하는데 있어 겹치는 부분이 많아 아쉬운 풀이 #include #include #include #include #include #include using namespace std;typedef pa..
-
(백준 9205번 맥주 마시면서 걸어가기) (라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)PROGRAMMING/알고리즘 2024. 6. 12. 11:15
플로이드 와샬 알고리즘 문제인지 모르고 봤다면 푸는게 좀 난해했을 것 같은 문제다..! 백준 9205번https://www.acmicpc.net/problem/9205 집과 n개의 편의점, 그리고 축제 장소가 2차원 공간에 있지만 하나의 그래프 노드라고 생각하면 문제가 쉽게 풀린다!두 점 사이의 맨해튼 거리가 1000이 넘으면 맥주가 부족해 도착하지 못하므로 1000을 기준으로 각 노드들(집, 편의점, 축제 장소)가 이어져 있는지를 우선 dist matrix에 0과 1을 이용해 표시한다. 다음 플로이드 마샬 알고리즘을 이용해 집에서 축제 장소까지 연결된 루트가 있는지 확인해주면 끝! 대칭(symmetric matrix)이기 때문에 distance matrix와 플로이드 와샬 알고리즘을 upper tria..
-
(백준 11403번 경로찾기 / 백준 1389번 케빈 베이컨의 6단계 법칙) (라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)PROGRAMMING/알고리즘 2024. 6. 12. 11:03
직관적인 플로이드 와샬 알고리즘 같은 알고리즘만 있으면 얼마나 좋을까..ㅎㅎ 플로이드 와샬 알고리즘만 있으면 쉽게 풀리는 두 개의 문제를 풀어보았다. 백준 11403번https://www.acmicpc.net/problem/11403#include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; bool dist[100][100]; for (int i = 0; i > dist[i][j]; } } for (int k = 0; k 백준 1389번https://www.acmicpc.net/problem/1389★ min_sum의 최대값..
-
(라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)PROGRAMMING/알고리즘 2024. 6. 12. 09:27
그래프 거리 구하는 알고리즘 세번째! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220797649276&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)마지막으로 알려드릴 최단경로 알고리즘입니다. 참 많기도 하죠. 이번엔 플로이드 와샬 알고리즘(Floyd-W...blog.naver.com 모든 간선을 다 확인하는 가장 비싸지만 가장 확실한 알고리즘으로 시간복잡도가 $O(V^3)$이다.알고리즘은 매우 간단하다! 행렬을 고등학교때 배운 사람이라면 이미 아는 내용!! 라이님 풀이를 gp..
-
(라이님 블로그 대회 알고리즘 따라잡기 17) 벨만 포드 알고리즘(Bellman-Ford Algorithm)PROGRAMMING/알고리즘 2024. 6. 12. 09:23
https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220796963742&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 벨만 포드 알고리즘(Bellman-Ford Algorithm) (수정: 2020-07-10)이어서 소개해드릴 것은 또다른 최단경로 알고리즘입니다. 벨만 포드 알고리즘(Bellman-Ford algorithm)...blog.naver.com 다익스트라 알고리즘에 이어 거리 구하는 알고리즘 2탄! Bellman-Ford Algorithm은 음의 거리에 대해서도 사용이 가능하기 때문에 타임머신이나 웜홀 문제에서 유용하다! 시간복잡도는 O(V..
-
(백준 1916번 최소비용 구하기 / 백준 4485번 녹색 옷 입은 애가 젤다지?) 라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)PROGRAMMING/알고리즘 2024. 6. 5. 17:09
백준 1916번https://www.acmicpc.net/problem/1916 #include #include #include #include using namespace std;typedef pair P;void dijkstra(int V, int start, int end, const vector>& adj) { vector dist(V, INT_MAX); priority_queue, greater> pq; dist[start] = 0; pq.emplace(0, start); while (!pq.empty()) { int curr_dist = pq.top().first; int curr = pq.top().second; pq.pop(); if (dist[curr] dist[curr] + w..
-
(백준 1935번 후위 표기식2) 라이님 블로그 대회 알고리즘 따라잡기 15) StackPROGRAMMING/알고리즘 2024. 5. 25. 21:41
오늘은 후위 표기식 2를 풀어보았다.간단한 문제이지만, 풀면서 은근 배우는 점이 많았다! 백준 1935번https://www.acmicpc.net/problem/1935 풀이에 대한 간단한 설명이 라이님 블로그에 있어서 참고해서 풀었다.풀이 자체는 어렵지 않았는데, 몇 가지 헷갈렸던 부분이 있어 정리한다. 1. stack의 pop() methodstack의 pop() method는 따로 top 원소를 반환하지 않는다!그래서 top원소를 빼내서 알고 싶다면 stack.top(); stack.pop();이렇게 두 개의 method를 한 번에 진행해야 한다. 그렇지 않고, int temp = stack.pop();을 호출하면 'void 형식의 값을 사용하여 "int"형식의 엔티티를 초기화할 수 없습니다'라는..