2021년 1월 28일
주제 : DP(Dynamic Programming)
문제 : 백준사이트 1965, 1535, 17212
DP란 ?
동태계획법은 동적계획법이라고도 하며 벨만(Bellman)에 의해서 고안된 것인데 재귀(再歸)라고 하는 수학적 개념에 기초를 두고 「최적성의 원리」에 따라 다단계의 결정과정을 취급하는 것이며 최대의 목재생산을 위한 간벌계획문제를 비롯해서 각종의 배분문제, 재고문제, 경제문제 등의 여러 가지 결정문제에 유용하게 쓰인다.
출처: 네이버 지식백과
DP 해결방법
제가 생각하는 DP의 핵심은 큰문제를 작은 문제로 나누어 푸는 것입니다. 이때, 작은 문제들은 한번만 풀고 그 값을 저장하여 다른 큰 문제를 풀때 저장된 값을 이용하여 문제를 해결합니다. 그래서 DP의 많은 문제를 재귀를 이용하면 쉽게 해결 가능합니다.
DP를 사용해야하는 상황
아직 문제를 만났을때 DP로 풀어야하는지 아닌지 구분을 잘 못하지만 다른 사람들의 말은 빌어 얘기해보자면 하나의 큰문제를 작은 문제로 나눌수가 있다. 즉, 분기가 발생하는 문제에 쉽게 적용 할 수 있습니다.
DP에서 알아야할 핵심 개념
Memoization
메모이제이션은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 메모아이제이션이라고도 한다.
예시
//before fib(n) { if n is 1 or 2, return 1; return fib(n-1) + fib(n-2); } //after fib(n) { if memo[n] is zero: memo[n] = fib(n-1) + fib(n-2); return memo[n]; }
해결 방법
DP는 크게 두가지 해결 방법이 있다.
Bottom-up
- 작은 문제에서 출발하여 큰 문제를 향해 가는 방식
- For문을 이용하여 처음값부터 다음값을 계산해 나가는 방식으로 구성
Top-Down
- (Top-Down)큰 문제에서 출발하여 작은 문제로 향해가는 방식
- 재귀와 같은 방식으로 위에서 아래로 내려오는 방식
- 함수 호출을 줄이기 위해 메모이제이션을 사용!
<코드>
Bottom-up 방식
import java.util.Scanner;
public class Boxin {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int N =sc.nextInt();
int max=0;
int[] box = new int[N];
int[] bl = new int[N];
for(int i =0 ; i< N; i++)
{ int size = sc.nextInt();
box[i]=size;
bl[i]=1;
}
for(int i =0 ; i< N; i++)
{
for(int j=0;j<i;j++) {
if(box[i]>box[j] &&bl[j]+1 > bl[i])
{
bl[i]=bl[j]+1;
}
}
}
for(int i=0;i<N;i++) {
if(bl[i]>max) {
max = bl[i];
}
}
System.out.println(max);
}
}public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] L = new int[N+1];
int[] J = new int[N+1];
int[][]D =new int [21][101];
int max=0;
for(int i = 1 ; i<=N;i++) {
L[i]=sc.nextInt();
}
for(int i = 1 ; i<=N;i++) {
J[i]=sc.nextInt();
}
for(int i = 1 ; i<=N;i++) {
for(int j=1; j<100;j++) {
if(L[i] <=j && (D[i-1][j-L[i]] + J[i] > D[i][j])) {
D[i][j] = Math.max(J[i] + D[i-1][j - L[i]], D[i-1][j]);
}
else
D[i][j] = D[i-1][j];
max = Math.max(D[i][j], max);
}
}
System.out.println(max);
}
}import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int N = sc.nextInt();
int D[] = new int[100001];
D[1]=1;
for(int i=2;i<=N;i++) {
if(i<2) {
D[i]=D[i-1]+1;
}
else if(i<5) {
D[i] = Math.min(D[i-1],D[i-2])+1;
}
else if(i<7) {
D[i] = Math.min(D[i-5], Math.min(D[i-1],D[i-2]))+1;
}
else
D[i] = Math.min(D[i-7], (Math.min(D[i-5], Math.min(D[i-1],D[i-2]))))+1;
}
System.out.println(D[N]);
}
}
Top-down 방식
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static final Scanner SCANNER = new Scanner(System.in);
private static int n;
private static int[] boxes;
private static int[] d;
public static void main(String[] args) {
n = SCANNER.nextInt();
boxes = new int[n];
d = new int[n];
for (int i = 0; i < n; i++) {
boxes[i] = SCANNER.nextInt();
}
for(int i=0; i < n; i++){
d[i] = 1;
for(int j=0; j < i; j++){
if(boxes[j] < boxes[i] && d[j]+1 > d[i])
d[i] = d[j]+1;
}
}
Arrays.sort(d);
System.out.println(d[n-1]);
}
}느낀점
이번 스터디를 통해서 정말 내가 많이 부족하구나를 느끼는 스터디였다, 막상 다른 팀원에게 내가 생각한 로직을 전달하는 것은 굉장히 힘들었고 그 이유 중 하나가 내가 정말로 DP를 이해하고 있지 않다는 생각이 많이 들었다. 이번에 조금 더 DP를 들여다 보고 매주 한문제의 DP 문제를 추가로 더 풀어보면 좋을것 같다는 생각이 든다. 재귀를 이용한 Top-Down 방식으로 코드를 더 짜보자!
목표
스터디를 총 4번 진행 즉, 한달 후에 공부했던 코드들을 보고 백준에서 각각 유형에 해당하는 문제를 풀어보자!!
다른 팀원들에 비해 많이 늦었지만 따라잡자 그게 내 주특기니까!
