알고리즘 (12) 썸네일형 리스트형 백준 DFSBFS-1260 www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS 알고리즘과 BFS 알고리즘을 구현할 수 있는지 점검해 볼 수 있는 좋은 문제이다. package BAEKJOON; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.Scanner; import java.util.Stack; publi.. 백준 종이의 개수-1780 www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 분할정복 알고리즘을 사용했다. 전체 영역을 검사한 뒤 전체가 같지 않으면 영역을 1/9로 나누면서 전체가 같으면 빠져나가고 다르면 그 내부를 9개로 나눠서 다시 검사하고... 를 반복했다. package BAEKJOON; import java.util.Scanner; public class CountOfPaper_1780 { static int[][] paper = null; static int[] .. 백준 단지번호붙히기-2667 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net DFS든 BFS든 문제는 해결 된다. 지나온 점들은 0으로 만들어주면서 다음 시작점을 찾도록 했다. package BAEKJOON; import java.awt.Point; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.Scanner; public class ComplexNum.. 백준 동전0-11047 www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 알고리즘으로 쉽게 해결된다. package BAEKJOON; import java.util.Scanner; public class Coin0_11047 { static int[] coins; public static int getCoinCount(int k) { int r = 0; // 이분탐색 써서 시작점 잡아도 좋겠다. for (int .. 이전 1 2 다음