[이것이 취업을 위한 코딩 테스트다] Chpater 8 - DP

 

---

Chapter 08 - 다이나믹 프로그래밍(Dynamic programming)

 

1. 다이나믹 프로그래밍(동적 계획법)

: 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법

 

1) 피보나치 수열

- 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예

• n번째 피보나치 수 = (n-1)번째 피보나치수 + (n-2)번째 피보나치수
• 단, 1번째 피보나치수 = 1, 2번째 피보나치 수 = 2

 

① 재귀 함수를 사용한 소스코드

int fibo(int x){
    if(x==1 || x==2){
        return 1;
    }
    return fibo(x-1)+fibo(x-2);
}

int main(){
	cout << fibo(4);
}

- 위 방법은 동일한 함수가 반복적으로 호출됨을 확인 할 수 있다.

  예를 들어 f(6)을 호출하는 것도 f(3)이 3번 호출이 된다.

- f(n)에서 n이 커지면 커질수록 반복해서 호출하는 수가 많아진다.

 

👉 dp를 사용하는 경우

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

② 메모이제이션 기법 사용(재귀)

int d[100];
int fibo(int x){
    if(x==1 || x==2){
        return 1;
    }
    if(d[x] != 0) return d[x];
    d[x] = fibo(x-1)+fibo(x-2); //계산 안한 문제
    return d[x];
}

int main(){
	cout << fibo(4);
}

- 한번 구한 정보를 리스트에 담아서 저장하면, 반복적으로 계산하지 않아도 된다.

- 시간복잡도 : O(N)

* f(1)을 구한다음 f(2)를 푸는데 사용되고, f(3)도 그 전 값을 푸는데 사용되는 방식이기 때문에

 

✅ 다이나믹 프로그래밍의 종류

✔️ 탑다운 방식(하향식) : 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식 (위 방식)

✔️ 바텀업 방식 : 반복문을 이용하여 작은 문제부터 답을 도출하는 방식

 

// 바텀 업 방식
long long d[100];
int main() {
	d[1] = 1, d[2] = 2;
	int n = 99;
	for (int i = 3; i < 100; i++) {
		d[i] = d[i - 1] + d[i - 2];
	}
	cout << d[n];
}

 

 

2. 실전문제(C++)

 

1) 1로 만들기

① 풀이 방법 : x가 30000이하이므로, dp 테이블을 만들어서 반복되는 연산을 줄인다.

* int형 배열 최대 사이즈 크기는 25만까지 가능

② 코드

int n, d[30001];
int main() {
	cin >> n;
	for (int i = 2; i < n + 1; i++) {
		d[i] = d[i - 1] + 1;
		if (i % 2 == 0) d[i] = min(d[i], d[i / 2] + 1);
		if (i % 3 == 0) d[i] = min(d[i], d[i / 3] + 1);
		if (i % 5 == 0) d[i] = min(d[i], d[i / 5] + 1);
	}
	cout << d[n];
}

* d[2] = d[1] + 1, d[2] = (d[2], d[1] + 1) 👉 1

  d[3] = d[2] + 1, d[3] = (d[3], d[1]+1)  👉 1

 

2) 개미 전사

① 풀이 방법 : 

왼쪽부터 차례대로 식량 창고를 턴다고 가정할 때, 

i-1번째 식량 찰고를 턴다면 i는 털수 없다.

i-2번째 식량 창고를 턴다면 i는 털수 있다.

따라서 둘중 더 많은 식량을 털수 있는 경우를 선택하면 됨!

② 코드 :

int n, d[100];
vector<int> arr;
int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    d[0] = arr[0];
    d[1] = max(arr[0], arr[1]);
    for (int i = 2; i < n; i++) {
        d[i] = max(d[i - 1], d[i - 2] + arr[i]);
    }
    cout << d[n - 1];
}

 

3) 바닥 공사

① 풀이 방법 : n이 3일 때 바닥을 덮을 수 있는 모든 경우의 수를 생각하여 바텀업 방식으로 점화식을 세우면 된다.

② 코드

int n, d[1001];
int main(void) {
    cin >> n;
    d[1] = 1;
    d[2] = 3;
    for (int i = 3; i <= n; i++) {
        d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796;
        // 796796 숫자로 계속 나눠줘야 함 아니면 값이 너무 커짐
    }
    cout << d[n];
}

 

4) 효율적인 화폐 구성

① 풀이 방법 : 금액 i를 만드는 최소한의 화폐 개수를 ai, 화폐의 단위를 k라고 햇을때

ai-k를 만드는 방법이 존재한 경우, ai = min(ak, ai-k + 1)

ai-k를 만드는 방법이 존재하지 않은 경우, ai = 10001

이 점화식을 모든 화폐 단위에 차례대로 적용하면 된다.

 

* 그리디 알고리즘으로 풀 수 없다. 작은 동전들을 조합하여 다른 해가 나올 수 있기 때문

② 코드

int n, m;
vector<int> arr;
int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    vector<int> d(m + 1, 10001);
    d[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = arr[i]; j <= m; j++) {
            if (d[j - arr[i]] != 10001) {
                d[j] = min(d[j], d[j - arr[i]] + 1);
            }
        }
    }
    if (d[m] == 10001) { 
        cout << -1;
    }
    else {
        cout << d[m];
    }
}