밀린 백준포스팅 목록 포스팅하며 복습해봐야 할 백준문제 목록. 1098911495145031978294156221011660327481002140614751931 많이 밀렸구만.. 더보기 백준 1516 : 게임 개발 https://www.acmicpc.net/problem/1516 순차적으로 진행해야 하는 DAG그래프를 다룰 때 위상정렬을 생각할 수 있다. 건물을 짓는데 필요한 건설시간과 건물을 짓기 이전에 걸리는 건설시간을 분리했다. 위상정렬을 할때 건물을 짓기 이전에 걸리는 시간이 최대여야 하기 때문이다. 예를들어 a를 짓기위해 b 와 c가 지어져야 하는데 b는 짓는데 총합 10초이고 c는 총합 20초라면a건설을 시작할 수 있는 시기는 c가 완료된 20초에나 가능한 것이다. 이를 유의해서 건물짓기 이전에 걸리는 건설시간을 MAX로 갱신시켜주어야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3.. 더보기 백준 9205 : 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 매우 간단한 BFS, DFS, 다익스트라, 플로이드-와샬 등으로 다양한 방법으로 풀 수 있다. 1. BFS나 DFS로 탐색할 경우 탐색이 끝난 후 visited[] 배열에 도착지가 true인가 false인가 확인하면 된다.2. 다익스트라로 탐색할 경우 탐색이 끝난 후 도착지 정점의 dist가 INF인지 아닌지 확인하면 된다.3. 플로이드-와샬로 탐색할 경우 탐색이 끝난 후 matrix[출발지][도착지]가 INF인지 아닌지 확인하면 된다. 기본적으로 1000m 이내에 있으면 간선으로 연결시켜주고 그 외의 경우에는 연결할 필요가 없다.또한 간선에 대한 가중치도 필요가 없다. 왜냐하면 콜라를 리필하는데 대한 비용같은 것은 염두에 두지 않기 때문.. 더보기 백준 10159 : 저울 https://www.acmicpc.net/problem/10159 백준 1613 : 역사 문제와 원리가 동일한 플로이드-와샬 알고리즘이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44#include #define MAX 101 #define INF 1000000000 using namespace std; int n, m; int matrix[MAX][MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1; i a >> b.. 더보기 백준 1613 : 역사 https://www.acmicpc.net/problem/1613 얼핏보면 위상정렬 문제같다. 선후관계가 명확하고 그래프가 DAG이기 때문이다.그러나 아예 연결이 안되어 있는 그래프 즉 선후관계가 정해져 있지 않은 그래프를 처리하는게 Topological Sort 로는 애매해보였다. 선후관계를 단방향 그래프로 생각했을 때 전체 그래프의 연결여부를 확인 할 수 있는게 또 하나 있다. 바로, 플로이드-와샬 알고리즘, n=400 이라 충분히 n^3 이 가능해서 생각해보았다. 플로이드 와샬을 썼을때 2차원배열에서 i->j로 갈때 INF가 떴다는 것은 i 에서 j 로 갈 수 없다는 것이다.이때, 만약 j->i 가 INF가 아니라 다른 숫자라면 j->i로는 갈 수 있고 따라서 j 가 i 보다 먼저 일어난 선후관계를.. 더보기 백준 11404 : 플로이드 https://www.acmicpc.net/problem/11404 제목부터 플로이드다플로이드-와샬 알고리즘을 알고있다면 그냥 n^3 한다음에2차원배열을 출력하면 끝. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44#include #define MAX 101 #define INF 1000000000 using namespace std; int matrix[MAX][MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for(int .. 더보기 백준 2606 : 바이러스 https://www.acmicpc.net/problem/2606 간단하다. BFS로 풀어도 되고 DFS 로 풀어도 되고 심지어 플로이드-와샬을 써도 된다.그냥 단순히 그래프의 연결문제를 탐색하는 것. 숫자만 세는 것이므로BFS 나 DFS로 visited = true; 라고 새롭게 방문을 하는 순간count++ 해주면 된다. 1. 큐를 이용한 BFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38#include #include #define MAX 101 using namespace std; int matrix[MAX][MAX]; bool visited[MAX]; i.. 더보기 백준 2660 : 회장뽑기 https://www.acmicpc.net/problem/2660 가장 기본적인 플로이드-와샬 알고리즘 문제이다.다익스트라는 한 점을 기준으로 해서 다른 점들과의 최소비용거리를 계산하지만플로이드-와샬 같은경우 모든 점과 점사이의 경로를 구한다.모든 점과 점사이의 최소비용거리 데이터는 2차원 배열에 저장이 되며 시간복잡도는 n^3 이다. 플로이드-와샬 알고리즘의 경우 동적계획법(DP)의 형태를 가진다.우선 모든 2차원 배열에 저장된 경로를 INF으로 선언하고(자기자신으로 가는경우 i==j 는 0)각 i -> j 로 갈 때 가중치를 저장해준다. ( i -> j 로 가는 경로가 없을때 INF 선언) 현재 정점에서 목적지로 갈때 직접 가는 것보다 다른 점을 거쳐가는 것이 더 빠른 경우를 찾는것 이 핵심이다.간단.. 더보기 이전 1 2 3 4 ··· 6 다음