Struggling Journey

www.acmicpc.net/problem/1707 1. 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입) 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의..

www.acmicpc.net/problem/11724 1. 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입) 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출) 첫째 줄에 연결 요소의 개수를 출력한다. 2. 풀이 import java.util.*; public class Main { // DFS를 이용해서 처리한다. public static void dfs(ArrayList[] a, boolean[] c, int x)..

www.acmicpc.net/problem/1260 1. 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입) 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출) 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를..

- 그래프는 정점과 간선으로 이루어진 자료구조의 일종 - 정점 (Node, Vertex) - 간선 (Edge) : 정점 간의 관계를 나타냄. - 경로 : 정점 A에서 B로 가는 경로 - e.g) A -> C -> D -> E -> B - 사이클 : 정점 A에서 다시 A로 돌아오는 경로 - e.g) A -> C -> B -> A - 방향 있는 그래프 - 방향 없는 그래프 (양방향 그래프) - 차수 : 정점과 연결되어 있는 간선의 개수 - 그래프 문제를 풀기 위해서는 문제에 나와있는 상황을 그래프로 모델링 후 여러가지 알고리즘을 수행해야함. - 그래프를 저장한다는 것은 간선을 저장하는 것. - 그래프를 저장하는 방법에는 2가지 방법이 있음. 인접행렬 인접리스트 - 이렇게 저장하므로써 한 정점 X와 연결된 간..

- 다이나믹 프로그래밍 -> 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 - 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있음. Overlapping Subproblem : 겹치는 부분문제 Optimal Substructure : 최적 부분구조 - 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 함. - Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같음. - 정답을 한 번 구했으면 그 값을 배열에 저장해둔다. (Memoization) - 다이나믹 프로그래밍의 구현 방식에는 두 가지 방법이 있다. Top-down : 큰 문제부터 쪼개가면서 작은 문제를 만들고 합쳐가면서 원래 문제를 푸는 방식 Bottom-up : 작은 문제들을 모아서 큰 문제..

www.acmicpc.net/problem/13398 1. 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다) 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다. 만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다. 입) 첫째 줄에 정수 n(1 ≤ n ≤ 100,..

www.acmicpc.net/problem/11054 1. 문제 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 입) 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai..

www.acmicpc.net/problem/11722 1. 문제 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 입) 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출) 첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다. 2. 풀이 import java.util.*; public class Main { public static void main(String a..