공부하는 블로그

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 주어진 수열에서 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)을 찾는 문제이다. LIS란 주어진 수열이 {10, 20, 50, 20, 30, 40, 60, 10, 80} 이라면 {10, 20, 30, 40, 60, 80}을 뜻한다. import java.util.Scanner; public class Main { public static ..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 배낭의 무게와 물건들의 가치와 무게가 함께 주어진다. 주어진 물건들을 이용하여 배낭의 값어치를 최대로 채우는 문제이다. import java.util.Scanner; public class Main { static int[][] items; static int[][] bag; public static void main(String[] args) { Scanner sc = new Scanner(Sys..

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 동적 프로그래밍을 이용해서 계단 수의 개수를 찾는 문제이다. package p10844; import java.util.Scanner; public class Main { static int[][] dp = new int[101][10]; static final int mod = 1000000000; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.close(); for (int i = 1; i < 10; i++) { dp[1][i] = 1; ..

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