Coding Story

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static int[][] arr; public static boolean[] visited; public static int n; public s..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parse..

선택 정렬 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 반복한다. 1. 입력 배열에서 최솟값을 발견한 다음, 이 최솟값을 배열의 첫번째 요소와 교환한다. 2. 첫번째 요소를 제외한 나머지 요소들 중에 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 3. 이 절차를 숫자 개수-1 만큼 되풀이 한다. #define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t)) void selection_sort(int list[], int n) { int i, j, least, tmp; for (i = 0; i < n - 1; i++) { least = i; // 최솟값 인덱스 for (j = i + 1; j < n; j++) { // 인덱스 i+..

Dijkstra 최단 경로 알고리즘 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘 n개의 정점이 있다면 O(n^2)의 시간복잡도를 가진다. #include #include #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 100 #define INF 1000L typedef struct GraphType { int n; // 정점의 개수 int weight[MAX_VERTICES][MAX_VERTICES]; }GraphType; int distance[MAX_VERTICES]; // 시작 정점으로부터의 최단경로 거리 int found[MAX_VERTICES]; // 방문한 정점 표시 // 선택되지 않은 정점 중 distance 값이 가..

신장 트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 모든 정점들이 연결되어 있고 사이클을 포함하면 안된다. 그래프의 최소(간선의 수가 가장 작은) 연결 부분 그래프 n개의 가지는 그래프는 최소한 (n-1)개의 간선을 가진다. 간선에 비용을 붙여 링크의 구축 비용까지를 고려해 최소 비용의 신장 트리를 선택해야함 통신 네트워크 구축에 많이 사용 최소 비용 신장 트리(MST) 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결 신장 트리 중에서 사용된 간선들이 가중치 합이 최소인 신장 트리 Kruskal, Prim 알고리즘이 대표적 반드시 n-1 개의 간선만 사용하고, 사이클이 포함되어서는 안된다. Kruskal 의 MST 알고리즘 탐욕적인 방법(greedy metho..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { public static boolean[] visited; public static int[] arr; public static int..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] arr; static boolean[] visited; stati..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int[] arr, nums; public static boolean[] visited; public..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] arr, nums; static boolean[] visited; static int n, result = 0; public s..

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ static int n; static int[] arr; static boolean[] visited; public static void dfs(int cnt){ if(cnt == n){ for(int x : arr){ System.out.print(x+" "); } System.out.p..