그래프
-
[JAVA] 백준 17471 게리맨더링알고리즘 공부/문제 풀이 2021. 10. 6. 11:28
https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net import java.util.*; import java.io.*; public class Main { static int N, total=0, min = Integer.MAX_VALUE; static int[] people; static ArrayList[] graph; public static void main(String[] args) throws Exception { BufferedReader br = new ..
-
[JAVA] 백준 1707 이분 그래프알고리즘 공부/문제 풀이 2021. 9. 28. 09:49
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static class Node { int idx; int set; public Node(int i, int s) { idx = i; set = s; } } public static void main(String[] args)throws Exception { BufferedReade..
-
[알고리즘 개념] 그래프알고리즘 공부/알고리즘 개념 2020. 9. 1. 19:40
그래프 정점(노드)와 간선(엣지)로 이루어진 자료구조 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프로 나뉜다. 그래프의 표현 인접 행렬 그래프 : 모든 정점에 대해 연결 유무를 표시한다. 직관적이며 쉽게 구현이 가능하지만, 불필요한 정보의 저장이 많으며 메모리 차지가 크다 인접 리스트 그래프 : 간선이 존재하는 곳만 표시한다. 필요한 정보만 저장하기 때문에 메모리 차지는 적지만, 구현이 어렵다. 그래프 탐색 BFS/DFS https://validming99.tistory.com/74 [알고리즘 개념] 깊이 우선 탐색(DFS)와 너비우선 탐색(BFS) 그래프 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종이다. G = (V,E) 세 가지 그림 모두 그래프이다. 트..