다이나믹 프로그래밍

27 Dec 2019 | Algorithm

다이나믹 프로그래밍

다이나믹 프로그래밍 정의

동적 계획법(DP)라고도 한다
큰 문제를 작은 문제로 나눠서 푸는 알고리즘
- DP
  - 작은 문제 중복o
- D&C(분할정복)
  - 작은 문제 중복x

두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다

Overlapping Subproblem (겹치는 작은 문제)
- 피보나치 수열
  - F(4) = F(3) + F(2), F(3) = F(2) + F(1)
  - F(3),F(2)가 중복된다
Optimal Substructure (최적 부분구조)
- 부분 문제의 답으로 문제의 답을 구할 수 있다.
  - F(n) = F(n-1) + F(n-2) (n>=2)
  - F(n)의 답을 F(n-1)와 F(n-2)로 구할 수 있다.
- Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
  - F(4)는 F(6), F(5)을 구할 때마다 일정하다.

다이나믹 프로그래밍 풀이

다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다
Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다
따라서 정답을 한 번 구했으면 어딘가에 메모해 놓는다.
이를 Memoization이라고 한다.

예제(피보나치 수열)

//f(5)를 구하려면?
f(5) = f(4) + f(3);
f(4) = f(3) + f(2);
f(3) = f(2) + f(1);
f(2) = f(1) + f(0);
f(1) = 1;
f(0) = 0;

//f(3), f(2), f(1)이 중복된다
int memo[100];
int fibonacci(int n){
  if(n<=1)
    return n;
  else{
    if(memo[n] > 0)
      return memo[n];
    memo[n] = fibonacci(n-1) * fibonacci(n-2);
    return memo[n];
  }
}

// 시간복잡도 -> 모든 문제를 1번씩 푼다
// 문제의 갯수 (n) * 문제 1개를 푸는 시간 (1)
// -> O(n)

다이나믹 프로그래밍 구현방식

Top-down (재귀)
Bottom-up (반복문)
- 문제를 크기가 작은 문제부터 차례로 푼다
- 문제의 크기를 조금씩 크게 만들면서 문제를 순차적으로 풀어나간다
- 반복하다 보면 가장 큰 문제를 풀 수 있다
```
int f[100];
int fibonacci(int n){
  f[0]=0;
  f[1]=0;
  for(int i=2; i<=n; i++){
    f[i] = f[i-1] + f[i-2];
  }
  return f[n];
}
```

Top-down vs Bottom-up 시간 차이

재귀보다 반복문이 빠르니 Bottom-up이 빠를것이다?
- 알 수 없다!

문제에 따라 따르다

f(0)=0;
f(1)=0;
f(2)=0;
f(3)=0;
...
f(9)=0;
     
f(n) = f(n-5) + f(n-10) (n>=10)
     
// f(10)을 구해라
// 1. 재귀
f(10) = f(5) + f(0); // 연산 1번
// 2. 반복문
f(10) = f(0)+f(1)+...f(10); // 연산 10번
     
     

Comment Read more

BOJ 9613번 GCD 합

27 Dec 2019 | Algorithm

package BOJ;

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

/**
 * BOJ 9613
 * GCD 합
 * https://www.acmicpc.net/problem/9613
 */

public class GCDSum_9613 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        while(n-- > 0){
            int[] line = Arrays.asList(br.readLine().split("\\s")).stream().mapToInt(Integer::parseInt).toArray();
            long sum=0; // int는 작아서 long으로 변경
            for(int i=1; i<line.length; i++){
                for(int j=i+1; j<line.length; j++){
                    sum += gcd(line[i], line[j]);
                }
            }
            System.out.println(sum);
        }
    }

    private static int gcd(int a, int b){
        if(b == 0)
            return a;

        return gcd(b, a%b);
    }

    private static int gcd2(int a, int b){
        int gcd = 0;
        for(int i=2; i<=Math.min(a,b);i++){
            if(a%i == 0 && b%i == 0)
                gcd = i;
        }
        return gcd;
    }
}

Comment Read more

BOJ 6588번 골드바흐의 추측

27 Dec 2019 | Algorithm

package BOJ;

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

/**
 * BOJ 6588
 * 골드바흐의 추측
 * https://www.acmicpc.net/problem/6588
 */
public class Goldbach_6588 {

    private static boolean[] prime = new boolean[1000000+1];

    public static void main(String[] args) throws IOException {
        eratosthenes(prime);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n;
        while((n = Integer.parseInt(br.readLine())) != 0){
            int[] answer = getTwoOfPrime(n);
            if(isValid(answer))
                System.out.printf("%d = %d + %d\n",n,answer[0],answer[1]);
            else
                System.out.println("Goldbach's conjecture is wrong.");
        }
    }

    private static void eratosthenes(boolean[] input) {
        input[1] = true;
        for (int i = 2; i < input.length; i++) {
            for (int j = 2 * i; j < input.length; j += i) { // j=i*i로 하면 stackoverflow 발생할 수 있다
                input[j] = true; // 지워진 경우
            }
        }
    }


    private static int[] getTwoOfPrime(int n){
        int[] TwoOfPrime = new int[2];
        for(int i=n-1; i>=0; i--){
            if(isPrime(i)){
                if(isPrime(n-i)){
                    TwoOfPrime[0] = n-i;
                    TwoOfPrime[1] = i;
                    break;
                }
            }
        }
        return TwoOfPrime;
    }

    private static boolean isPrime(int n){
        return prime[n] == false;
    }

    private static boolean isValid(int[] input){
        return input[0] != 0 && input[1] != 0;
    }
}

Comment Read more

BOJ 2960번 소수(에레토스테네스의 체)

26 Dec 2019 | Algorithm

소수

약수가 1과 자기 자신밖에 없는 수
N이 소수이면 N이 2<=x<N-1에 존재하는 x로 나누어 떨어지면 안된다.

어떤 수 N이 소수인지 아닌지 판별

public boolean isPrime(int n){
  if(n<2)
    return false;
  for(int i=2; i<n; i++){
    if(n%i == 0)
      return false;
  }
  return true;
}

1-2. N이 소수가 아니다 -> N = 2 * N/2로 나타낼 수 있다.

-> N이 소수이려면 2<=x<=N/2에 존재하는 x로 나누어 떨어지면 안된다.
N = a * b로 나타낼 수 있으며 a의 최소값은 2이므로 b<=N/2이다.

public boolean isPrime(int n){
  if(n<2)
    return false;
  for(int i=2; i<=n/2; i++){
    if(n%i == 0)
      return false;
  }
  return true;
}

1-3. N이 소수가 아니다 -> a<=√N, b>=√N (a<=b)

-> N이 소수이려면 2<=x<=√N에 존재하는 x로 나누어 떨어지면 안된다
24인 경우 √24 = 4….이고 24의 약수는 1,2,3,4,6,12,24 이다.
√N 보다 작은 약수가 소수여야 √N보다 큰 약수와 곱하였을때도 소수이고 √N 보다 작은 원소의 갯수가 √N보다 큰 원소의 갯수보다 작으므로 √N 보다 작은 원소까지 검사한다

public boolean isPrime(int n){
  if(n<2)
    return false;
  for(int i=2; i*i<=n; i++){
    if(n%i == 0)
      return false;
  }
  return true;
}

N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법

에라토스테네스의 체

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * BOJ 2960
 * https://www.acmicpc.net/problem/2960
 */
public class Eratosthenes_2960 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split("\\s");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);

        int answer = eratosthenes(new boolean[n+1],k);
        System.out.println(answer);
    }

    private static int eratosthenes(boolean[] input, int k){
        List<Integer> answer = new ArrayList<>();
        int cnt =0;
        for(int i=2; i<input.length; i++){
            if(input[i] == false) { // 안 지워진 경우
                answer.add(i);
            }
            for(int j=2*i; j<input.length; j+=i){ // j=i*i로 하면 stackoverflow 발생할 수 있다
                if(input[j] == false)
                    answer.add(j);
                input[j] = true; // 지워진 경우
            }
        }
        return answer.get(k-1);
    }
}

Comment Read more

BOJ 1934번 최소공배수

26 Dec 2019 | Algorithm

최대 공약수 (GCD)

두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.
최대공약수가 1인 두 수를 서로소라고 한다

2부터 min(A,B)까지 모든 정수로 나눈다

int g =1;
for(int i=2; i<=min(A,B); i++){
  if(a%i == 0 && b % i ==0){
    g=i;
  }
}

유클리드 호제법

A를 B로 나눈 나머지를 r이라 했을때 GCD(A,B) = GCD(B,r)

public void int gcd(int a, int b){
  if(b==0)
    return a;
  else
    return gcd(b,a%b);
}

최소공배수 (LCM)

두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수
LCM = (A*B)/GCD

package BOJ;

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

/**
 * BOJ 1934
 * https://www.acmicpc.net/problem/1934
 * LCD * GCD = A * B
 */
public class LCD_1934 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] answer = new int[n];
        int idx = 0;
        while(n-- > 0){
            int[] numbers = Arrays.asList(br.readLine().split("\\s")).stream().mapToInt(Integer::parseInt).toArray();
            int lcd = (numbers[0] * numbers[1]) / gcd(numbers[0],numbers[1]);
            answer[idx] = lcd;
            idx++;
        }

        for(int num : answer)
            System.out.println(num);


    }

    private static int gcd(int a, int b){
        if(b == 0)
            return a;

        return gcd(b, a%b);

    }


}

Comment Read more

jayyhkwon의 개발공부로그

다이나믹 프로그래밍

다이나믹 프로그래밍

BOJ 9613번 GCD 합

BOJ 6588번 골드바흐의 추측

BOJ 2960번 소수(에레토스테네스의 체)

소수

BOJ 1934번 최소공배수

최대 공약수 (GCD)

최소공배수 (LCM)