0. 문제 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 1. 문제 이해 시뮬레이션 2. 제출 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { static int N, M, blank, ret; /..

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..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 서로소 집합 2. 제출 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class SWEA3289 { static int N, M; // 노드 수, 연산 수 static int[] p; // 부모 노드 저장 public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputSt..

1. 최소 신장 트리 (MST) 신장 트리 n개의 정점으로 이루어진 무향 그래프에서 n개 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 알고리즘 방식 시간 복잡도 유리한 상황 자료구조 Kruskal 일반적 O(ElogE + V) 간선이 많지 않은 그래프 간선 리스트 Prim (PQ 구현) 우선순위 큐(PQ) 사용 O(ElogV) 또는 O(ElogE) 간선이 많지 않은 그래프 인접 행렬, 인접 리스트 Prim (반복문 구현) 반복문 사용 O(V^2) 간선이 많은 밀집 그래프 인접 행렬, 인접 리스트 (E : 간선의 수, V : 정점의 수) But! PQ..

1. 서로소 집합 Disjoint-set 상호 배타 집합 서로 중복되는 원소가 없는 집합들. 표현 연결 리스트 트리 연산 집합들을 식별하기 위해서 특정 멤버를 대표자로 사용한다. make-set(x) : 집합을 생성한다. 전처리 과정에서 단 한번 실행된다. find-set(x) : x가 속한 집합을 찾아서 대표자를 반환한다. Union(x, y) : x가 속한 집합과 y가 속한 집합을 합친다. Union-Find 연산이 핵심이다. 가. 연결 리스트로 구현 같은 집합의 원소들은 하나의 연결리스트로 관리 가장 앞의 원소를 대표자로 사용 각각의 원소는 자신의 대표자와 다음 원소를 가리키는 2개의 링크를 가진다. 연산의 편의성을 위해서 tail을 사용한다. Make-Set(a) : a를 대표자(rep)이자 ta..

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..