[Algorithm] 동적 계획법 (Dynamic Programming) #230203

본 게시글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)"의 내용을 참고하여 기재하였습니다. 

동적 계획법이란 ? 

동적 계획법은 분할 정복과 유사하지만, 이미 계산한 값을 중복해서 계산하지 않기 위해 따로 저장하는 메모이제이션 기법을 사용했다는 것이 주요 특징이다.

이 기법은 참조적 투명성을 가지고 있는 함수에 대해서 적용된다. 같은 입력이 들어왔을 때 항상 같은 출력을 반환한다는 것이다.

 

유의사항

(1) 입력이 정해진 범위를 벗어난 경우 등을 기저 사례로 처리하여 cache에 저장하기
(2) cache의 초기값을 -1과 같은 수로 두고 -1이 아니라면 이미 계산된 값이라 생각한다.
(3) 저장된 값을 반환하여 담는 ret변수는 &를 사용해서 “별칭”으로 선언한다. 이는 cache의 값을 그대로 가져오기 때문에, ret의 값을 바꾸면 cache의 값도 바뀌게 된다.

 

메모이제이션 기법을 이용해 nCr을 계산하는 함수

#include <iostream>

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

시간 복잡도 계산

(존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

 

문제 : 외발 뛰기 문제

algospot.com :: JUMPGAME

int n;
int board[100][100];

bool jump(int y, int x) {
    if (y >= n || x >= n)
        return false;
    if (y == n - 1 && x == n - 1)
        return true;

    int jumpSize = board[y][x];
    return jump(y + jumpSize, x) || jump(y, x + jumpSize);
}

이 코드는 같은 함수가 여러번 호출되어 중복이 발생한다는 문제점이 있다.

0과 1만을 반환하는 함수에서 int형을 반환하는 함수로 바꿔, 0과 1 이외에도 -1을 반환하는 케이스 (계산되지 않은 함수인 경우) 를 만든다.

int n;
int board[100][100];
int cache[100][100];

bool jump(int y, int x) {
    if (y >= n || x >= n)
        return false;
    if (y == n - 1 && x == n - 1)
        return true;

    int& ret = cache[y][x];
    if (ret != -1)
        return ret; 

    int jumpSize = board[y][x];

    return ret =  (jump(y + jumpSize, x) || jump(y, x + jumpSize));
}

 

 

문제 : 와일드 카드

각 파일들과 주어진 문자열을 비교하는 문제

   

(접은글) 내가 푼 방식

*를 다루는 게 많이 헷갈린다. 아래 네 가지 경우를 핸들링해야된다고 생각하여 문제를 풀었다.

(1) *p* : hapa, hopp, aaapaaa ..

(2) *p : hapa, hopp, aaap ..

(3) p* : pasdf, pencil, piona ..

(4) p*p : php, panp, phpinfo

#include <iostream>
#include <string>
#define MAX 50
using namespace std;

void verifyQuestionMark(int i, int n, string input, string files[MAX]) { // input 문자열의 i번째에 물음표가 있고, 파일들은 총 n개다
	bool flag = true;
	for (int file = 0; file < n; i++) {
		for (int k = 0; k < files[file].size(); k++) {
			if (i == k)
				continue;
			if (files[file][k] != input[k])
				flag = false;
		}
		if (flag)
			cout << files[file] << endl; 
	}
}

void verifyStarMark(int i, int n, string input, string files) {
	string target;
	if (i == 0) {  // 가장 처음에 있는 와일드 카드라면
		for (int j = 1; j < input.size(); j++) {
			target += input[j];
			if (input[j] == '*') {
				verifyStarMark(j, n, input, files);
				break;
			}
		}

	}
	else if (i == n-1) { // 가장 마지막에 있는 와일드 카드라면

	}
	else { // 중간에 있는 와일드 카드라면

	}
} 

void match(int n, string input, string files[MAX]) {
	

	for (int i = 0; i < input.size(); i++) {
		string target;

		if (input[i] == '?') {
			verifyQuestionMark(i, n, input, files);
		}
		else if (input[i] == '*') { // *it, it*, *it*
			if (i == 0) { // 제일 앞에 위치해있다면 
				if (input[input.size() - 1] == '*') {
					// 마지막에도 *가 있다면
					target = (1, input.size() -1);
				}
				else { // 앞에만 있는 거라면
					target = (1, input.size());
				}
			}
			else { // 뒤에만 있는 거라면
				target = (0, input.size() - 1);
			}
			for (int j = 0; j < n; j++) {
				if (files[j].find(target) != string::npos) {
					cout << files[i] << endl;
				}
			}
		}
	}
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		string input;
		cin >> input;

		int n; cin >> n;
		string files[MAX];
		for (int i = 0; i < n; i++) {
			cin >> files[i];
		}

		match(n, input, files);
	}
}

 

// 완전 탐색으로 구현
bool match(const string& w, const string& s) {
    int pos = 0;
    // pos가 w와 s의 안에 있고, 계속 일치하는 경우
    while (pos < w.size() && pos < s.size() && (w[pos] == s[pos] || w[pos] == '?'))
        pos++;

    // 대응되지 않아 while문을 나온 경우
    // (1) w를 모두 검사한 경우
    if (pos == w.size())
        return (pos == s.size()); // s를 모두 검사한 경우에만 대응

    // (2) *를 마주한 경우 
    if (w[pos] == '*') {
        // * 이후 문자열 패턴과 일치하는 문자열이 s에 있는 지 확인
        for (int skip = 1; pos + skip < s.size(); skip++) {
            if (match(w.substr(pos + 1), s.substr(pos + skip)))
                return true; 
        }
        return false;
    }
}

수행시간에서 문제는, 마지막에 매칭이 안될지도 모르는 경우에도 skip을 계속 증가시켜가며 * 뒤에 나오는 문자열을 일치시키기 위해 남은 s의 문자열을 계속 match함수를 이용해 검사한다는 것이다. s가 엄청 긴 문자열인 경우에도 말이다.

W를 전체 패턴이라 보고, w를 지금 검사하고 있는 pos이후의 부분 패턴이라고 하자. w는 항상 W 의 접미사이다. 따라서 w의 길이를 알면 w 문자열을 알 수 있다.

w와 s의 시작 위치를 넘기는 것으로 메모이제이션을 구현해보자. 입력을 bool이 아닌 int로 바꾸고, 재귀호출을 사용하되 대응 시 단순히 true를 반환하는 것이 아니라 ret에 대응한다는 정보를 저장하고 반환한다.

int cache[101][101]; // [w][s]의 대응 여부를 저장
// 1이면 대응, 0이면 미대응, -1이면 미검사 

string W, S;

bool matchMemoized(int w, int s) { 
    int& ret = cache[w][s];
    if (ret != -1) // 이미 구한 값이면 그대로 반환
        return ret;

    // 아직 구한 값이 아니면 검사 시작
    while (w < W.size() && s < S.size() && (W[w] == '?' || W[w] == S[s])) {
        w++; s++; 
    }

    if (w == W.size())
        return s == S.size();

    if (W[w] == '*') {
        for (int skip = 0; s + skip <= S.size(); skip++) {
            if (matchMemoized(w + 1, s + skip)) { // 다음 문자열을 비교하여 대응된 경우
                return ret = 1; // ret에 1을 대입 후 반환
            }
        }
        return ret = 0; // 미대응된 경우 0을 대입 후 반환
    }

}

 

최적화 문제들

하나의 답을 찾는 최적화 문제에서 특정 성질이 성립할 경우 단순히 메모이제이션을 적용하는 것보다 더 효율적으로 DP를 구현할 수 있다.

아래 예제에서는 문제를 푸는 과정에서 현재 탐색하고 있는 시점 (y, x)에서, 그 이전에 구했던 최대합 값(sum)이 그 다음 탐색을 하기 위해 불필요하다는 점을 이용해 효율적으로 구현하였다.

예제1 : 삼각형 위의 최대 경로 (TRIANGLEPATH)

삼각형 형태로 숫자들이 입력되었을 때, 맨 위에서 시작해서 아래 혹은 대각선 오른쪽 아래로 내려가는 경우 맨 아래줄까지 닿았을 때 지나간 숫자의 합이 가장 큰 경우? 그리고 그 숫자의 합은?

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX_NUMBER 10 // 100000
using namespace std;

int n, triangle[100][100]; 
int cache[100][100][MAX_NUMBER * 100 + 1];

int path(int y, int x, int sum) {
    if (y == n - 1)
        return sum + triangle[y][x]; // 여기에는 sum 에 마지막 원소까지 더해주며 반환

    int& ret = cache[y][x][sum];
    if (ret != -1)
        return ret;
    sum += triangle[y][x];
    return max(path(y + 1, x, sum), path(y + 1, x + 1, sum));
}

원래 배운대로 메모이제이션을 사용하면 위와 같다.

(1) 제일 아래에 도착했을 때 지난 경로의 sum을 반환하는 기저사례 추가
(2) cache 값을 ret에 담아서 -1이 아닌경우 바로 반환
(3) max 함수를 이용해 그 다음 호출할 값들 후보(재귀호출을 통해 구한다.) 중 더 큰 것을 반환.

⇒ 여기서 알고리즘을 더 효율적으로 할 방법은, 아래로 내려가면서 위에서 구한 sum은 다음 계산에 영향을 끼치지 않는다는 것이다. 따라서 전체 경로의 최대합이 아닌 “부분 경로의 최대합”을 반환하도록 하면 sum을 입력받지 않아 시간 복잡도는 O(2^n)에서 O(n^2)으로 바뀌게 된다.

int n, triangle[100][100];
int cache[100][100];

// 부분 문제에 대한 최대합을 반환한다. 
int path(int y, int x) {
    if (y == n - 1)
        return triangle[y][x];

    int& ret = cache[y][x];
    if (ret != -1) return ret; 

    return max(path(y + 1, x), path(y + 1, x + 1)) + triangle[y][x]; // 현재 거리를 포함해 다음으로 갈 경로 중 값이 더 큰 쪽을 더하여 반환한다. 
}

이를 최적 부분 구조(Optimal substructure)라고 한다.

각 부분 문제의 최적해가 있으면 전체 문제의 최적해를 구할 수 있는 성질이다.

최대 증가 부분 수열 (LIS)

// 완전 탐색을 이용한 구현
int n; // A의 크기

int lis(vector<int>& A) {
    int ret = 0;
    if (A.empty())
        return 0;

    for (int i = 0; i < n; i++) {
        vector<int> B;
        for (int j = i + 1; j < n; j++) {
            if (A[i] < A[j])
                B.push_back(A[j]);
            ret = max(ret, lis(B) + 1); // max(기존 답, A[i]를 포함한 새로운 LIS인 B길이)
        }
    }
    return ret; 
}

여기에서도 마찬가지로, 앞에서부터 탐색하여 i가 j보다 앞에 있고 더 작은 값이라고 해보자 .

j가 뒤에서 더 탐색하며 더 큰 친구 k를 찾더라도 i는 k보다 앞에 있고 더 작은 값이라는 것은 저명한 사실이다.

따라서 여기서도 최적 부분 구조의 개념을 적용할 수 있다.

lis(start) 는 S[start]에서 시작하는 부분 증가수열 중 최대 길이이다.

즉 전체 길이에서 최대길이를 반환하던 기존 코드에서, “현재 시점”을 기준으로 부분 증가 수열 중 최대 길이를 반환하게 되는 것이다.

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX_NUMBER 10 // 100000
using namespace std;

int n;
int cache[100];
int S[100];

int lis(int start) {
    int& ret = cache[start];
    if (ret != -1) return ret;

    ret = 1; // 현재 시점에서 제일 짧은 경우의 길이는 1 이다. (S[start)
    for (int next = start + 1; next < n; next++) {
        if (S[start] < S[next])
            ret = max(ret, lis(next) + 1);
        // 현재 경로와 다음 경로를 비교해서 더 큰 값으로 이동
    }
    return ret; 
}

main 함수에서는 lis(start)를 호출할 때 이 start를 모든 경우에서 시도해주어야 한다.

int main(){
    ... 
    for(int begin = 0; begin < n; begin+}){
        maxLenght = max(maxLength, lis(begin));
}

이를 ‘음의 무한대’개념을 적용해서 단순화하면, 초기값 S[-1] = -무한으로 설정하면 시작위치를 자동으로 정해서 쓸 수 있다.

int n;
int cache[101];
int S[100];

int lis(int start){
    int &ret = cache[start];
    if(ret != -1) return ret;

    ret = 1; 
    for(int next = start + 1; next < n; next++){
        if(start == -1 || S[start] < S[next])
            ret = max(ret, lis(next) + 1); 
    }
    return ret; 
}

 

합친 LIS (JLIS)

두 수열이 주어졌을 때 두 수열을 합치되 모든 수열은 오름차순으로 정렬되어있어야 한다.

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

int cache[101][101];
int n, m;
vector<int> A, B;

// 합친 증가 부분 수열의 최대 길이를 반환
int lis (int i, int j) {
    int& ret = cache[i][j];
    if (ret != -1) return ret;

    int maxElement = max(A[i], B[j]);
    ret = 2;
    for (int ni = i + 1; ni < n; ni++) {
        if (maxElement < A[ni])
            ret = max(ret, lis(ni, j) + 1);
    }
    for (int nj = j + 1; nj < m; nj++) {
        if (maxElement < B[nj])
            ret = max(ret, lis(i, nj) + 1);
    }
    return ret; 
}

int main() {
    int cases; cin >> cases;
    while (cases--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            int temp; cin >> temp;
            A.push_back(temp);
        }
        for (int j = 0; j < m; j++) {
            int temp; cin >> temp;
            B.push_back(temp);
        }

        memset(cache, -1, sizeof(cache));
        cout << lis(0, 0) << endl;

        A.clear(); B.clear();
    }
}

 

원주율 외우기

 

(접은글) 내가 푼 방식 

 

놓친 것 : 문제에서 주어진 조건의 유한성을 발견하지 못했다. 수열은 3, 4, 5 세 길이 중 하나이다. 따라서 for문을 돌릴 때도 3부터 5까지 돌리면 된다

 

#include <iostream>
#include <vector>
#define MAX 10000
#define INF 987654321
using namespace std;

int cache[MAX];
vector<int> input; 

// int a, int b 구간 사이에서의 난이도를 반환
int calDifficulty(int begin, int end) { // A 수열을 포함하는 전체 
	bool flag = false;

	// (1) 모든 숫자가 같은 경우 
	for (int i = begin; i <= end; i++) {
		if (input[i] != input[begin]) // 하나라도 다르면
			flag = true; 
	}
	if (!flag)
		return 1; 

	// 숫자가 등차수열인 경우
	int interval = input[begin + 1] - input[begin];
	for (int i = begin; i < end; i++) {
		if (input[i + 1] - input[i] != interval)
			flag = true;
	}

	if (!flag) {
		if (abs(interval) == 1) // (2) 1씩 단조 증가 혹은 단조 감소하는 경우
			return 2;
		else
			return 5; // (4) 숫자가 등차수열을 이루는 경우
	}

	// (3) 두 개의 숫자가 번갈아가며 나타나는 경우
	for (int i = begin; i < end - 1; i++) {
		if (input[i] == input[i + 2])
			return true;
	}
	if (!flag)
		return 4; 

	// (5) 그 외의 경우
	return 10; 
}

int sol(int start) {

	if (start == input.size())
		return 0; 
		
	int& ret = cache[start];
	if (ret != -1)
		return ret;

	ret = INF;  // 최솟값을 찾는 문제에서 ret의 초기값은 무한대.
	
	for (int len = 3; len <= 5; len++) {
		if (start + len <= input.size()) {
			return ret += min(ret, sol(start + len) + calDifficulty(start, start + len - 1));
		}
	}
	return ret; 
}

 

여기서 주목해야할 점은,

• return ret += min(ret, sol(start + len) + calDifficulty(start, start + len - 1));

이 부분이다. 원래는 저 calDifficulty 부분에 1을 더했었는데 이제는 난이도가 1만 있는게 아니라 경우에 따라 다르므로, 그 경우를 처리하는 함수를 하나 만들어서 1 대신에 주어진 조건에 합당한 수를 더하여 쌓아가는 것이다.

// int a, int b 구간 사이에서의 난이도를 반환
int calDifficulty(int a, int b) { // A 수열을 포함하는 전체 

    string M = N.substr(a, b - a + 1);

    // (1) 모든 숫자가 같은 경우 
    if (M == string(M.size(), M[0]))
        return 1; 

    // 숫자가 등차수열인 경우
    bool progressive = true; 
    for (int i = 0; i < M.size() - 1; i++) {
        if (M[i + 1] - M[i] != M[1] - M[0])
            progressive = false;
    }
    // 등차수열이고 공차가 1 혹은 -1인 경우
    if (progressive && abs(M[1] - M[0]) == 1)
        return 2; 

    bool alternating = true; 
    for (int i = 0; i < M.size(); i++) {
        if (M[i] != M[i % 2])
            alternating = false;
    }

    if (alternating) return 4;
    if (progressive) return 5;

    return 10; 
}

int sol(int start) {

    if (start == N.size())
        return 0; 

    int& ret = cache[start];
    if (ret != -1)
        return ret;

    ret = INF;  // 최솟값을 찾는 문제에서 ret의 초기값은 무한대.

    for (int len = 3; len <= 5; len++) {
        if (start + len <= N.size()) {
            return ret += min(ret, sol(start + len) + calDifficulty(start, start + len - 1));
        }
    }
    return ret; 
}

풀이에서는 vector가 아니라 string을 사용해서 함수 시작시 substr을 만들어서 처리하였다.

Quantization

문제를 푸는 것의 핵심은 재귀 포인트를 찾는 것이다.

그리고 인접한 숫자끼리 정렬해서 s개의 묶음으로 만든다는 아이디어이다.

 

(접은 글)내가 푼 방식

여기까지 아이디어를 빌리고 다음은 내가 구현해보았다 .

quantize에서는 아래 과정을 수행해야한다.

(1) from에서 시작해서 인접한 값을 가지는 숫자들의 구간을 정한다. (이 구간의 크기를 size라고 한다. )
(2) 그 구간에서 최소 오류값을 구하여 지정한다.
(3) 그 다음 구간으로 넘어가서 (1), (2)를 반복하고, 이 값을 모두 더하여 반환한다.
(4) 기저사례 : from + size 가 전체 수열의 끝에 다다르면 작업을 종료한다.

#include <iostream>
#include <algorithm>
#include <vector>
#define INF 987654321
#define MAX 
using namespace std;

vector<int>input;
int n; // 수열의 길이
int s; // 양자화하여 사용할 숫자의 수

int cache[1000]; // from에서 정할 수 있는 최소 오류값

// 양자화 과정에서, 특정 묶음을 지정할 수 있는 최소 오류를 찾아 반환
int minError(int from, int to) {
	int sum = 0; 
	for (int i = from; i <= to; i++) {
		sum += input[i];
	}
	return sum / (to - from + 1);
}

// from에서 시작해서 parts개의 묶음으로 묶는 함수. 
// 최소 오류 제곱합을 반환한다.
int quantize(int from, int parts) {
	int& ret = cache[from];
	if (ret != -1) return ret; 
	if (parts == 0)
		return 0; 

	// size를 매번 확실히 정할 수 없다. 
	// 따라서 size의 크기를 1부터 (자기자신) n-s+1 (제일 끝까지) 탐색하며 제일 적절한 최소 오류를 반환한다. 
	int ret = INF; 
	for (int size = 1; size <= n - s + 1; size++) {
		if (from + size == n)
			return 0; 
		ret = min(ret, minError(from, from + size - 1) + quantize(from + size, parts -1));
	}
	return ret;
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		cin >> n;
		cin >> s; 
		for (int i = 0; i < n; i++) {
			int temp; cin >> temp;
			input.push_back(temp);
		}
		sort(input.begin(), input.end());
		memset(cache, -1, sizeof(cache));
		cout << quantize(0, s) << endl;
	}
	return 0; 
}

minError함수는 책을 참고하여 작성하였다. 미분을 통해 x(최소 오류값)을 구하고 반환하였음.

 

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

const int INF = 987654321;
int n; 
int A[101], pSum[101], pSqSum[101];

int cache[101][11]; // 수열의 from번째 숫자에서 parts개의 묶음을 생성하였을 때 발생하는 최소 오차 제곱의 합

void precalc() {
    sort(A, A + n);
    pSum[0] = A[0];
    for (int i = 0; i < n; i++) {
        pSum[i] = pSum[i - 1] + A[i];
        pSqSum[i] = pSqSum[i - 1] + A[i] * A[i];
    }
}

int minError(int lo, int hi) {
    int sum = pSum[hi] - (lo == 0 ? 0 : pSum[lo - 1]);
    int sqSum = pSqSum[hi] - (lo == 0 ? 0 : pSqSum[lo - 1]);

    int m = int(0.5 + (double)sum / (hi - lo + 1));

    int ret = sqSum - 2 * m * sum + m * m * (hi - lo + 1);
    return ret;
}

int quantize(int from, int parts) {
    if (from == n) return 0;
    if (parts == 0) return INF; 

    int& ret = cache[from][parts];
    if (ret != -1) return ret;
    ret = INF; 
    for (int partSize = 1; from + partSize <= n; partSize++) {
        ret = min(ret, minError(from, from + partSize - 1) + quantize(from + partSize, parts - 1));
    }
    return ret; 
}

책에서는 부분합을 사용해서, 최소 오류 값을 반환하는 과정에 시간 복잡도를 줄였다.

 

내가 놓친 부분은,

(1) size를 반복하는 for문 안에서

    if (from + size == n)
            return 0; 

다음과 같이 썼었는데, 다음 재귀호출에서 if(from == n)으로 검사해주면 되는거라 수정이 필요해보임.

(2) ret을 INF로 쓴 것은 잘했다! min을 구하는 문제에서는 초기값을 INF로 설정해줘야함을 잊지 말 것

(3) for문 조건에서, 괜히 어렵게 for (int size = 1; size <= n - s + 1; size++) 라고 작성했다. 남은 묶음의 수 당 최소 1개의 원소는 남겨줘야 한다고 생각했는데, 실제로는 지금 시작부분에서 수열의 전체 길이를 넘지 않도록 size를 증가해줘가며 더해준다.

 

당연한 거지만 size자체가 아니라 from + size의 값을 제한해줘야해서 조건문에는 from이 반드시 들어가야 한다 . . 그리고 원소를 남겨줄 필요가 없는 이유는 from이 수열의 마지막에서 시작할 수도 있다. 고정된 n-s+1값을 for문의 마지막 size로 두면, 증가하는 from에 맞춰 유동적으로 size를 조절할 수 없다.

 

따라서 이런 DP에서 재귀호출을 할 때는 for문 조건을 “처음부터 끝까지”로 두기를 바란다.

경우의 수와 확률

오버플로우가 생기는 경우 MOD 연산을 이용해 답을 도출한다.

예제 : 타일링 방법의 수 세기

#include <iostream>
#define MAX 101
#define MOD 100000007
using namespace std;

int cache[MAX];

int tiling(int width) { // 2 x width 크기의 사각형을 타일로 덮는 방법을 반환
    if (width <= 1)
        return 1;
    int& ret = cache[width];
    if (ret != -1) return ret;

    ret = (tiling(width - 1) + tiling(width - 2)) % MOD;

    return ret;
}

첫 타일을 세로로 덮는 경우 → 남은 타일의 크기는 n -1

첫 타일을 가로로 2개 덮는 경우 → 남은 타일의 크기는 n-2

따라서 width 가 0이 될 때까지 재귀호출을 반복하는 것이고, 최종적으로 필요한 것은 “총 개수”이므로 모든 재귀호출에서 구한 값을 더해서 값을 도출한다.

예제 : 삼각형 위의 최대경로 개수 세기

(1) 최대 합 경로를 찾는 알고리즘 (8.4 참고)

#include <iostream>
#define MAX 101
using namespace std;

int cache[MAX][MAX]; // (x, y)까지 오는 동안 지난 경로의 합
int map[MAX][MAX];
int n; // 삼각형의 높이

int path(int y, int x) {
    int& ret = cache[y][x];
    if (ret != -1) return ret; 

    // 기저사례 
    if (y == n - 1)
        return map[y][x];

    ret = 0;    
    for (int nx = x + 1; nx < n; nx++) {
        ret  = max(ret, path(y + 1, nx));
    }
    return ret;
}

1차 피드백

여기서 간과한 점은, 경로를 이동할 때 바로 아래 혹은 대각선 오른쪽 아래로만 갈 수 있다는 점이다.

따라서 함수를 아래와 같이 바꾼다.

#include <iostream>
#define MAX 101
using namespace std;

int cache[MAX][MAX]; // (x, y)까지 오는 동안 지난 경로의 합
int map[MAX][MAX];
int n; // 삼각형의 높이

int path(int y, int x) {
    int& ret = cache[y][x];
    if (ret != -1) return ret; 

    // 기저사례 
    if (y == n - 1)
        return map[y][x];

    ret = 0;    
    return ret = max(map[y+1][x], map[y+1][x+1]) + map[y][x];
}

요렇게 하면, 아래로 내려가는 두 가지 선택지 중 큰 것을 선택해서 현재 경로에서 더하여 줄 수 있다!

 

(2) 최대 경로 개수 구하기

특정 최대합을 내는 경로의 개수를 계산한다.

단순한 해결법은, 특정 최대합을 내는 경로를 모두 조사해 같으면 1을 더하는 방식이다. 근데 그렇게 하면 복잡도가 너무 많이 나와서, 최대로 가는 경로를 찾으면서 ret 에 각각의 과정에서 더한 값을 마지막에 반환하는 것이다

#include <iostream>
#define MAX 101
using namespace std;

int cache[MAX][MAX]; // (x, y)까지 오는 동안 지난 경로의 합
int map[MAX][MAX];
int n; // 삼각형의 높이

int countCache[MAX][MAX];
int path(int y, int x);

// (y, x)에서 시작해서 아래로 내려가는 경로 중 최대 경로의 개수를 반환한다. 
int count(int y, int x) {
    if (y == n - 1)
        return 1;

    int& ret = countCache[y][x];
    if (ret != -1) return ret;

    ret = 0; // 모든 경로의 갯수를 세는 것이므로 0으로 세팅
    if (path(y + 1, x + 1) >= path(y + 1, x)) ret += count(y + 1, x + 1);
    if (path(y + 1, x + 1) <= path(y + 1, x)) ret += count(y + 1, x);

    return ret;
}

int path(int y, int x) {
    int& ret = cache[y][x];
    if (ret != -1) return ret; 

    // 기저사례 
    if (y == n - 1)
        return map[y][x];

    ret = 0;    
    return ret = max(path(y + 1, x), path(y+ 1, x+ 1)) + map[y][x];
}

 

예제 : 우물을 기어오르는 달팽이

비 올 확률이 50%라고 했을 때 m일 안에 달팽이가 우물 끝까지 올라갈 확률을 구하자.

여기서는 최적의 해를 구하는 것이 아니라 모든 경우의 수를 구하는 것이므로 cache의 의미는 최적해가 아닌 “해당 조건에서의 총 경우의 수”가 되는 것이다여기서는 모든 날짜에서 모든 경우의 수 (1or2)를 적용해 문제를 풀었다

#include <iostream>
#define MAX 1001
using namespace std;

int n; // 우물의 깊이
int m; 
int cache[MAX]; // days만큼 지났을 때 달팽이가 올라간 높이의 "경우의 수" 

// DP알고리즘 (days만큼 지났을 때 달팽이가 올라간 높이를 계산하여 반환)
int climb(int days, int sum) { // days만큼 지났고, 지금까지 sum만큼 올라간 상태이다.
	int& ret = cache[days];
	if (ret != -1) return ret; 

	// 기저사례 (우물 끝까지 올라간 경우 종료) 
	if (ret >= n)
		return 1;

	ret = 0;
	for (int start = days + 1; start < m; start++) {
		ret = climb(start, sum + 1) + climb(start, sum + 2); 
	}
	return ret;
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		cin >> n >> m; 
		memset(cache, -1, sizeof(cache));
		cout << climb(0, 0) / pow(2, m) << endl;
	}
	return 0;
}

여기서는 모든 날짜에 경우의 수 (1 or 2)를 적용해 문제를 풀었다.

 

실제 답과 비교해보기

 

(1) cache는 2차원 배열을 사용하기

cache배열 구조는 주로 함수의 인자를 따라간다. 여기에서도 달팽이가 days만큼 지났을 때 climbed만큼 올라와 있는 경우, “m일 전까지 높이 n의 우물을 오를 경우의 수”를 구하여야 한다.

결국에는 조건를 정리하는 것이 관건이다.

• days == m인 경우에 종료
• climbed == n인 경우에 종료
• 다음 날에 1미터 올라가거나 2미터 올라가거나 둘 중 하나이다.

#include <iostream>
#define MAX_N 1001
using namespace std;

int n, m;
int cache[MAX_N][2 * MAX_N + 1];

int climb(int days, int climbed) {
    if (days == m)
        return climbed >= n ? 1 : 0;

    int& ret = cache[days][climbed];
    if (ret != -1) return ret;
    return ret = climb(days + 1, climbed + 1) + climb(days + 1, climbed + 2);
}

(2) 위의 조건에 입각해서 코드를 보면,

• days==m과 climbed==n을 충족한 경우에 1을 반환
• for문을 쓸 필요 없이 “다음 날”에 대한 1 혹은 2미터 올라가는 경우의 수를 더해주면 되므로 위와 같이 ret 을 맞춰준다 !

경우의 수를 계산하는 DP 문제에서는 아래와 같은 로직을 사용한다.

(1) 모든 경우를 세는 완전 탐색 알고리즘을 설계한다. 재귀호출을 할 때는 각 호출이 아래 경우 두가지를 위반해서는 안된다.
   - 모든 경우는 유일하다.
   - 이 경우들은 서로 겹치지 않는다.
(2) 이전 조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄인다.
(3) 메모이제이션을 적용한다.

문제 : 비대칭 타일링 (ASYMTILING)

여기서는 대칭/비대칭이 나오게 되는 경우에 대해 알면 된다. 대칭 타일링이 나오게 되는 일정한 규칙을 찾으면 되는데,

(1) n이 짝수인 경우

• 1 1 1 1 혹은 2 2와 같이 정확히 반 갈라져서 양쪽이 같은 경우
• 1 2 1 혹은 1 1 2 1 1 과 같이 가운데가 2이고 나머지 양쪽이 같은 경우

(2) n이 홀수인 경우

• 1 1 1 혹은 2 1 2과 같이 가운데가 1이고 나머지 양쪽이 같은 경우

// 동적 계획법 알고리즘
int asymmetric(int width) {
    if (width % 2 == 1) // 홀수인 경우
        return (tiling(width) - tiling(width / 2) + MOD) % MOD;
    // 짝수인 경우
    int ret = tiling(width);
    ret = (ret - tiling(width / 2) + MOD) % MOD; // 정확히 반 갈라지는 경우
    ret = (ret - tiling(width / 2 - 1) + MOD) % MOD;  // 중간에 타일이 하나 있는 경우
    return ret; 
}

비대칭 타일을 고르고 있기 때문에, 홀수인 경우에는 가운데를 제외하고 양쪽이 같은 경우를 빼준다. 짝수인 경우에는 tiling(width / 2)와 tiling(width/2) -1을 빼서 대칭 타일이 되는 경우를 제외해준다.

 

문제 : 폴리오미노 (POLY)

#include <iostream>
#define MOD 10000000
#define MAX 101
using namespace std;

int n; // 정사각형의 수
int map[MAX][MAX];
int cache[MAX]; // 정사각형이 m개 남았을 때 만들어진 정사각형의 경우의 수

// 현재까지 사용한 정사각형으로 만들어진 세로 단조 폴리오미노의 수
int poly(int m) { // m : 남은 정사각형의 수
	// 기저사례 : 정사각형을 모두 사용한 경우
	if (m == 0) return 1;

	int& ret = cache[m];
	if (ret != -1) return ret;

	ret = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j]) // 이미 정사각형이 있으면
				continue;
			int flag = true ; // 세로 단조임을 나타내는 표시
			for (int k = j - 1; k >= 0; k--) { // 앞의 부분을 탐색
				if (map[i][k]) // 세로 단조 폴리오미노가 아닌 경우
					flag = false;
			}
			if (flag) { // 정사각형을 놓는 경우
				map[i][j] = 1;
				poly(m- 1); // 정사각형을 하나 줄이고 다시 탐색
			}

		}
	}
	return ret;
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		cin >> n; 
		memset(cache, -1, sizeof(cache));
		memset(map, 0, sizeof(map));
		cout << poly(n) << endl;
	}
	return 0; 
}

문제 해결 방법

(1) 각 가로줄마다 몇개의 정사각형을 넣을 지 결정한다. first
(2) 남은 정사각형의 수와 first를 인자에 넣고 재귀호출한다.
(3) 첫 줄에 있는 사각형의 수가 first이고 그 다음 줄의 사각형의 개수가 second라고 하면, 그 두 줄에서 만들 수 있는 세로 단조 폴리오미노의 개수는 first + second -1이다. ⇒ first x poly(n - first, 1) + (first + 1) x poly(n - first, 2)
(4) first가 정해져있다는 가정 하에 second 값을 1부터 n - first까지 증가시켜가며 만들어지는 경우의 수에 poly(n - first, second) 값을 곱하면 된다.
⇒ poly(현재 줄 포함 남은 정사각형 개수, 현재 줄에 있는 정사각형의 수) 이므로 !!!

 

#include <iostream>
#include <cstring>
#define MAX 101
#define MOD 10000000
using namespace std;

int cache[MAX][MAX]; // n개의 정사각형이 남은 경우 첫번째 줄의 정사각형의 수가 first인 경우 

int poly(int n, int first) {
    // 기저사례 : 남은 정사각형의 수와 현재 줄에 넣을 정사각형의 수가 같으면 모두 탐색한 것!
    if (n == first) return 1;

    // 메모이제이션
    int& ret = cache[n][first];
    if (ret != -1) return ret;

    ret = 0; 
    for (int second = 1; second <= n - first; second++) {
        int add = second + first - 1;
        add *= poly(n - first, second);
        add %= MOD;
        ret += add;
        ret %= MOD;
    }
    return ret; 
}    

int main() {
    int cases; cin >> cases;
    while (cases--) {
        int n; 
        cin >> n;
        memset(cache, -1, sizeof(cache));
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            ret += poly(n, i);
            ret %= MOD;
        } 
        cout << ret << endl;
    }
    return 0; 
}

정답 코드이다.

여기서 main의 for문에서 ret을 구하고 MOD를 한번 더 나누지 않아 실패가 떴었다.

 

문제 : 두니발 박사의 탈옥 (NUMB3RS)

(1) p에서 시작한다
(2) 근접한 마을의 개수를 세고 현재  ret 에서 곱한다
(3) 근접한 모든 마을에 가는 for문을 만들어서 경우의 수를 ret에 계속 곱한다.
(4) 원하는 목적지에 도착하면 return으로 재귀호출을 종료한다.

#include <iostream>
#include <vector>
#define MAX_D 101
#define MAX_N 51
using namespace std;

int cache[MAX_D][MAX_N];
int n; // 마을의 수
int d; // 현재 일수
int p; // 교도소가 있는 마을
int t; // 계산할 마을의 수
int map[MAX_N][MAX_N]; // 마을의 연결상태
int vil;  // 확률을 계산하려 하는 마을

// 현재 위치에서 인접해있는 마을들을 반환
vector<int> countAdjacent(int vil) {

	vector<int> adjacents;

	for (int i = 0; i < n; i++) {
		if (map[vil][i])
			adjacents.push_back(i);
	}
	return adjacents;
}

int sumCases(int days, int vil, int target) {

	vector<int> adjas = countAdjacent(vil);
	// 기저사례
	if (days == 0) return adjas.size();

	int& ret = cache[days][vil];
	if (ret != -1) return ret;

	ret = 1;
	for (int i = 0; i < adjas.size(); i++) {
		ret *= sumCases(days - 1, adjas.back(), target);
		adjas.pop_back();
		if (target) {
			return ret;
		}
	}
}

int main() {
	int cases; cin >> cases;
	while (cases--) {
		memset(map, 0, sizeof(map));
		cin >> n >> d >> p;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> map[i][j];
			}
		}
		
		memset(cache, -1, sizeof(cache));
		cin >> t;
		for (int i = 0; i < t; i++) {
			cin >> vil;
			cout << (double)(1 / (double) sumCases(d, p, vil)) << endl;
		}
	}

}

 

메모이제이션을 적용하기 위해서, 아래 세가지 정보만 최소한으로 남기고 전체 경로의 확률이 아닌, 현재 위치에서 시작해서 남은 날짜(days)동안 움직여 q에 도달할 확률을 계산한다.

(1) 현재 위치 (2) 탈옥 후 지난 날짜 (3) 확률

 

⇒ search(int days, int here) : 두니발 박사가 days만큼 지난 날짜에 here에 숨어있다고 할 때, d일에 q 마을에 숨어있을 조건부 확률

⇒ 전체가 아닌 “현재 시점으로부터의 확률”을 구한다는 원칙에 입각하면 조건부 확률을 사용해야하는 것이다.

double search(int days, int here) {
    if (days == d) return (here == vil ? 1.0 : 0.0);

    double& ret = cache[days][here];
    if (ret > -0.5) return ret;  // 초기화된 경우라면

    ret = 0.0;
    for (int there = 0; there < n; there++) { // 모든 마을을 검사
        if (map[here][there]) // 현재 마을과 연결되어있는 마을이라면
            ret += search(days + 1, there) / degree[here]; 
    }
    return ret;
}

현지 위치에서 인접한 모든 마을을 탐색하며 days의 수를 늘려가다가, d일에 vil에 도착할 경우의 수를 구하는 것이 search(days + 1, there)이 부분이다.

여기서 degree[here]을 나눠주면, 이동 가능한 모든 경우에서 조건 (d일에 vil에 도착하는 경우)이 만족하는 경우만 걸러주는 셈이다.

double search(int here, int days) {
    if (days == 0) return (here == p ? 1 : 0);

    double& ret = cache[here][days];
    if (ret > -0.5) return ret;

    ret = 0.0;
    for (int there = 0; there < n; there++) {
        if (map[here][there])
            ret += search(there, days - 1) / degree[there];
    }
    return ret;
}

두니발 박사가 d일 뒤에 vil에 도착했다고 가정하고 거꾸로 접근해보자.

현재 위치에서 다음 인접한 마을로 가야하는 것은 매한가지이다. 달라진 것은,

(1) days가 1씩 줄어든다.

(2) 전날 there에 있다가 오늘 here로 온 확률이므로, 여기로 온 경우의 수 search(there, days -1)에서 degree[there]을 나눠준다.