종만북 9장 동적 계획법 테크닉
이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.
➖ 21-07-09
최적화 문제의 실제 답 계산하기
-
모든 부분 문제마다 최적해를 저장하는 방법은 느리고 메모리를 많이 차지한다
-
대개 동적 계획법을 사용하는 코드에서는 실제 답을 계산하는 과정을 별도로 구현한다
최적화 문제 답 계산하기 레시피
-
재귀 호출의 각 단계에서 최적해를 만들었던 선택을 별도의 배열에 저장
-
변도의 재귀 함수를 이용해 이 선택을 떠라가며 각 선택지를 저장하거나 출력
최대 증가 부분 수열 실제로 출력하기
-
choices[i]: 어떤 숫자를 다음 숫자로 선택해야 전체 증가 부분 수열의 길이를 최대화할 수 있는지 기록
-
reconstruct(): choices[]의 겂을 이용해 실제 LIS 재구성
int n;
int cache[101];
int S[100];
int choices[101];
//S[start]에서 시작하는 증가 부분 수열 중 최대 길이 반환
int lis4(int start){
//start = -1로 주어질 수 있기 때문에 cache[start]가 아닌 cache[start+1]사용
int& ret = cache[start+1];
if(ret != -1) return ret;
//항상 S[start]는 있기 떄문에 길이 최하 1
ret = 1;
int bestNext = -1;
for(int next = start + 1; next < n; ++next){
if(start == -1 || S[start]<S[next]){
int cand = lis4(next) + 1;
if(cand > max){
max = cand;
bestNext = next;
}
}
}
//start = -1로 주어질 수 있기 때문에 choices[start]가 아닌 choices[start+1]사용
choices[start + 1] = bestNext;
return ret;
}//S[start]에서 시작하는 LIS를 seq에 저장
void reconstruct (int start, vector<int> & seq){
if(start != -1) seq.push_back(S[start]);
int next = choices[start+1];
if(next != -1) reconstruct(next, seq);
}여행 짐싸기(PACKING)
- 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도가 주어지고
가져가는 물건들의 부피 합이 캐리어의 용량 w이하가 되어야 할 때
최대 절박도 합과 절박도를 최대화할 수 있는 물건들의 목록을 계산하는 프로그램
동적 계획법 알고리즘
- pack(capacity, item) = 캐리어에 용량이 capacity 만큼 남았을 때 item 이후의 물건들을 싸서 얻을 수 있는 최대 절박도의 합
int n, w;
int volume[100], need[100];
int cache[1001][100];
string name[100];
//캐리어에 용량이 capacity 만큼 남았을 때
//item 이후의 물건들을 싸서 얻을 수 있는 최대 절박도의 합 반환
int pack(int capacity, int item){
if(item == n) return 0;
int & ret = cache[capacity][item];
if(ret!= -1) return ret;
//물건 담지 않았을 경우
ret = pack(capacity, item+1);
//물건 담을 경우
if(capacity >= volume[item])
ret = max(ret, pack(capacity - volume[item], item+1) + need[item]);
return ret;
}답 추척하기
-
각 부분 문제에 선택지가 두 개(물건 담는 경우, 물건 담지 않는 경우)밖에 없음
-> 따로 선택을 저장하지 않고도 답을 역추적할 수 있다 -
pack(capacity, item) 부분 문제에서 pack(capacity, item)과 pack(capacity, item+1)이 같은지 비교
-> 같다면 item을 선택하지 않고도 최대 절박도를 얻을 수 있다는 뜻이다
//pack(capacity, item)이 선택한 물건들의 목록을 picked에 저장
void reconstruct(int capacity, int item, vector<int>& picked){
if(item == n) return;
if(pack(capacity, item) == pack(capacity, item+1))
reconstruct(capacity, item+1, picked);
else{
picked.push_back(item);
reconstruct(capacity-volume[item], item+1, picked);
}
}k번째 답 계산하기
모스 부호 사전(MORSE)
-
n개의 정점(-)과 m개의 단점(o)으로 구성된 모든 신호들을 담고있는 사전이 있다 (n, m <= 100)
-
이 신호들은 사전 순서대로 정렬되어 있다
-> 장점(-)의 아스키 코드는 45, 단점(o)의 아스키 코드는 111 -
n과 m이 주어질 때 이 사전의 k번째 신호를 출력하는 프로그램 작성 (k <= 1000000000)
-
모든 신호를 사전순서대로 만드는 완전 탐색 알고리즘
//s: 지금까지 만든 신호
//n: 더 필요한 장점(-)의 개수
//m: 더 필요한 단점(o)의 개수
void generate(int n, int m, string s){
if(n == 0 && m == 0){
cout << s << endl;
return;
}
if(n>0) generate(n-1, m, s+"-");
if(m>0) generate(n, m-1, s+"o");
return;
}- k개 건너뛰기
-> 사전순으로 모든 신호들을 생성하면서 k-1개를 건너뛰고 첫 번째 것 출력
-> 건너뛰어야 할 신호들의 수를 저장하는 전역 변수 skip
//skip은 k-1로 초기화 된다
int skip;
void generate2(int n, int m, string s){
//base case
if(skip < 0) return;
if(n == 0 && m == 0){
if(skip == 0) cout << s << endl;
--skip;
return;
}
if(n>0) generate(n-1, m, s+"-");
if(m>0) generate(n, m-1, s+"o");
return;
}- 좀더 똑똑하게 건너뛰기
-> generate2(n,m,s)가 호출되었을 때 만들 수 있는 신호의 개수: (n+m)C(n)
-> skip이 (n+m)C(n)보다 같거나 크다면 skip만 줄여 버리고 실행 종료
//K의 최댓값 = 1000000000
//오버플로우를 막기 위해 이보다 큰 값은 구하지 않는다
const int M = 1000000000 + 100;
//필요한 이항계수를 미리 계산해둔다
int bino[201][201];
void calcBino(){
memset(bino, -1, sizeof(bino));
for(int i = 0; i <= 200; ++i){
bino[i][o] = bino[i][i] = 0;
for(int j = 1; j<i; ++j)
bino[i][j] = min(M, bino[i-1][j-1] + bino[i-1][j]);
}
return;
}
int skip;
void generate3(int n, int m, string s){
//base case
if(skip < 0) return;
if(n == 0 && m == 0){
if(skip == 0) cout << s << endl;
--skip;
return;
}
if(bino[n+m][n] <= skip){
skip -= bino[n+m][n];
return;
}
if(n>0) generate(n-1, m, s+"-");
if(m>0) generate(n, m-1, s+"o");
return;
}- 좀더 깔끔한 구현
//n개의 -, m개의 o으로 이루어진 신호 중
//skip개를 건너뛰고 만들어지는 신호 반환
string kth(int n, int m, int skip){
//n==0인 경우 나머지 부분은 전부 o일 수밖에 없다
if(n==0) return string(m, o);
if(skip < bino[n+m-1][n-1])
return "-" + kth(n-1, m, skip);
return "o" + kth(n, m-1, skip - bino[n+m-1][n-1])
} k번째 답 계산하기 레시피
-
답들을 사전순서대로 만들며 경우의 수를 세는 완전 탐색 알고리즘 설계하고,
메모이제이션을 적용해 경우의 수를 세는 동적 계획법 알고리즘으로 바꾼다 -
모든 답들을 사전순서대로 생성하며 skip개를 건너뛰고 첫번째 답을 반환하는 재귀 호출 함수 구현
-
재귀 함수는 각 조각에 들어갈 수 있는 값을 하나씩 고려하면서
값을 선택했을 때 만들어지는 답의 수 M과 건너뛰어야할 답의 수 skip 비교 -
M <= skip 인 경우:
-> M개의 답은 우리가 원하는 답보다 앞에 있으므로, 이들을 건너뛴다
-> skip을 M만큼 줄인다 -
M > skip 인 경우:
-> M개의 답 중 우리가 원하는 답이 있으므로, 이 값을 선택한다
-> M개의 답 중 skip개를 건너뛴 것 = 우리가 원하는 답
-> 이 값을 답에 추가하고 재귀 호출로 답의 나머지 부분을 만든다
➖ 21-07-10
정수 이외의 입력에 대한 메모이제이션
연관 배열 사용하기
-
STL의 map과 같은 연관 배열을 사용해 캐시 구현
-
입력으로 정수 배열이 주어진 경우
map<vector<int>, int> cache;
- 계산량이 아주 작은 문제에만 사용할 수 있다
일대일 대응 함수 작성하기
-
입력을 적절하게 정수로 변환해줄 수 있는 일대일 함수(bijection function) 작성
-
ex. 주어지는 정수 배열이 항상 [1,n]범위의 수를 하나씩 가지고 있는 경우(=순열)
-> 가능한 n!개의 입력 배열 중 입력 배열이 사전순으로 몇 번째인지 반환하는 함수 만들기
int cache[N_FACTORIAL];
//n!개의 입력 중 key가 몇 번째에 해당하는지 반환
int mapFunc(const vector<int>& key);
int f(const vector<int>& key){
//base case
...
//메모이제이션
int& ret = cache[mapFunc(key)];
if(ret != -1) return ret;
//답 실제로 계산
...
return ret;
}
입력이 불린값의 배열인 경우
-
배열의 길이가 n이라 할 때 가능한 입력 배열의 종류 2^n개
-> 길이 n인 배열을 길이가 n인 2진수와 일대일 대응시켜 메모이제이션 -
실제로 입력이 불린 값의 배열인 함수를 작성할 때 대부분 아예 배열 대신 정수를 전달하는 함수를 작성
-> 비트마스크를 이용해 배열의 값에 접근
입력이 순열인 경우
-
주어지는 배열 X가 항상 [1, 2, ..., 10]의 순열인 경우
-> 가능한 10!개의 입력들 중 X가 사전순으로 몇 번째 오는지 반환하는 함수 만들기 -
10!의 입력을 사전순으로 나열한 후, 첫번째 자리에 어느 숫자가 오는지를 기준으로 10묶음으로 나눈다
-> 각 묶음마다 9!의 입력 -
ex. X의 첫 번째 숫자가 4인 경우:
-> 세 묶음(첫 번째 숫자가 1, 2, 3인 묶음)이 X 앞에 존재 (= 9! * 3 )
-> + 첫 번째 숫자가 4인 입력 중 X보다 앞에 오는 것을 센다 -
첫 숫자가 4인 입력들을 사전순으로 나열한 후, 두번째 자리에 어느 숫자가 오는지를 기준으로 9묶음으로 나눈다
-> 각 묶음마다 8!의 입력 -
ex. X의 두 번째 숫자가 5인 경우:
-> 세 묶음(첫 번째 숫자가 4이고, 두 번째 숫자가 1, 2, 3인 묶음)이 X 앞에 존재 (= 8! * 3 )
-> + 첫 번째 숫자가 4이고 두 번째 숫자가 5인 입력 중 X보다 앞에 오는 것을 센다
//factorials[i] = i!
int factorials[12];
//X가 [0, .., n-1]의 순열일 때 사전순 번호를 반환 (0에서 시작)
int getIndex(const vector<int>& X){
int ret = 0;
for(int i = 0; i<X.size(); ++i){
int less = 0;
//X[i+1, ...] 중 X[i]보다 작은 수를 센다
//이것이 X 앞에 오는 묶음의 수가 된다
for(int j = i+1; j<X.size(); ++j)
if(X[j]<X[i]) ++less;
ret += factorials[X.size() - i - 1] * less;
}
return ret;
}
입력의 범위가 좁을 경우
- 각 위치의 숫자들을 쭉 늘어 놓으면 각 배열은 십진수 하나에 일대일 대응된다
- ex. {4, 0, 1, 7, 2} -> 40172, {0,0,0,0,0} -> 0
- 배열의 길이가 n이고, 배열의 원소가 [0,k-1]의 범위에 들어간다면 -> n자리 k진수
조합 게임
-
동적 계획법의 또 다른 사용처는 조합 게임(combinational game)을 해결하는 것
-> 게임의 상태가 주어졌을 때 완벽한 수를 찾아내는 알고리즘을 만들기 -
마지막 수를 두는 참가자는 항상(그런 수가 있다면) 자신이 이길 수 있는 수를 둘 것이다
마지막 수를 두는 참가자가 지는 경우는 어떤 수를 두더라도 질 수밖에 없는 상태 뿐이다
-> 그러므로 마지막에서 두 번째 줄에 있는 모든 상태들에 대해 어느 쪽이 이길지 판단할 수 있다 -
해결할 수 없는 게임의 경우:
-> 각 상태에서 둘 수 있는 수가 너무 많고 게임이 종료하기까지 둬야하는 수가 너무 많은 경우
-> 지난 상태로 다시 돌아갈 수 있는 게임의 경우
위에서 내려가기
-
흔히 위에서부터 내려오는(top down) 재귀 호출 알고리즘으로 구현
-
winner(state, player): 게임의 현재 상태가 state이고, player가 수를 둘 차례일 때 어느쪽이 최종적으로 이길까
-
canWin(state) : 게임의 현재 상태가 state일 때, 이번에 수를 둘 차례인 참가자가 이길까?
-> state에서 둘 수 있는 수를 하나 하나 순회하며, 해당 수를 둔 후의 상태 state2에 대해 canWin()호출 -
canWin(state2) = true 라면 다음 차례가 되는 상대방이 이긴다
canWin(state2) = false 라면 다음 차례가 되는 상대방이 진다
-> canWin(state2) = false를 반환하게 하는 수가 하나라도 있다면 이 상태에서 자신이 이길 수 있다
메모이제이션
- 한 정점에 도달할 수 있는 경로 여러가지
-> 같은 state에 대해 canWin()을 여러번 호출
-> 메모이제이션을 시용한다
틱택토(TICTACTOE)
-
틱택토 게임판 상태: vector board
-> 아홉자리의 3진수 숫자로 일대일 대응시켜 메모이제이션 -
canWin(board): 틱택토 게임판이 현재 board일 때 이번 차례인 사람이 이길 수 있으면 1, 비길 수 있으면 0, 질 수 밖에 없으면 -1을 반환한다
//turn이 한 줄을 만들었는지 반환
bool isFinished(const vector<string>& board, char turn);
//틱택토 게임판이 주어질 때 [0, 19682]범위의 정수로 변환 (3^9 = 19682)
int bijection(const vector<string>& board){
int ret = 0;
for(int y = 0; y<3; ++y)
for(int x = 0; x<3; ++x){
ret = ret * 3;
if(board[y]][x] == 'o') ++ret;
else if(board[y][x] == 'x') ret += 2;
}
return ret;
}
//cache[]는 -2로 초기화
//memset()을 통해 초기화항 수 없으므로 for문으로 직접 초기화해야
int cache[19683];
//내가 이길 수 있으면 1, 비길 수 있으면 0, 지면 -1 반환
int canWin(vector<string>& board, char turn){
//base case: 마지막에 상대('o'+'x'-turn)가 둬서 한 줄이 만들어진 경우
if(isFinished(board, 'o'+'x'-turn)) return -1;
int& ret = cache[bijection(board)];
if(ret != -2) return ret;
int minValue = 2;
for(int y = 0; y<3; ++y)
for(int x = 0; x<3; ++x){
if(board[y][x] == '.'){
//모든 반환 값의 min을 취함
//canWin((board, 'o'+'x'-turn) = -1 또는 0을 반환하게 하는 turn이 하나라도 있다면
//이 상태에서 자신이 이기거나 비길 수 있다
board[y][x] = turn;
minValue = min(minValue, canWin(board, 'o'+'x'-turn));
board[y][x] = '.';
}
}
//플레이할 수 없거나 어떻게 해도 비기는 것이 최선인 경우
if(minValue == 2 || minvalue == 0) return ret 0;
//최선이 상대가 이기는 것이라면 난 무조건 지고, 상대가 지는 것이라면 난 이긴다
return ret = -minValue;
}-
더 빠르게 구현하기
-> 틱택토 게임판을 좌우, 상하, 혹은 대각선으로 뒤집거나 90도 회전해도 게임의 결과 변하지 않는다 -
양쪽이 완벽하게 플레이할 경우 항상 비길 수 밖에 없다
숫자 게임(NUMBERGAME)
규칙
-
n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 한다
-
게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있다
-> 게임판의 왼쪽 끝이나 오른쪽 끝에 있는 숫자 중 하나를 가져간다. 가져간 숫자는 게임판에서 지워진다
-> 게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 두 개, 혹은 오른쪽 끝에서 두 개의 숫자를 지운다 -
게임은 모든 숫자가 다 없어졌을 때 끝나며, 각 사람의 점수는 자신이 가져간 숫자들의 합이다
-
두 사람 모두 최선을 다할 때, 두 사람의 최종 점수 차이는 얼마일까?
풀이
-
각 사람이 이기냐 지냐만이 중요한 것이 아니라 얼마나 큰 점수차이로 이기느냐도 중요하다
-
play(state): 현재 게임판에 남은 수들이 state일때 (이번 차례인 참가자의 점수) - (다음 차례인 참가자의 점수)의 최대치
-> 게임판의 왼쪽 끝 숫자를 가져가는 경우: board[left] - play(left +1, right)
-> 게임판의 오른쪽 끝에 있는 숫자를 가져가는 경우: board[right] - play(left, right-1)
-> 게임판의 왼쪽 끝에서 두 개의 숫자를 지우는 경우: 0 - play(left+2, right)
-> 게임판의 오른쪽 끝에서 두 개의 숫자를 지우는 경우: 0 - play(left, right-2)
const int EMPTY = -987654321;
int board[50];
int cache[50][50];
int play(int left, int right) {
//base case
if (left > right) return 0;
int& ret = cache[left][right];
if (ret != EMPTY) return ret;
//수를 가져가는 경우
ret = max(board[left] - play(left + 1, right), board[right] - play(left, right - 1));
//수를 없애는 경우
if (right - left + 1 >= 2) {
ret = max(ret, -play(left + 2, right));
ret = max(ret, -play(left, right - 2));
}
return ret;
}⚡미니맥스 알고리즘
-
재귀 함수의 정의를 다음과 같이 바꾸어 보자
player(state, player): 현제 게임판에 남은 수들이 state라고 가정하고, 이번 차례가 player라고 할 때 (현우 점수)-(서하 점수) -
현우는 play()의 반환값을 가능한 한 최대화하고, 서하는 최소화하는 쪽으로 게임을 하게 된다
-> 게임 트리의 각 층마다 번갈아가면서 최대화(maximaize)와 최소화(minimize)
-
이 경우 player에 따라 반환값이 달라지고, 부분 문제의 수가 두 배 늘어난다
#include <iostream>
#include <algorithm>
using namespace std;
const int EMPTY = -987654321;
int board[50];
int cache[50][50][2];
//현우: player = 0
//서하: player = 1
int play(int left, int right, int player) {
//base case
if (left > right) return 0;
int& ret = cache[left][right][player];
if (ret != EMPTY) return ret;
//현우 차례인 경우: (현우의 점수) - (서하의 점수) 최대화
if (player == 0) {
//수를 가져가는 경우
ret = max(board[left] + play(left + 1, right, 1), board[right] + play(left, right - 1, 1));
//수를 없애는 경우
if (right - left + 1 >= 2) {
ret = max(ret, play(left + 2, right, 1));
ret = max(ret, play(left, right - 2, 1));
}
}
//서하 차례인 경우: (현우의 점수) - (서하의 점수) 최소화
else if (player == 1) {
//수를 가져가는 경우
ret = min(- board[left] + play(left + 1, right, 0), - board[right] + play(left, right - 1, 0));
//수를 없애는 경우
if (right - left + 1 >= 2) {
ret = min(ret, play(left + 2, right, 0));
ret = min(ret, play(left, right - 2, 0));
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int c;
cin >> c;
while (c--) {
//캐시 초기화
for (int i = 0; i < 50; ++i)
for (int j = 0; j < 50; ++j) {
cache[i][j][0] = EMPTY;
cache[i][j][1] = EMPTY;
}
int n;
cin >> n;
for (int i = 0; i < n; ++i)
cin >> board[i];
cout << play(0, n - 1, 0) << endl;
}
return 0;
}
➖ 21-07-11
반복적 동적 계획법
- 부분 문제 간의 의존성을 파악하기 쉬운 경우 반복문을 통해 동적 계획법 구현 가능
삼각형 위의 최대 경로
-
점화식:
path2(y, x) = triangle [y,x] + max(path2(y+1, x), path2(y+1, x+1)) -
맨 아랫줄부터 path2()의 값을 계산하면서 올라가면 계산하는 데 필요한 값들을 항상 가지고 있게 된다
int n, triangle[100][100];
int C[100][100];
int iterative(){
//base case:
for(int x = 0; x<n; ++x)
C[n-1][x] = triangle[n-1][x];
//다른 부분 계산
for(int y = n-1; y >= 0; --y)
for(int x = 0; x < y+1; ++x)
C[y][x] = triangle [y,x] + max(C[y+1][x], C[y+1][x+1]);
return C[0][0];
}슬라이딩 윈도를 이용한 공간 복잡도 줄이기
-
슬라이딩 윈도(sliding window): 사용하는 데이터 전체를 메모리에 유지하는 것이 아니라 필요한 부분만을 저장하는 기법
-
새 값을 계산할 때 과거에 계산한 결과가 전부 필요한 것이 아니라 일부분만이 필요할 때 사용
int n, triangle[100][100];
int C2[2][100];
int iterative(){
//base case:
for(int x = 0; x<n; ++x)
C[(n-1)%2][x] = triangle[n-1][x];
//다른 부분 계산
for(int y = n-1; y >= 0; --y)
for(int x = 0; x < y+1; ++x)
C[y%2][x] = triangle [y,x] + max(C[(y+1)%2][x], C[(y+1)%2][x+1]);
return C[0][0];
}반복적 동적 계획법과 재귀적 동적 계획법의 비교
-
재귀적 동적 계획법의 장점:
-> 좀더 직관적인 코드
-> 부분 문제 간의 의존 관계나 계산 순서에 대해 고민할 필요 X
-> 전체 부분 문제 중 일부의 답만 필요할 경우 더 빠르게 동작 -
재귀적 동적 계획법의 단점:
-> 슬라이딩 윈도 기법을 쓸 수 없다
-> 스택 오버플로우 조심해야 -
반복적 동적 계획법의 장점:
-> 구현이 대개 더 짧다
-> 재귀 호출에 필요한 부하가 없기 때문에 조금 더 빠르게 동작한다 -
반복적 동적 계획법의 단점:
-> 구현이 좀더 비직관적이다
-> 부분 문제 간의 의존 관계를 고려해 계산되는 순서를 고민해야 한다
