패스트캠퍼스 챌린지 32일차

동적 프로그래밍 (Dynamic Programming) 1

 - 문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제 해결

 

 

동적 프로그래밍 풀이 방식

1. 풀고 싶은 가짜 문제 정의

2. 가짜 문제를 풀면 진짜 문제를 풀 수 있는가?

3. 가장 작은 문제 해결하기

4. 3)에서 계산 한 것을 기반으로, 점점 더 큰 문제 해결하기

5. 1~4) 가 성공적으로 끝난다면 진짜 문제 해결하기

 

1,2,3 더하기 (BOJ 9095)

- 정수 n이 주어졌을떄, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성

 

접근1 : 풀고싶은 가짜 문제 정의

  - 진짜 문제를 써 본후 가짜 문제로 정의한다

  - Dy[i] = i 를 1,2,3의 합으로 표현하는 경우의 수

접근2 : 가짜 문제를 풀면 진짜 문제를 풀 수 있는가?

  - Dy 배열을 가득 채운다면, 진짜 문제에 대한 값은 Dy[N] 

접근3 : 초기값은 어떻게 되는가?

 - 초기값 : 쪼개지 않아도 풀 수 있는 작은문제 들에 대한 정답

접근4: 점화식 구해내기

 4-1) Dy[i] 계산에 필요한 탐색 경우를 공톰점끼리 묶어내기 (Partitioning)

  => 전체 경우의 수 = 각 파티션의 경우의수 의 합

  EX) N= 5일 경우

  - 마지막에 1을 더하는 경우 = 합이 i-1인 경우 (1+1+1+1+1 ...)

  - 마지막에 2를 더하는 경우 = 합이 i-2인 경우 (1+1+1+2 ...)

  - 마지막에 3을 더하는 경우 = 합이 i-3인 경우 (1+1+3 ...)

 점화식 : Dy[i] = Dy[i-1] + Dy[i-2] + Dy[i-3]

 4-2) 묶어낸 부분의 정답을 Dy 배열을 이용해서 빠르게 계산하기 

 

구현

static int[] Dy;

static void preprocess(){
	Dy = new int[15];
    
    //초기값 구하기
    Dy[1] = 1;
    Dy[2] = 2;
    Dy[3] = 3;
    
    // 점화식을 토대로 Dy 배열 채우기
    for(int i = 4; i <=11; i++){
       Dy[i] = Dy[i-1] + Dy[i-2] + Dy[i-3];  
    }
}

static void pro(){
   int T = scan.nextInt();
   for (int tt = 1; tt <= T; tt+){
     int N = scan.nextInt();
     sb.append(Dy[N]).append('\n');
   }
   System.out.print(sb);  
}

 

2 X N 타일링 (BOJ 11726)

 - 가장 오른쪽에 있는쪽에 오는 도형이 세로 도형이냐, 가로 도형이냐로 구분

 점화식 

  - Dy[i] = (Dy[i-1} + Dy[i-2]) % 10007

 

 완전 탐색을 통해 모든 경우를 세면 정답의 개수만큼 시간이 걸리지만, Dy 배열을 1번지부터 N번지 까지

 채우는 것은 O(N) 이라는 시간복잡도면 충분

 

	static int N;
	static int[] Dy;
    
	static void input(){
		N = scan.nextInt();
   	}

    static void pro() {
        Dy = new int[1005];
        // 초기값 구하기
        Dy[1] = 1;
        Dy[2] = 2;

        // 점화식을 토대로 Dy 배열 채우기
        for (int i = 3; i <= N; i++){
            Dy[i] = (Dy[i - 1] + Dy[i - 2]) % 10007;
        }
        System.out.println(Dy[N]);
    }

 

 

32일차 인증

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]