📁 최단거리문제 보통 시작노드부터 도착노드까지의 최단경로를 구하는 형식의 문제이다. MST에서 알 수 있듯이 최단경로는 절대 사이클을 포함하지 않는다. 최단거리 문제는 가중치 유무에 따라, 가중치가 있을 경우엔 가중치의 음양에 따라 알맞은 알고리즘을 사용한다. 양의 가중치만 있을 때 : 다익스트라 알고리즘(Dijkstra's Algorithm) 음의 가중치만 있을 때 : 벨만포드 알고리즘(Bellman-Ford Algorithm) n 대 n의 최단거리를 모두 구하고 싶을 때 : 플로이드와샬 알고리즘(Floyd-Warshall Algorithm) 📁 다익스트라 알고리즘 Dijkstra's Algorithm 에지의 가중치가 양수일 때 사용한다. 음수 가중치를 고려하지 않으므로 가중치의 합이 최단거리를 좌우한..
📂 최소신장트리 (Minimum Spanning Tree) 신장트리 : 그래프 G의 노드 V를 모두 포함하는 E에 속하는 에지를 사용해 만든 트리 최소신장트리 : 가중그래프 G의 신장트리 중에서 트리에 속한 가중치의 합을 최소로 하는 신장 트리 최소신장트리를 만드는 2가지 방법 : Prim's Algorithm, Kruskal's Algorithm 최소신장트리의 간선 개수는 (정점의 수 - 1) 이다. (N-1개의 간선으로 연결되어 있으면 필연적으로 모든 노드가 연결된다) 간선들의 가중치 합이 최소인 경우 서로 다른 최소신장트리가 하나 이상 있을 수 있다. 📂 크루스칼 알고리즘 (Kruskal's Algorithm) 가중치가 가장 작은 간선부터 차례대로 간선을 선택해 나가는 방법으로, 탐욕적(greedy..
🧨 백준 1707번 - 이분 그래프 문제 난이도 : 골드4 (낮은 정답률에는 이유가 있다) 문제 링크 : www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 🧨 알고리즘 선택 및 C++ 코드 메모리초과, 런타임에러(Segfault, OutofBounds)에 틀렸습..
🧨 백준 10026번 적록색약 문제 난이도 : 골드5 문제 링크 : www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 유기농배추 문제와 크게 다를 거 없고, 대신 0과 1의 이분법이 아니라 0, R, G, B를 구분해야 하는 정도가 조금 더 난이도 있다고 볼 수 있다. 여태까지 그래프 관련 문제들 계속 BFS로 구현했어서 이번에는 재귀를 사용한 DFS로 구현했다. 조금 어렵다고 생각했는데 막상 짜보니 별거 아닌 거 같다..
🧨 백준 1012번 - 유기농 배추 문제 난이도 : 실버2 문제 링크 : www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 2178번 미로탐색 문제와 비슷하게 2차원 좌표를 이용해 위치 이동을 해야하므로 상하좌우 dx, dy 배열을 사용했다. 재귀를 사용하는 DFS는 뭔가 거부감이 있어서 일단 BFS로 구현했다. (DFS로 짜도 상관없는 거 같다) 처음에 대체 어디에 배추가 있는지 알아야 지렁이를 놓든 말든 할거 아닌가 싶어서 이를 표시해..
🧨 백준 2178번 미로탐색 문제 난이도 : 실버1 문제 링크 : www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 처음 문제를 봤을 땐 좀 낯설었다. 뭔가 너비우선탐색을 사용하는 거 같은데 어떻게 사용할지 한참 고민했다. 미로에서 칸 이동을 해야 하므로 어쩔 수 없이 상하좌우 대소비교가 들어가야했다. 그래프 탐색을 이용한 문제는 대부분 원하는 값만을 구하려고 하면 어렵게 느껴진다. 갈 수 있는 모든 칸에 대해 지나야 하는 최소 칸 수를 계산해야 (N, M)..
🧨 백준 2644번 - 촌수계산 문제 난이도 : 실버2 문제 링크 : www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 DFS를 쓰는 줄 알았는데 코드에 감이 안 잡혀서 더 생각해봤더니 BFS를 활용한 문제였다. 너비우선탐색으로 깊이를 카운팅했다. 정점(첫 노드)에서 내가 원하는 사람까지 가는 깊이만 카운팅하려 했는데 조건문 쓰는 게 더 복잡해서 그냥 다 계산했다. 입력받은 start 사람에서 모든 사람들까지의 ..
그래프 그래프 G = (V, E) 이때 V는 노드, E는 에지이다. 에지 E는 V * V 의 부분집합이다 (즉 노드와 노드를 연결하는 모든 쌍의 부분집합) 유향그래프 vs 무향그래프 : 에지의 방향성에 따라 유향그래프 : (i, j) ≠ (j, i) 무향그래프 : (i, j) = (j, i) 양방향 유향그래프 가중그래프 G = (V, E, W) 가중그래프(weighted graph)는 에지마다 가중치 W를 가진다 보통 사람은 그래프를 손으로 그려 시각적으로 보는 걸 선호하지만, 컴퓨터로는 2차원 행렬 또는 리스트로 표현한다. 그래프의 탐색 자체는 그리 어렵지 않다. 효율적인 탐색을 위해 깊이우선, 너비우선 탐색으로 분류할 수 있다. 그리 어렵지 않은 내용이므로 그림은 과감히 생략ㅎ 깊이우선탐색 (Dept..
