공부하는 블로그

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;..

동적 프로그래밍과 탐욕법은 문제를 해결하여 최적의 해를 구하는 방법이다. Dynamic Programming? 동적 프로그래밍(Dynamic Programming)은 큰 문제를 하위의 작은 문제들로 나누어 풀어 최적의 해를 구하는 기법이다. 이러면 분할정복 기법과 다를게 없어 보인다. 하지만 분할정복 기법은 작은 문제들을 풀다보면 같은 작은 문제를 반복해서 푸는 경우가 생기게 된다. 이 때, 작은 문제를 매번 다시 계산하지 않고 값을 배열에 저장(Memoization)해두었다가 재사용하는 것이 동적 프로그래밍이다. 동적 프로그래밍을 이용하여 풀 수 있는 대표적인 문제는 피보나치 수열, 최장 공통부분 수열문제, 배낭 문제 등이 있다. 간단하게 피보나치수열 문제를 풀어보자. package fibonacci;..

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..

Dijkstra Algorithm ? 다익스트라 알고리즘(Dijkstra Algorithm)은 가중치를 가진 그래프에서 최단 경로를 탐색하는 알고리즘이다. 단, 가중치가 양수일 경우에만 사용이 가능하다. 다익스트라 알고리즘의 기본 로직은 출발 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단 거리를 갱신해나간다. 이러한 방식으로 출발 정점에서부터 다른 모든 정점까지의 최단 경로를 구할 수 있다. 그 과정은 다음과 같다. 1. 출발 정점으로부터 각 정점에 도달하는데까지 걸리는 시간을 계산한다. (연결이 되지 않았다면 가중치는 ∞) 2. 방문하지 않은 정점 중에서 제일 짧은 시간이 걸리는 정점을 찾는다. 3. 찾아낸 정점에서 이웃 정점에 도달하는데 걸리는 시간을 계산한다. 만약 이전에 기록한 시간보다 ..