공부하는 블로그

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 주어진 수열에서 연속합이 가장 큰 경우를 찾는 문제이다. 연속합이란 수열에서 연속된 수를 선택해서 구할 수 있는 합이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] sum = new int[n];// i번째까지의 합을 저장하는 수열 int[] dp..

11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 수열이란 S(1) S(k+1) > S(k+2) > ··· > S(n-1) > S(n)을 만족하는 수열이다. 주어진 수열의 부분 수열 중에서 가장 긴 바이토닉 수열을 찾는 문제이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int ..

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분 수열(Longest Common Subsequence, LCS)를 찾는 문제이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str1 = sc.next(); String str2 = sc.next(); sc.clo..

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

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