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

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public class Main { static ..

https://www.acmicpc.net/problem/14500 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static int[][] arr; static int n, m; static boolean[][] visit; static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; static int max = Integer.MIN_VALUE; public static void main(String[] args) throws IOE..

그래프를 인접 행렬과 인접 리스트로 표현했을 때 진입/진출 차수 계산, 엣지수를 계산할 때 각각의 시간 복잡도를 C언어 코드로 구현하였다. int matrixCalculateOutDegree(GraphType* g, int v) { int i, degree = 0; for (i = 0; in; i++) { if (g->adj_mat[v][i] != 0) degree++; } return degree; // 시간 복잡도는 O(n) } int matrixCalculateInDegree(GraphType* g, int v) { int i, degree = 0; for (i = 0; i n; i++) { if (g->adj_mat[i][v] != 0) degree++; } return degree; /..

그래프 탐색 알고리즘 그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것이다. 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다. 그래프의 탐색 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 두가지가 있다. 깊이 우선 탐색(DFS: depth first search) 그래프의 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행한다. 알고리즘 자기 자신을 다시 호출하는 순환 알고리즘의 형태를 띈다. 그래프의 시작 정점에서 출발하여 시작 정점 v를 방문하였다고 표시한다. v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택하여 깊이 우선 탐색을 다시 시작한다..