공부하는 블로그

9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 동적 프로그래밍을 활용하여 점화식을 해결하는 문제이다. import java.util.Scanner; public class Main { static long[] memory; public static void main(String[] args) { Scanner sc = new Scanner(System.in); StringBuilder sb = new StringBuilder(); int t = sc.nextInt(); for (int i = 0; i < t;..

10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬의 거듭 제곱을 구하는 문제이다. import java.util.Scanner; public class Main { static int N; static int[][] A; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); A = new int[N][N]; long B = sc.nextLong(); for (int i = 0; i < N; i++) { f..

2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 행렬 곱셈을 하는 간단한 문제이다. import java.util.Scanner; public class Main { static int N; static int M; static int K; static int[][] A; static int[][] B; public static void main(String[] args) { // 입력 Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = ..

2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 재귀 호출을 이용한 분할 정복 알고리즘을 구현하는 문제이다. import java.util.Scanner; class Main { static int N; static int[][] paper; static int blue = 0; static int white = 0; public static void main(String[] args) { // 입력 Scanner sc = new Scanner(System.in); N = sc.ne..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 깊이우선탐색(DFS)를 이용해서 아파트 단지가 몇개인지, 각 단지에는 아파트가 몇개인지 찾는 문제이다. import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { static int N; // 지도의 크기 static int[][] map; // 지도 static boolean[][] visit; // 방문 여부 저장 static int..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존� www.acmicpc.net 다익스트라 알고리즘을 이용하여 최단 경로를 찾는 문제에서 경유지 두 군데가 추가된 문제이다. import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static class Node implements Comparable{ int v; int d; public Node(int v, in..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다익스트라 알고리즘을 이용하여 가중 그래프에서 출발 정점으로부터 각 정점의 최단 경로를 구하는 문제이다. import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static class Graph implements Comparable { int vertex; int weight; public Graph(..

1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 우선순위가 정해진 문제를 푸는 순서를 찾아내는 문제이다. 문제를 푸는 순서에 대한 조건은 두 가지가 있다. 1. 순서가 정해진 문제는 순서에 맞춰 풀어야 한다. ---- 위상정렬 2. 가능한 쉬운 문제(문제 번호가 낮은 문제) 먼저 풀어야 한다. ---- 우선순위 큐 import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public ..