0. 문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1. 문제 이해 부분집합 완전탐색 (DFS, BFS) 2. 제출 가. 통과 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class BOJ17471 { static int N, ret; static int[] person, parent; sta..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [알고리즘] 창용 마을 무리의 개수 0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 이건 인접리스트를 만들고 dfs로 connected component의 수를 세는 문제라 ramen4598.tistory.com c++로 푼 적 있는 문제다. java로 다시 풀어보고, Union-Find로도 풀어보았다. 1. 문제 이해 인접리스트의 완전탐색 서로소 집합 (Union-Find) 2. 제출 가. DFS import java.io.Buff..

0. 문제 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 문제 이해 인접 리스트의 완전 탐색 DFS 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringTokenizer; public class BOJ13023 { static int N, M, flag; static List[] list; static boolean[] vis; public static void..

2636. 치즈 Flood Fill DFS BFS 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 1987. 알파벳 그래프 DFS 비트마스킹 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 2623. 음악프로그램 위상 정렬 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가..

0. 문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. 문제 이해 BFS DFS 정렬 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Queue; import j..

1. 그래프 정점 간의 관계를 간선으로 표현한 것. 간선의 방향에 따라서 무향 그래프(양방향 그래프), 유향 그래프로 나뉠 수 있다. 밀집도에 따라서 완전 그래프, 밀집 그래프 그리고 희소 그래프로 나뉜다. 이 외에도 가중치 그래프, 사이클 없는 그래프 등 다양한 그래프가 존재한다. 그래프를 표현하는 방식은 크게 3가지 있다. 그래프 표현 방식 설명 시간 복잡도 (연결 여부 확인) 공간 복잡도 특징 인접 행렬 그래프의 노드들을 2차원 배열에 저장. 배열의 행과 열은 각각 그래프의 노드를 의미하며, 배열의 값은 두 노드 간의 간선 유무(또는 가중치)를 의미함. O(1) O(V^2) -구현이 쉽다. -진입 차수를 구하기 쉽다. -밀집 그래프에 유리한다. 인접 리스트 각 노드에 연결된 노드들을 리스트로 저장...

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 dfs 2. 제출 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * SWEA1861 */ public class SWEA1861 { static int[][] map; static int N, num, max; // N, 방번호, 이동할 수 있는 횟수 static int[] dy = {-1, 0, 1, 0}; static int[] dx = {0, 1,..

Tree에 대한 이론은 앞서 정리했었다. [알고리즘] 그래프 이론 기초 0. 강의 2주차 이론 [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회 이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inord... ramen4598.tistory.com 1. 이진트리 - 특성 높이 n(0부터 시작)에 위치한 노드의 최대 개수는 2^n개 높이가 n인 이진 트리가 가질 수 있는 노드의 … 최소 개수는 n+1개다. → 변질(편향) 이진트리 최대 개수는 2^(n+1)-1개다. → 포화 이진 트리 2. 이진 트리 - 구현 가. 배열 - 노드 번호를 인덱스로 사용 루트의 번호를 1로 함. n 레벨에 위치한 노드에 대하여 왼쪽에..