후라이

https://www.acmicpc.net/problem/1707  해당 백준 문제는 이분 그래프 판별 문제이다.BFS, DFS 문제를 꾸준히 풀었다면 쉽게 풀이할 수 있을 것이다. 이분 그래프란?: 그래프의 정점들을 두 개의 집합으로 나누었을 때, 각 집합에 속한 정점끼리는 서로 간선으로 연결되지 않으며두 집합에 속한 정점들끼리만 간선으로 연결된다는 것. (1) 정점 집합 분할 : 이분 그래프는 정점들을 두 개의 집합으로 나눌 수 있다.즉, 집합 A와 집합 B가 있고, 각 간선은 집합 A의 정점과 집합 B의 정점 간에만 존재한다. (2) 인접 정점  : 두 집합에 속한 정점들은 서로 인접해야 하며, 같은 집합에 속한 정점들끼리는 인접하지 않다.   이분 그래프인지 아닌지를 탐색하는 데에는 BFS, DF..

https://www.acmicpc.net/problem/1012   해당 문제는 배추를 보호하기 위한 배추흰지렁이의 수를 구하기 위해, 그래프 순회 알고리즘을 사용하는 문제이다.이전 단계에서 DFS, BFS 문제를 풀이했었다면, 이 문제도 큰 어려움 없이 문제를 풀 수 있다. import java.util.*;public class Main { // 방향 벡터 (상, 하, 좌, 우) static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t =..

https://www.acmicpc.net/problem/17299  해당 백준 문제는 오등큰수를 스택 알고리즘을 사용해 풀이하는 문제이다.예시를 보면 어떤 문제인지 이해할 수 있다. 우선 문제에 맞게1. N개의 수를 저장할 배열2. 배열 내에서 특정 숫자가 몇 번 등장했는지 frequency를 저장할 배열3. NGF를 저장할 배열 을 만들어주면 된다.  int N = Integer.parseInt(br.readLine()); int[] A = new int[N]; int[] NGF = new int[N]; // 결과 배열 int[] freq = new int[1000001]; // 등장 횟수 기록 배열 StringTokenizer st =..

https://www.acmicpc.net/problem/2293  해당 문제는 DP를 사용해 주어진 동전의 가치로 해당 금액(k)을 만들 수 있는 경우의 수를 구하는 문제이다.문제 예제와 같이 3가지의 동전과 각각의 가치 1,2,5가 주어졌을 때이 세 가지 종류의 동전으로 10을 만들 수 있는 가지수를 구하는 것이다.  1원 10개1원 8개 + 2원 1개1원 6개 + 2원 2개1원 4개 + 2원 3개1원 2개 + 2원 4개2원 5개1원 5개 + 5원 1개1원 3개 + 2원 2개 + 5원 1개1원 1개 + 2원 3개 + 5원 1개5원 2개쉽게 하나하나 구해보면 위와 같은 총 10가지의 경우의 수가 나오게 될 것이다. 이제 이 문제를 동적계획법(DP)로 풀이해보자.우선, 동전의 가치를 저장할 정수형 배열을..