[백준/종만북] 2주차(5/6~5/12) - 동적 계획법(Dynamic Programming)

OOING·2023년 5월 12일

백준+알고리즘 공부

목록 보기

5/75

📍 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(a.k.a. 종만북)>으로 공부한 내용을 정리한 게시글입니다.
📍 ChatGPT에게 추천 받은 분할 정복 문제 3개

동적 계획법(Dynamic Programming)

주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산

❔ 분할 정복과의 차이점

분할 정복 : 나눠진 각 문제들이 서로 연관이 없음 -> 재귀 이용

동적 계획법 : 나눠진 각 문제들이 같은 부분 문제(overlapping subproblems)에 의존 -> 중복 계산을 줄이기 위해 메모리(캐시)에 저장

✔️ 동적 계획법을 이용하면 계산의 중복을 줄일 수 있음

이항 계수(binomial coefficient) 계산

이항 계수 nCk : n개의 서로 다른 원소 중에서 r개의 원소를 순서 없이 골라내는 방법의 수

재귀 함수 호출

int bino(int n, int r) {
	if(r == 0 || n == r) return 1;
    return bino(n-1, r-1) + bino(n-1, r);
}

재귀 호출을 하는 경우 같은 파라미터를 갖는 함수가 여러번 호출됨

메모이제이션

이항 계수 계산에 메모이제이션 적용

int cache[30][30];	// -1로 초기화

int bino2(int n, int r) {
	if(r == 0 || r == n) return 1;
    if(cache[n][r] != -1 ) return cache[n][r];
    return cache[n][r] = bino2(n-1, r-1) + bino2(n-1, r);
}

메모이제이션을 적용하면 모든 부분 문제가 한 번씩만 계산됨을 보장
메모이제이션은 참조적 투명 함수(referential transparent function)의 경우에만 적용 가능

참조적 투명 함수 : 함수의 반환 값이 그 입력 값으로만 결정되는 함수(입력이 고정되어 있을 때 그 결과가 항상 같은 함수)

구현 패턴

항상 기저 사례를 먼저 처리
함수의 반환 값이 항상 0 이상이므로 cache[]를 모두 -1로 초기화 (함수의 반환 값이 음수일 수 있는 경우는 사용 X)
ret은 cache[a][b]의 참조형 int& ret = cache[a][b];
memset()을 이용해 cache[]를 초기화 memset(cache, -1, sizeof(cache));

최적화 문제

최적 부분 구조(optimal substructure) : 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 얻어낼 수 있음

1463 1로 만들기

#include <iostream>
using namespace std;

int cache[1000002];	// cache[n]으로 만드는 연산의 최소 횟수
int n;

int dp(int x) {
	for (int i = 2; i <= x; i++) {
		cache[i] = cache[i - 1] + 1;
		if (i % 3 == 0) cache[i] = min(cache[i], cache[i / 3] + 1);
		if (i % 2 == 0) cache[i] = min(cache[i], cache[i / 2] + 1);
	}

	return cache[x];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	cout << dp(n);
}

어우 대충 공부하고 풀려니까 생각이 너무 안 난다 심지어 전에 풀어봤던 문제인데도!! x에서 시작해서 1로 만들려고 했는데, 최솟값에 자꾸 0이 섞여들어가서 제대로 답이 나오지 않았다.. 나중에 생각해봐야지

11726 2xn 타일링

#include <iostream>
using namespace std;

int cache[1002];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	cache[1] = 1;
	cache[2] = 2;

	for (int i = 3; i <= n; i++)
		cache[i] = (cache[i - 1] + cache[i - 2]) % 10007;

	cout << cache[n];
}

점화식 cache[i] = cache[i-1] + cache[i-2]

그런데 이걸 10007로 나누지 않아서 틀렸다. int 범위 조심할 것!

2156 포도주 시식

#include <iostream>
#include <algorithm>
using namespace std;

int cache[10002];
int wine[10002];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> wine[i];
	}

	cache[1] = wine[1];
	cache[2] = cache[1] + wine[2];

	for (int i = 2; i <= n; i++) {
		cache[i] = max({ cache[i - 1], cache[i - 2] + wine[i], cache[i - 3] + wine[i - 1] + wine[i] });
	}

	cout << cache[n];
}