취미처럼

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프 : 정점을 두개의 그룹으로 분할하여 다른 그룹의 정점끼리는 연결되지 않는 그래프 인접한 노드 중에 자신과 같은 번호가 있다면 이분 그래프를 만들 수 없음(다시 자신번호로 연결되는 경우) StringBuilder 객체로 답을 제출했을 때 계속 출력초과가 나옴 이유는 아직 모르겠음.. import java.util.*; import java.io.*; public class Main { ..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 연결요소의 개수 : 끊기지 않고 연결된 부분의 개수 import java.util.*; import java.io.*; public class Main { // 정점 개수 static int N; // 간선 개수 static int M; static ArrayList[] list; static boolean[] visit; static..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import java.util.*; import java.io.*; public class Main { // 정점 개수 static int N; // 간선 개수 static int M; static ArrayList[] list; static boolean[] visit; static StringBuilder sb = new StringBuilder(); pu..

1. DFS(Depth - First Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 그래프는 노드와 간선으로 표현되며, 두 노드가 간선으로 연결되어 있다면 두 노드가 "인접하다"라고 표현한다. 스택이나 재귀함수로 구현 가능 모든 경우의 수를 탐색하고자 하는 미로 문제에 적합 1. 인접행렬 방식 2차원 배열로 그래프의 연결관계를 표현하는 방식 연결되지 않은 정보도 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비됨 노드 번호로 바로 접근 가능하므로 인접리스트에 비해 정보를 얻는 속도가 빠름 2. 인접리스트 방식 노드에 연결된 정보만을 리스트로 추가하는 방식 연결된 정보만 저장하기 때문에 메모리를 효율적으로 사용 인접행렬 방식에 비해 연결된 데이터..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 한 배열 리스트에 4개 이상이 쌓이면 관계가 존재하는 것 import java.util.*; import java.io.*; public class Main { static int n, m; static List[] list; static boolean[] visit; public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); // 사람 수 n = sc.nextInt(); // 친구 관계 수 ..

https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); StringBuffer sb = new StringBuffer(); Deque deque = new Linke..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new S..

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net dp[2] = 3 dp[4] = dp[2] * dp[2] + 2 dp[6] = dp[4] * dp[2] + dp[2] * 2 + 2 dp[8] = dp[6] * dp[2] + dp[4] * 2 + dp[2] * 2 + 2 +2마다 예외 모양이 존재 중복되는 부분 제거 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Sca..

https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 숫자를 제거하지 않은 경우 : 0 숫자를 제거한 경우 : 1로 나누어서 생각 특정 숫자를 제거했을 때 1. i번째 수가 처음 제거 : 이전 최대 연속 합 할당 2. i번째 수 이전 제거된 수 있음 : 현재 수는 지울 수 없으므로 이전 최대 연속합에 arr[i] 를 더함 import java.util.*; import java.io.*; public class Main { public static vo..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 왼쪽부터 증가하는 수열 길이의 최대값 + 오른쪽부터 증가하는 수열 길이의 최대값 플러스 했으므로 중복이라 -1 해주면 됨 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputSt..