Algorithm Study #3 (Dynamic Programming (DP) - 1.2)

jakeseo_me·2019년 2월 16일
1

java algorithm study

목록 보기
9/18

DP문제풀이 1 - 1로 만들기

  • 1로 만들기, boj.kr/1463

    • 세준이는 어떤 정수 N에 다음과 같은 연산 중 하나를 할 수 있다.
      1. N이 3으로 나누어 떨어지면 3으로 나눈다.
      2. N이 2로 나누어 떨어지면 2로 나눈다.
      3. 1을 뺀다.
      • 세준이는 어떤 정수 N에 위와 같은 연산을 선택해서 1을 만드려고 한다.
      • 연산을 사용하는 횟수의 최소값을 출력하시오.
  • 문제 풀이 접근법

    • 숫자를 빨리 줄여야 한다.

      • 3으로 나누는 연산을 최대한 많이 사용
        • 2로 나누는 연산을 그 다음으로 많이 사용
        • 1을 빼는 연산을 가장 적게 사용
      • 하지만 무작정 나눈다고 빨리 풀릴까?
        • 10의 경우를 살펴보자
          - 무작정 나누는 경우
          	- 10을 2로 나누면 5
              - 5에서 1을 빼면 4
              - 4에서 2로 나누면 2
              - 2에서 1을 빼거나 2로 나누면 1
          - 1을 빼서라도 3의 배수로 만드는 경우
          	- 10에서 1을 빼면 9
              - 9에서 3으로 나누면 3
              - 3에서 3으로 나누면 1
          - 결과적으로 무작정 나누는 것은 해답이 될 수 없다.
          - 다이나믹 프로그래밍이 필요하다.
      • D[N] 배열에는 무엇을 Memoization 해야 하는가?
        • N을 1로 만드는데 필요한 연산의 최소값
      • N을 어떻게 분기시킬까?
        • N을 3으로 나눈다면?
          - D[N/3] + 1
          • N을 2로 나눈다면?
            • D[N/2] + 1
          • N에서 1을 뺀다면?
            • D[N-1] + 1
      • 간단한 프로세스를 정의해보자
        • 먼저 n=1부터 최소한의 경우의 수를 구해놓는다.
          • n=1일 때 구해놓은 값을 기준으로 n=2를 구한다.
          • n=2일 때 구해놓은 값을 기준으로 n=3을 구한다.
          • 반복한다... n=n일 때 최소값을 구한다.
    • 실제 구현(top-down)

      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      
      public class Main{
      
          static int[] d;
      
          static int go(int n){
              if( n == 1 ) return 0; // 1일 때는 아무 연산도 할 필요 없음
      
              if( d[n] > 0 ) return d[n]; // 이미 계산된 값인 경우 그것을 이용하면 된다.
      
              d[n] = go(n-1) + 1; // n-1을 계속 수행했을 때 (일반적으로 최악의 경우)
      
              if (n%2 == 0) {
                  int temp = go(n/2) + 1; // 2로 나누는 것이 이득일 때 배열 교환
                  if (d[n] > temp) d[n] = temp;
              }
      
              if (n%3 == 0) {
                  int temp = go(n/3) + 1; // 3으로 나누는 것이 이득일 때 배열 교환
                  if (d[n] > temp) d[n] = temp;
              }
      
              return d[n];
          }
      
          public static void main(String args[]) throws IOException {
              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
              int n = Integer.parseInt(br.readLine());
              d = new int[n+1];
              go(n);
              System.out.println(d[n]);
          }
      }
      - 실제 구현(bottom-up)
      ```java
    import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      
      public class Main{
      
          public static void main(String args[]) throws IOException {
              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
              int n = Integer.parseInt(br.readLine());
      
              if(n == 1){
                  System.out.println(0);
                  return;
              }
      
              int[] d = new int[n+1];
      
              d[0] = 0;
              d[1] = 0;
              d[2] = 1;
      
              for(int i=3; i<=n; i++){
                  int di = d[i-1]+1;
                  if(i%2 == 0) di = (di <  d[i/2]+1) ? di : d[i/2]+1;
                  if(i%3 == 0) di = (di <  d[i/3]+1) ? di : d[i/3]+1;
                  d[i] = di;
              }
      
              System.out.println(d[n]);
          }
      }

DP문제풀이 2 - 2 X n 타일링

  • 2 X n 직사각형을 1X2, 2X1타일로 채우는 방법의 수
  • boj.kr/11726
  • 아래 그림은 2X5를 채우는 방법의 수
  • D[i] = 2Xi 직사각형을 채우는 방법의 수
  • n번째 열에 타일을 어떻게 놓을 것인가?
    • d[n] = d[n-1] + d[n-2] 만 알면 풀 수 있는 간단한 문제
      • ppt의 이미지 참조
      • 구현 코드
        import java.io.BufferedReader;
        import java.io.IOException;
        import java.io.InputStreamReader;
        import java.math.BigInteger;
        
        public class Main{
        
            public static void main(String args[]) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                int n = Integer.parseInt(br.readLine());
        
        
                if(n == 1){
                    System.out.println(1);
                    return;
                }
        
                BigInteger[] d = new BigInteger[n+1];
        
                d[1] = new BigInteger("1");
                d[2] = new BigInteger("2");
        
                for(int i=3; i<=n; i++){
                    d[i] = d[i-1].add(d[i-2]);
                }
        
                System.out.println(d[n].mod(new BigInteger("10007")));
            }
        }

DP문제풀이 3 - 2 X n 타일링 2

  • 위의 문제와 흡사
  • 2x2 사각형만 추가로 고려해주면 됨
  • boj.kr/11727

DP문제풀이 4 - 1, 2, 3 더하기

  • boj.kr/9095
  • 정수 n을 1, 2, 3의 조합으로 나타내는 방법의 수를 구하는 문제
    • n = 4일 때
      - 1+1+1+1
      - 1+1+2
      - 1+2+1
      - 2+1+1
      - 2+2
      - 1+3
      - 3+1
      	- 총 7가지의 방법
  • 마지막 숫자가 1, 2, 3일 때를 고려하면 된다.
    • 마지막 숫자가 1일 때, 합은 n-1
      • 마지막 숫자가 2일 때, 합은 n-2
      • 마지막 숫자가 3일 때, 합은 n-3
        • 4일 때는,
          - 3, 2, 1을 구하는 방법의 합을 전부 다 합치면 된다.
          	- D[3] + D[2] + D[1]

DP문제풀이 5 - 카드 구매하기

  • boj.kr/11052

  • D[n] = n개 팔아서 얻을 수 있는 최대 수익

  • max(P[i]+D[n-i])

  • 1<=i<=n

  • 가능한 경우 생각해보기

    • 총 채워야 하는 칸의 개수 n
      • D[n] 한 칸을 채울 때
        • 1~n까지 n번 검사해야 함
  • 구현

    import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      import java.util.StringTokenizer;
    
      import static java.lang.Math.max;
    
      public class Main{
    
          public static void main(String args[]) throws IOException {
              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
              int n = Integer.parseInt(br.readLine());
              StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    
              int[] p = new int[10001];
              int[] d = new int[10001];
    
              p[0] = 0;
        for(int i=1; i<=n; i++){
            p[i] = Integer.parseInt(st.nextToken());
        }

        d[0] = 0;

        for(int i=1; i<=n; i++){
            for (int j=1; j<=i; j++) {
                d[i] = max(d[i], d[i-j] + p[j]);
            }
        }

        System.out.println(d[n]);
    }
}
```
- 각각 쌓는 방식
	- d[1] + d[3]의 조합 vs d[2] + d[2]의 조합 vs ... 과 같은 방식으로 해결
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. Javascript를 좋아합니다.

0개의 댓글