목록알고리즘 (87)

수학과의 좌충우돌 프로그래밍

[Algorithm] 플로이드 와샬(Floyd-Warshall) 알고리즘

그래프에서 정점끼리의 최단 경로를 구하는 방법은 여러가지가 있습니다. 플로이드 와샬 알고리즘에 대해서 알아보기 전에 이에 대해서 간단히 살펴보도록 하겠습니다. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 single source and single destination shortest path problem 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 single source shortest path problem 하나의 목적지로가는 모든 최단 경로를 구하는 문제 single destination shortest path problem 모든 최단 경로를 구하는 문제 all pairs shortest path problem Floyd-Warshall 알고리즘이란? Fl..
알고리즘/이론 2019. 11. 10. 21:34
[Algorithm] 벨만포드(Bellman-Ford) 알고리즘

Bellman-Ford 알고리즘이란? Bellman-Ford 알고리즘이란, 한 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘입니다. 벨만포드 알고리즘 외에 최단거리를 구하는 알고리즘은 여럿 있지만 벨만포드는 가중치가 음수 일 때도 사용이 가능합니다. 하지만 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수일 경우에는 굳이 벨만포드 알고리즘을 사용할 필요가 없습니다. 음수간선 음수간선이 있을 경우 어떠한 문제가 생길지 알아보도록 하겠습니다. 아래 그래프에서 s 에서 출발하여 g 로 도착하는 경우를 생각해봅시다. s -> a -> b -> g 이 경우도 물론 음수간선이 존재합니다. 하지만 문제가 되는 경우는 없습니다. 3+(-4)+4 로 가중치 3으로 도착할 수 있습니다. s -> c -> d -..
알고리즘/이론 2019. 11. 7. 01:27
[Algorithm] Prim 알고리즘

Prim 알고리즘이란? Prim 알고리즘이란, 그래프에서 MST 를 찾는 알고리즘입니다. MST 가 무엇인지 모르신다면 아래 링크를 참고해주세요. Spanning Tree 와 MST [Algorithm] Spanning Tree 와 MST, 스패닝 트리와 최소 스패닝 트리 Spanning Tree 란? Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래.. ssungkang.tistory.com 이 알고리즘은 MST 를 찾기 위해서 시작 정점에서부터 단계적으로 확장해나갑니다. 특이한 점은 MST 를 찾기위해서는 간선을 선택해야 하지만 Prim 은 정점 선택을 ..
알고리즘/이론 2019. 11. 5. 22:58
[Algorithm] Kruskal 알고리즘

Kruskal 알고리즘이란? Kruskal 알고리즘이란, 그래프에서 MST 를 찾는 알고리즘입니다. MST 가 무엇인지 모르신다면 아래 링크를 참고해주세요. Spanning Tree 와 MST [Algorithm] Spanning Tree 와 MST, 스패닝 트리와 최소 스패닝 트리 Spanning Tree 란? Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래.. ssungkang.tistory.com 이 알고리즘은 MST 를 찾기 위해서 greedy 하게 접근합니다. greedy 하게 접근한다는 말은 현재 순간에 최적의 선택을 한다는 의미인데 최소 비용으..
알고리즘/이론 2019. 11. 5. 21:31
[C++] BAEKJOON 11559 Puyo Puyo

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net dfs 를 사용하여 문제를 해결하였습니다. 사실 dfs 를 이용한 접근보다 구현 쪽에 치중되어 있는 문제입니다. dfs 를 사용하여 같은 상하좌우 붙어있는 같은 색상을 찾아 해당 좌표를 v vector 에 넣어주었습니다. v vector 의 크기가 4 이상이면 삭제가 가능한 블록이므로 v_total vector 에 넣어주었습니다. 바로 삭제하지 않고 한 번에 모아서 삭제하는 이유는 동시에 깨지는 블록들의 경우에는 별도의 갯수로 세지 않기 때문입니다. v_total vector 가 비..
알고리즘/C++ 2019. 11. 4. 01:10
[C++] BAEKJOON 2573 빙산

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net dfs 를 이용하여 문제를 해결하였습니다. 매 년 마다 dfs 를 순회하여 빙산을 없애줍니다. 빙산을 한 번에 없애면 같은 년도에 먼저 없어..
알고리즘/C++ 2019. 11. 3. 21:38
[C++] BAEKJOON 1389 케빈 베이컨의 6단계 법칙

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. www.acmicpc.net bfs 를 이용하여 문제를 해결하였습니다. 인접리스트를 이용하여 각 유저간의 연결 관계를 표시합니다. for (int i=0;i> n1 >> n2..
알고리즘/C++ 2019. 11. 3. 18:43
[C++] BAEKJOON 6593 상범 빌딩

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net BFS 를 이용하여 문제를 해결하였습니다. 건물이 층, 폭, 너비 3차원이기 때문에 3차원 배열과 각 좌표를 담을 수 있는 pair3 ..
알고리즘/C++ 2019. 11. 1. 01:08
[C++] BAEKJOON 2146 다리 만들기

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net dfs 와 bfs, 두 방법을 사용하여 문제를 해결하였습니다. dfs 를 사용하여 각 섬을 구분지어주었습니다. 1110000222 1..
알고리즘/C++ 2019. 10. 31. 22:49
[C++] BAEKJOON 2468 안전 영역

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net dfs 를 사용하여 문제를 해결하였습니다. 최대 높이 maxH 측정 높이 0 부터 maxH 까지 각 경우를 고려 visited 배열을 ..
알고리즘/C++ 2019. 10. 31. 15:02
Prev 1 2 3 4 5 ··· 9 Next

티스토리툴바