PROGRAMMING
-
(백준 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..
-
(라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)PROGRAMMING/STL 2024. 6. 5. 10:33
D 아이 제이 케이 스트라 알고리즘을 공부해보았다! 이것도 매우 유명한 알고리즘 중 하나! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220796029558&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 다익스트라 알고리즘(Dijkstra's Algorithm) (수정: 2019-08-16)이제부터 그래프에 대한 글만 엄청 쓸 겁니다. 한 11~12개 정도 예정되어 있네요. 그래프... 정말 어렵고, ...blog.naver.com 라이님 알고리즘을 보다가 gpt가 조금 고쳐준 버전으로 문제를 풀어볼까 한다!#include #include #in..
-
(백준 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"형식의 엔티티를 초기화할 수 없습니다'라는..
-
(백준 9012번 스택) 라이님 블로그 대회 알고리즘 따라잡기 15) StackPROGRAMMING/알고리즘 2024. 5. 22. 21:59
백준 9012번https://www.acmicpc.net/problem/9012 '('의 쌍은 ')'임을 기억해주자!1. '('가 들어오면 stack에 넣는다2. ')'가 들어오면 stack에 '('가 있는지 확인한다- 있으면 '('을 pop해준다- 없으면 "NO"3. 1, 2번을 반복한다. 모두 반복한 후 stack이 empty가 아니면 "NO"#include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; while (N--) { stack st; string s; cin >> s; bool flag = t..