0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 최소 신장 트리 (MST) 2. 제출 이 문제는 모든 노드가 서로 연결될 수 있는 완전 그래프다. 따라서 많은 간선이 생길 수 있다. (E의 최대 개수 = (V(V-1))/2)) Kruskal으로 풀기 : 시간 복잡도 O(ElogE + V) : 간선이 많은 밀집 그래프에서 불리. Prim으로 풀기 PQ로 구현한 Prim : 시간 복잡도 O(ElogE) : 간선이 많은 밀집 그래프에서 불리. 반복문으로 구현한 Prim : 시간 복잡도 O(V^2) : 밀집 그래프에 유리! 밀집 그래프에서 유리한 반복문으로 구현한 Prim 알고리즘으로 문제를..

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. 문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. 문제 이해 조합 2. 제출 2가지 방식으로 조합을 구현해 보았다. 가. 재귀 함수 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class BOJ1759_2 { sta..

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