1. 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로. 2. Dijkstra 알고리즘 음의 가중치가 없는 그래프의 한 정점에서 다른 정점들까지의 최단 거리 비용을 구하는 알고리즘. 시간 복잡도 : 반복문으로 구현 시 O(V^2) : PQ로 구현 시 O(ElogE) 가. 반복문으로 구현 시간 복잡도 : 반복문으로 구현 시 O(V^2) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class dijkstraTest { static class Node { in..

0. 문제 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 1. 문제 이해 순열 시뮬레이션 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 BOJ17281 { static int N, cur, ret; static int[..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 최소 신장 트리 (MST) Kruskal Prim 2. 제출 MST를 구하는 문제다. 주어지는 가중치가 크기 때문에 overflow를 주의하면서 풀면 된다. 가. Kruskal import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class SWEA3124 { static int V, E; static long ret; // int overflow 발생 sta..

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