동적계획법 : 동적계획법 이론과 문제

I. 들어가며

모든 알고리즘은 사실 완전탐색(DFS, BFS)를 이용해서 정답을 도출할 수 있다

그럼에도 불구하고 알고리즘 기법이 탄생한 이유는 비효율적인 연산과 시간을 없애고 답을 효율적으로 도출하기 위함이다.

동적계획법(이하 'DP')은 가장 다양한 유형의 문제들을 논리적 사고로 효율적으로 풀 수 있는 알고리즘이다.

 

II. 동적계획법 알아보기

1. 정의

동적계획법(Dynamic programming : DP) 는

1) 복잡한 여러문제를 간단한 문제로 분리하여

2) 부분의 문제를 해결함으로써

3) 최종적으로 복잡한 문제의 답을 구하는 방법을 의미한다.

 

2. 핵심이론

(1) 원리와 구현방식 [예 : 피보나치 수열]

1) 큰 문제를 작은문제로 나눌 수 있어야한다 (분리)

[6번 수열 구하는 문제는 5번과 4번수열의 합이다

-> 이 경우 5번수열을 구하는 문제와 4번수열을 구하는 문제로 나눌 수있다]

 

2) 작은 문제들이 반복돼 나타나고 사용되며, 이 작은 문제들의 결과값은 같아야한다.

[이렇게 수열문제는 반복되고, 수열의 값은 항상 같다]

[점화식 : 전체문제를 나누기 -> 전체문제와 부분문제간 인과관계 파악하기 ]

[ D[i] = D[i - 1] + D[i - 2] ]

 

3) 모든 작은 문제들 한번만 계산해 DP테이블에 저장, 추후 재사용시 DP테이블 이용 (메모리제이션기법)

[메모리제이션 이란 부분문제를 풀었을 때 DP테이블에 저장하고, 다음부터는 DP테이블 값 이용하는 것임]

 

4) DP는 top-down 방식, bottom-up 방식으로 대별된다.

 

a. top-down

재귀함수 형태로 코드 구현

장점 : 코드의 가독성, 이해하기 편리함

단점 : 런타임에러 발생 가능

 

b. bottom-up

작은문제부터 해결하면서 점점 큰문제로 확장해 나가는 방법 -> 반복문 형태로 구현

III. 동적계획법 문제1 : 정수를 1로 만들기

[ 백준 1463 ]

1. 문제설명

 

2. 문제풀이

(1) 문제분석

• Bottm-up 방식 구현 연습문제
• 점화식을 코드화 하는 훈련

(2) 손으로 풀기

1) 점화식의 형태와 의미 도출

D[i] : ~~ 이다

 

2) 점화식 구하기

3가지 case 구하기

 

3) 점화식을 이용해 D 배열 채우기

앞에서 부터 값을 구하면서 저장

4) D[N] 출력

 

 

(3) 슈도코드 코드 작성

- 블로그에서 생략

(4) 코드 구현 

1)

package datastructrue11;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//점화식 : 점점 꽃이 되어가는 식
//작은것부터 ! 2번배열부터! -> 바텀업


//문제 이슈 1 : 1을 바로 혹은 2와 3 둘다 중복되는 경우
//누가 더 적은지 비교하는 방법?  min으로 한다
// 다만 기본으로 -1을 하는것 혹은 2로 나눈경우를 먼저 연산해서 넣어준다



public class P1463 {

    public static void main(String[] args) throws IOException {

        //버퍼로 입력받음
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //문자열을 정수형으로 바꾸기
        int N = Integer.parseInt(br.readLine());

        //쉬운 생각을 위해서 N + 1 로 선언
        int [] D = new int[N + 1];
        //0으로 세팅한다
        //다만 정수형 배열의 기본값은 0이다.
        D[1] = 0;

        //2부터 N까지 반복한다.
        for(int i = 2 ; i < N + 1 ; i++){

            //최초에 기본값 세팅으로 무조건 다 뺀다.
            D[i] = D[i - 1] + 1 ;

            //1을 빼고 나서 연산한 값과 나눈연산이 둘다 가능한 경우가 있다
            // 이 경우 Math.min 함수를 써서 비교 후 적은 값을 대입한다.
            if(i % 2 == 0)
                D[i] = Math.min(D[i], D[i/2] + 1);

            //마찬가지로 1을 빼고나서 연산한값
            // 혹은 2와 동일하게 나누어 떨어지는 값이 있을 수있다.
            // 이 경우 3으로 나누는것이 더 최솟값이 될 수있는 지 비교후 대입한다
            if(i % 3 == 0) {
                D[i] = Math.min(D[i], D[i/3] + 1);
            }
        }

        for(int i : D){
            System.out.print(i + " ");
        }

    }

}

4. 보충 및 회고 

(1) 보충

1) 점화식을 세우는 법에대해서 공부가 필요할것 같다.

 

 

 

 

 

 

(2) 회고 : 문제풀이과정에서 어떻게 접근하려고했는지 (접근방법) + 어려움이 있었는데 해결했다.

1)

많은 깨달음이 있었던 문제이다 다양한 어려움이 있었다.

점화식을 만드는것부터 자체가 어려움이 있었다

그리고 이러한 점화식을 코드화 할 때도 마찬가지이다.

 

2)

3가지의 경우 점화식을 세우고나서 이 경우에 대해서 순서를 두는것 자체도 큰 의미로 만들어 질 수있다는것을 알게되었다

 

3) 

위 순서를 이용해서 불리한 경우를 먼저 넣고 Math.min() 으로 비교 후에 대입하는 방식에서 놀라움을 감추지 못했다.!

 

IV. 동적계획법 문제2 : 퇴사 준비하기

[ 백준 14501 ]

1. 문제설명

2. 문제풀이

(1) 문제분석

• D[i] 를 어떻게 할지 정의를 해야함
• D[i] 의 정의를 i번째 날부터 퇴사일 까지의 최대수입으로 정의

(2) 손으로 풀기

1) 점화식의 형태와 의미 도출

D[i] : i번째 날부터 퇴사일 까지 벌 수 있는 최대수입이다

 

2) 점화식 구하기

오늘 시작되는 상담이 퇴사일 까지 끝나는지 여부로 대별됨

퇴사일부터 역산해서 하는것이 용이함 

 

3) 점화식을 이용해 D 배열 채우기

 

 

(3) 슈도코드 코드 작성

- 블로그에서 생략

(4) 코드 구현 

1)

package datastructrue11;

import java.util.Scanner;

public class P14501 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int D [] = new int[N+2]; //점화식 배열
        int T [] = new int[N+1]; //상담에 필요한 일수 저장배열
        int P [] = new int[N+1]; //상담완료시 수입저장배열

        for(int i = 1 ; i < N + 1 ; i++ ){
            T[i] = sc.nextInt();
            P[i] = sc.nextInt();
        }

//        for(int i = N ; i > 0 ; i --){
//            if(i + T[i] > N + 1){
//                D[i] = D[i + 1];
//            }
//            else{
//                D[i] = Math.max(D[i+1], P[i] + D[i + T[i]]);
//            }
//        }


        // N 부터 0까지 반복하기
        for(int i = N ; i > 0 ; i --){

            //i 번째의 필요일수 더한날이! / 퇴사일보다 큰 경우
            if(i + T[i] > N + 1){

                //다음 상담시작일정으로 넘긴다.
                D[i] = D[i + 1];
            }
            //퇴사일 보다 작은경우
            else {

                // 다음 상담시작일정에서 수입과
                // i번째의 필요일수 더한날을 마쳤을 때 수입의 최대값을 비교한다.
                D[i] = Math.max(D[i + 1], P[i] + D[i + T[i]]);
            }

        }



        System.out.println(D[1]);

    }
}

4. 보충 및 회고 

(1) 보충

1) 점화식을 세우는 법에대해서 공부가 필요할것 같다.

 

2) 

 

 

 

 

(2) 회고 : 문제풀이과정에서 어떻게 접근하려고했는지 (접근방법) + 어려움이 있었는데 해결했다.

1)

점화식만이라도 세우려고 하다가 1시간을 꼬박 사용했었던것 같다

 

2)

점화식의 정의와 형태를 먼저 생각하는 방식으로 하는 것이 좋을것같다. 또한 역산하는 방식으로도 생각해보는것도 바람직한 방법일수도 있다고 생각된다.

 

3)

반복문 for 의 경우 0부터 시작하는것이 아니라, 0으로 끝나는 방식도 생각해보는것도 괜찮을것 같다.

 

IV. 동적계획법 문제3 : 이친수구하기

[ 백준 2193 ]

1. 문제설명

 

2. 문제풀이

(1) 문제분석

• D[i] 를 어떻게 할지 정의를 해야함
• D[i] 이차원 배열 방식으로 접근한다
• 키포인트는 이친수를 0으로 끝나는경우, 1로 끝나는 경우 구분하기 !
•  

1) 점화식의 형태와 의미 도출

D[i][0] : i 길이에서 끝이 0으로 끝나는 이친수의 개수

D[i][1] : i 길이에서 끝이 1로 끝나는 이친수의 개수

 

 

2) 점화식 구하기

//뒷부분이 0인경우
    D[i][0] = D[i - 1][1] +D[i - 1][0] ;
//뒷 부분이 1인경우
    D[i][1] = D[i - 1][0];

 

3) 점화식을 이용해 D 배열 채우기

(3) 슈도코드 코드 작성

- 블로그에서 생략

(4) 코드 구현 

1)

package datastructrue11;

import java.util.Scanner;

public class P2193 {

    public static void main(String[] args) {

        //N 입력 선언
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int [][] D = new int[N + 1][2] ;

        //앞부분 N , 뒤부분 0 or 1
        D[1][1] = 1;
        D[1][0] = 0;

        for(int i = 2 ; i < N + 1 ; i ++){

        //뒷부분이 0인경우
            D[i][0] = D[i - 1][1] +D[i - 1][0] ;
        //뒷 부분이 1인경우
            D[i][1] = D[i - 1][0];

        }

        System.out.println(D[N][0] + D[N][1]);


    }
}

4. 보충 및 회고 

(1) 보충

1) 의문1

문제의 조건에서 예시로 주어진건 N이 4일때 인것인지?

 

2) 의문2

N을 6입력했는데 왜 풀이 과정에서는 5가 나왔는지? 첫자리가 이미 정해져있다고 해도, 그것을 기준으로 계속 나아가는데?

 

 

 

 

(2) 회고 : 문제풀이과정에서 어떻게 접근하려고했는지 (접근방법) + 어려움이 있었는데 해결했다.

1)

점화식 정의를 1차로만 생각하다가 다시 또 2차를 보니 신기하다

 

2)

녹록치않은데,,, 이렇게 하는게 맞나 싶다...

 

3)

정수형은 가급적 long 자료형으로