물음표 살인마

이분그래프란? 위의 그림과 같이 A(검정)/B(회색)로 나눌 수 있는 그래프 A에 포함된 정점끼리 연결된 간선이 없음 B에 포함된 정점끼리 연결된 간선이 없음 A-B 서로를 연결하는 간선만 존재 EX. 수강신청 시 학생과 과목을 연결, 소유물 표현 시 사람과 사물을 연결할 때 등 쓰인다 ----- 이분그래프 관련 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net import java.util.ArrayList; import java.util..

연결요소란? Connected Component 1~6까지 모든 요소를 하나의 그래프라고 쳤을 때 위의 그림처럼 나누어져 있는 경우가 있다. 이렇게 나누어진 각각의 그래프를 연결 요소라고 한다. 연결 요소의 조건 1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다. 2. 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다. 즉 위의 그림은 2개의 연결 요소로 구성된 하나의 그래프이다. 참고로 연결 요소가 1개인 그래프는 연결 그래프라고 한다. ----- 백준 11724를 통한 연결 요소 실습 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ ..

그래프 탐색의 목적: 임의의 정점에서 시작하여 연결되어 있는 모든 정점을 한 번씩 방문하는 것. 탐색 방법은 크게 2가지, DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)으로 나뉜다. 1. 깊이 우선 탐색(Depth First Search) 스택을 이용해 갈 수 있는 만큼 최대한 많이 간다. 더이상 갈 수 없으면 이전 정점으로 돌아간다. 재귀 호출을 이용해 구현 가능 void dfs(int x){ check[x] = true; for(int i = 0; i < a[x].size(); i++){ if(!checked[y]){ dfs(y); } } } 2. 너비 우선 탐색(Breadth First Search) 큐를 이용해 지금 위치에 갈 수 있는 것을 모두 큐에 넣는 방식 큐에 넣을 때 방문했다고 체크..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 위 문제를 푸는 방법은 여러가지지만, 인접행렬, 인접 리스트, 간선 리스트를 모두 사용해보기 위한 방법으로 풀어본다. 문제 풀이 1. 간선 리스트를 통해 A, B, C, D를 특정한다. 2. 인접 행렬을 통해 B, C가 친구인지 알아낸다. (인접 행렬이 인접리스트보다 뛰어난 유일한 경우는 두 정점 사이에 간선이 있는지 없는 지 구하는 경우.) 3. 인접 리스트를 통해 D의 친구인 E 가 있는 지 탐색 4. A, B, C, D, E 중 동일인이 없다면 1을 출력 package graph; import j..

그래프 그래프: 정점(Node, Vertex)과 간선(Edge)으로 나타내는 자료구조의 한 종류 그래프 알고리즘의 포인트: "어떠한 문제 상황을 어떻게 그래프로 만들어낼 것인가" 경로(Path): 정점 A에서 B로 가는 경로 사이클(Cycle): 정점 A에서 다시 A로 돌아오는 경로 단순 경로/단순 사이클 같은 정점을 두 번 이상 방문하지 않는 경로/사이클 특별한 언급이 없다면, 일반적으로 말하는 경로/사이클은 단순 경로/사이클이다. 그래프의 종류 - 방향이 있는 그래프 - 방향이 없는 그래프(양방향 그래프) 알고리즘 상에서 방향이 없는 그래프는 모두 방향이 있는 그래프로 바꿔서 저장해야한다. - 간선이 여러개인 경우' 일반적으로 잘 없는 경우이지만, 필요한 간선을 제외하고 삭제하면 된다. ex) 최단 ..

소수(Prime Number)란? 약수가 1과 자기 자신 밖에 없는 수. 정수 n이 소수가 되려면 1. 2보다 크거나 같고, 2. n-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. boolean isPrimeNum(int a){ if (a < 2) { return false; } for (int i = 2; i

큐란? 한쪽 끝에서만 자료를 넣고 반대쪽 끝에서만 뺄 수 있는 자료구조 먼저 넣은 것이 먼저 나오기 때문에 FIFO(First In First Out) 이라고도 한다. push: 큐에 자료를 넣는 연산 pop: 큐에서 자료를 빼는 연산 front: 큐의 가장 앞에 있는 자료를 보는 연산 back: 큐의 가장 뒤에 있는 자료를 보는 연산 empty: 큐가 비어있는지 아닌지를 알아보는 연산 size: 큐에 저장되어있는 자료의 개수를 알아보는 연산 bfs 알고리즘에서 많이 쓰이기 때문에 필수적으로 알아두어야 하는 자료구조이다. java의 경우 java.util.Queue를 사용하면 된다. Java로 큐 구현하기(백준 10845) int[] arr = new int[10000]; int begin = 0; in..

https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 단어뒤집기를 푸는 3가지 방법 1. StringBuilder 2. for문 3. stack 1. StringBuilder sb.append(new StringBuilder(str).reverse()).append(" "); 2. for문 for(int j = str.length() ; j > 0 ; j--){ sb.append(str.charAt(j-1)); } sb.append(" ");..