Im4u 봄방학캠프 DAY 4; Discrete Optimization Problems #4 Dynamic Programming (II) 구종만 jongman@gmail.com
오늘할얘기 최적화문제의답안생성하기 다른형태의동적계획법문제들 계산게임 지수크기상태공간을갖는문제들 선형변환형태의점화식을갖는문제들 이론적배경 Optimal Substructure (.. 하지만슬라이드 50 장돌파해서이건생략 )
Longest Increasing Subsequence 7 6 10 12 8 9 7 12 14 11 단조증가하는부분수열을구하고싶다 일단은해당수열의 길이 만을찾아봅시다 O( n 2 ) 의답을찾아봅시다
Think-Path 지금까지본문제와는스타일이약간달라요 ~ 답이어디서시작할지, 끝날지를모름 당장동적계획법으로찾으려면막막할수있음 늘그렇듯이 Brute-Force 에서시작해봅시다 어떤재귀호출방법을써야모든답안을다만들어볼수있을까요?
모든답안을만들어보자 두가지방법이있을듯 : try _ subsequence( last _ number, current _ index) current_index 7 6 10 12 8 9 7 12 14 11 last_number try _ subsequence( last _ number _ index) 7 6 10 12 8 9 7 12 14 11 last_number_index 어느쪽이더동적계획법에적합해보이나? 왜?
당연히두번째죠 첫번째점화식을동적계획법으로바꾸려면주어지는숫자의크기에비례하는배열이있어야하죠 다른테크닉으로이방법을사용할수도있지만여전히더느립니다. 두번째점화식은 C i =i n C = 1 i C O( n 2 ) 에구현가능 ^_^ 번째수에서시작하는 LIS 의길이 max j= i+ 1, A j > A i j + 1 답은? maxc i
구현해봅시다 int n, A[100]; int cache[100]; int go(int here) { int& ret = cache[here]; if(ret!= -1) return ret; ret = 1; for(int there = here+1; there < n; ++there) if(a[here] < A[there]) ret = max(ret, go(there) + 1); return ret; } int ret = 0; for(int i = 0; i < n; ++i) ret = max(ret, go(i)); 처음으로 C++ 의 reference variable 을쓴코드 ( 이테크닉꽤나유용합니다 )
실제해계산하기 길이를구하기는쉬웠는데, 실제수열을출력하라면어떻게해야하나? 방법 1: 길이를저장하는대신, 수열을직접저장 int n, A[100]; vector<int int> cache[100]; vector<int int> go(int here) { vector<int int>& ret = cache[here]; if(!ret.empty()) return ret; ret.push_back(a[here]); for(int there = here+1; there < n; ++there) if(a[here] < A[there]) { vector<int int>& cand = go(there); if(cand.size() + 1 > ret.size()) { ret.clear(); ret.push_back(a[here]); ret.insert( cand.begin begin(), cand.end end() ); } } return ret; }
재귀적으로해계산하기 C14 = maxci = 14 였다고하자. 이값은어떻게14 가되었을까? 14 오른쪽에 A j > A 14 이고, Cj = 14 인 j 가존재 A C 12 17 10 4...... >4.... 8 6 9 14...... 13.... 이것을찾는일을반복하자
반복적 (Iterative) 으로찾기 int n, A[100]; int cache[100]; int bestindex = 0; for(int i = 1; i < n; ++i) if(go(bestindex) < go(i)) bestindex = i; do { printf("%d ", A[bestIndex]); for(int i = bestindex+1; i < n; ++i) if(go(i) + 1 == go(bestidex) && A[bestIndex] < A[i]) { bestindex = i; break; } } while(a[bestindex] > 1); printf("\n"); 반복적으로다음위치를찾아나간다
재귀적으로찾기 int n, A[100]; int cache[100]; void printbest(int here) { printf("%d ", A[here]); if(cache[here] > 1) for(int there = here+1; there < N; ++there) if(cache[there]+1 == cache[here] && A[there] > A[here]) { printbest(there); break; } } for(int i = 1; i < n; ++i) if(go(bestindex) < go(i)) bestindex = i; printbest(bestindex); 경험적으로는재귀적으로짜는편이좀더좋다
Lexicographically Smallest Solution 주어진수열의 LIS 중, 사전순으로가장앞에있는것을계산하라 5 6 7 8 9 1 2 3 4 5
Lexicographically Smallest Solution 주어진중복이없는수열의 LIS 중, 사전순으로가장앞에있는것을계산하라 6 7 8 9 10 1 2 3 4 5 C i = maxc 인i 가하나라면문제없다. 여러개라면어떻게할까? 숫자가 ( 클 / 작을 ) 수록좋다!
Lexicographically Smallest Solution 주어진중복이없는수열의 LIS 중, 사전순으로가장앞에있는것을계산하라 6 7 8 9 10 1 2 3 4 5 C i = maxc 인i 가하나라면문제없다. 여러개라면어떻게할까? 숫자가 ( 클 / 작을 ) 수록좋다!
K-th Smallest Solution 주어진수열의 LIS 중, 사전순으로 k 번째에있는것을계산하라 K=3 1 5 2 6 3 7 4 8 5 9 답의수는감당하기힘들정도로커질수있다. 2 1 4 3 6 5 8 7 10 9 따라서, Brute-Force 로는안된다!
또한번의동적계획법 가장좋은답의 길이 말고도, 가장좋은답을만들수있는방법의수또한별도로계산해서저장 C i =i D i =i = 번째수에서시작하는 LIS 의길이 번째수에서시작하는LIS 의수 j= i+ 1, A j n 1 Σ > A, C i j + 1== C i D j 이걸가지고어떻게답을만들수있을까?
생각하기나름이겠지만 전이방법이가장쉽더군요 K 번째답 (1-based) 그앞에 k-1 개의답이있는것중사전순으로가장앞에있는답 (0-based) intskip = k 1;
그렇게생각하면 7 8 9 4 5 6 1 2 3 C i = maxc 인i 가여러개있다고합시다 이들을줄세워보면 1 에서시작하는것들이맨앞에 7 에서시작하는것들이맨뒤에 가겠지요.. 1.......... 1............. 4.......... 4............. 7.......... 7..........
첫번째숫자만맞춰봅시다 A[] D[] 7 8 9 4 5 6 1 2 3 7 12 15 If skip = 0? If skip = 20? If skip = 30? If skip = 15?
첫번째숫자만맞춰봅시다 A[] D[] 7 8 9 4 5 6 1 2 3 7 12 15 If skip = 0? 1 If skip = 20? 4 If skip = 30? 7 If skip = 15? 4
Skip=20 의예 skip=20 1.......... 1.......... 1.......... 1.......... 1............. 1.......... 1.......... 4.......... 4.......... 4............. 4.......... 4.......... 7.......... 7............ D[6]=15 new_skip=5
Skip=20 의예 skip=20 1.......... 1.......... 1.......... 1.......... 1............. 1.......... 1.......... 4.......... 4.......... 4............. 4.......... 4.......... 7.......... 7............ D[6]=15 new_skip=5
코드 int n, A[100], C[100], D[100]; void printafterskip(int begin, int skip) { printf("%d ", A[begin begin]); if(c[begin begin] == 1) return; // (A[index], index) 의쌍 vector<pair<int int, int> > nextcandidates; for(int i = begin+1; i < n; ++i) if(a[begin begin] < A[i] && C[i]+1 == C[begin begin]) nextcandidates.push_back(make_pair(a[i], i)); sort(nextcandidates.begin begin(), nextcandidates.end end()); } for(int i = 0; i < nextcandidates.size(); ++i) if(skip >= D[nextCandidates[i].second) skip -= D[nextCandidates[i].second]; else { printafterskip(nextcandidates[i].second, skip); break; }
TheDictionary 알파벳 a 와 z 만으로구성된문자열들 a 의개수는 n 개, z 의개수는 m 개라고하자. 이들을사전순으로정렬했을경우, k 번째에오는문자열은무엇일까? TopCoder SRM428 Div2 Hard
Counting 이산구조시간에배우셨겠죠? C(n,m) = ncm= 이항계수 (binomial coefficient) aazz azaz azza zaaz zaza zzaa C(n,m) = C(n-1,m-1) + C(n-1,m)
첫글자를결정해보자 C(n,m) aaaaaaazzzzzzzz aaaaaazazzzzzzz... azzzzzzzzaaaaaa zaaaaaaazzzzzzz zaaaaaazazzzzzz... zzzzzzzzaaaaaaa C(n-1,m) C(n,m-1)
배스킨라빈스 31 두명의사람이배스킨라빈스 31 을한다. 한사람은한개 ~ 여섯개의숫자를부를수있다. 한게임에서같은숫자는최대네번만부를수있다. 게임의현재진행상황이주어진다. 1123656 양쪽이 완벽하게 플레이한다고할때, 이게임의승자는?
완벽하게 의정의 상대방이어떻게플레이하더라도, 내가적절히반응하면승리할수있다 => 승리 내가어떻게플레이하더라도, 상대방이적절히반응해나를지게만들수있다 => 패배
Recurrence 게임의 상태 가주어질때, 게임의승패를결정하는함수를정의하고, 이함수를점화식으로나타낸다 F(state) = 현재상태에서, 이번차례인사람이반드시승리할수있는방법이있는가? WIN WIN LOSE? WIN? WIN? LOSE WIN LOSE LOSE
배스킨라빈스 31: 상태공간 Key Observation: 각숫자가어떤 로나왔는지는상관이없다 각숫자가나온 만이중요하다
배스킨라빈스 31: 상태공간 Key Observation: 각숫자가어떤 _ 순서 _ 로나왔는지는상관이없다 각숫자가나온 _ 횟수 _ 만이중요하다 따라서, 각숫자마다0,1,2,3,4 의상태: 5^6 = 15,625 개의상태 Quite manageable! 각상태마다할수있는행동을다해본다 어떤행동을해도내가진다면패배, 하나라도이긴다면승리
배스킨라빈스 31: 코드 map<vector<int int>, int> cache; int willwin(vector<int int>& used, int total) { if(total >= 31) return 1; if(cache.count(used)) return cache[used]; int& ret = cache[used]; for(int i = 1; i <= 6; ++i) if(used[i-1] < 4) { used[i-1]++; if(!willwin(used, total+i)) ret = 1; used[i-1]--; } return ret; } std::map 을이용한간단한 memoization!
A Game 짝수길이의게임판, 두사람의플레이어 7 8 9 4 5 6 1 2 3 5 왼쪽끝이나오른쪽끝의숫자를번갈아가며먹는다 먹은수의총합이해당플레이어의점수 ( 내점수 ) ( 상대점수 ) 를최대화할수있는방법은? IOI 96 Day 1 Task 1
A Game: 상태공간 7 8 9 4 5 6 1 2 3 5 7 8 9 4 5 6 1 2 3 5 7 8 9 4 5 6 1 2 3 5 7 8 9 4 5 6 1 2 3 5 7 8 9 4 5 6 1 2 3 5 7 8 9 4 5 6 1 2 3 5 게임의상태는왼쪽끝칸과오른쪽끝칸으로정의할수있다 : O( n 2 ) 개의상태
Minimax Algorithm f (state) = 현재상태에서첫번째플레이어의점수 두번째플레이어의점수 = f (state) 따라서, 우리점수를최대화하려면상대의점수를최소화해야한다 f ( state) = max f ( nxt) + nxt next( state) Cost( nxt)
A Game: 코드 int n, A[100]; int cache[100][100]; int go(int left, int right) { if(left > right) return 0; int& ret = c[left][right] if(ret!= -1) return ret; return ret = max( -go(left+1, right) + A[left], -go(left, right-1) + A[right] ); } go(left+1, right), go(left, right+1) 는상대방의점수
DP 가만능은아니다 Chess Endgame analysis King + Rook vs. King + Queen 어느쪽이이길것인가?
Cycles in the Game State
State Space MUST Be A DAG 게임의상태들로구성된공간에사이클이있으면 memoization 을사용할수없다 이경우에는다른방법을사용해야함 ( 생략 ) 사이클이없는그래프 (Directed Acyclic Graph)
Bit of Combinatorial Game Theory Impartial game 두플레이어가할수있는일은완전히똑같고, 현재게임판의상태에만좌우된다 체스나바둑은 Impartial Game 이아니다 Normal game 마지막으로수를둘수있는플레이어가이기는경우 Game of NIM Impartial Normal Game 은수학적으로훨씬효율적으로풀수있다 ( 여기선생략 )
Traveling Salesman Problem 모든도시를 1 번씩방문하는경로중가장짧은것은?
Can We Brute-Force It? N 개의도시에대해 N! 개의경로가있다. 20! = 2432902008176640000
Key Observation B-A-F-D, A-F-B-D 경로의차이점은? 최소한앞으로는없다!
Exponential State Space 어떤경로의현재상태를 state= {set of visited vertices, 로표현하자 current vertex} Current vertex: O(V) Set of visited vertex: O(2 V ) C( visited, here) = min C( visited { next}, next) + Cost( here, next) next visited
Implementing Set of Visited Vertices std::bitset<20> 20 개의비트 (0, 1) 을저장하는컨테이너 bitsetvariable[i] = i 번정점을방문했는가? Integers w/ Bitmasks (far more popular) 32 비트정수를사용한다 i 번비트가켜져있는가 == i 번정점을방문했는가? 9 8 7 6 5 4 3 2 1 0 372 10 = 0 1 0 1 1 1 0 1 0 0 2
C++ Bitmask Trick of Trades int bitset; // i 번째비트가켜져있다면? if(bitset & (1 << i)) // i 번째비트를켠다 bitset = (1 << i); // i 번째비트를끈다 bitset&= ~(1 << i); // i 번째비트를토글 bitset ^= (1 << i); // 모든비트를왼쪽으로한칸씩옮긴다 bitset <<= 1; & : Bitwise AND : Bitwise OR ^ : Bitwise XOR << : Shift left >> : Shift right 지수시간상태공간동적계획법은매우자주출현하는주제이므로유의합시다 ~ // 마지막비트를끈다 bitset = (bitset - 1) & bitset;
TSP: 코드 int n, graph[20][20]; int cache[20][1<<20]; int go(int here, int visited) { if(visited == (1<<n) - 1) return 0; int& ret = cache[here][visited]; if(ret!= -1) return ret; ret = 987654321; for(int next = 0; next < n; ++next next) if((visited & (1 << next)) == 0) ret = min(ret, graph[here][next next] + go(next next, visited (1 << next))); return ret; }
Game Of Euler 4x4 판에번갈아가며길이 1~3 의핀을꽂는다 위에서꽂을수도있고, 측면에서꽂을수도있다 더꽂을수없을때까지계속 마지막플레이어가진다 (misere form) 게임중간의상황이주어질때, 승자는?
Key Observation 어떤칸에핀이꽂혀있다면, 어떤형태의핀으로차있던지상관이없다 길이 3 인핀이위에서꽂혔던지 길이2인핀이옆에서꽂혔던지 길이1인핀이위에서꽂혔던지 결국 2 4 4 = 65536 개의상태가된다
The Game Of Death A 가 일곱! 을외쳤다. 술을먹을사람은?
The Game Of Death A 도꽤취했기때문에, A 가본것을믿을수는없다 왼쪽으로한명 / 오른쪽으로한명 ( 각각 1/3 확률 ) G 가술을마실확률은?
Recurrence C( i, j) = 일확률 i 개의화살표를따라간뒤에 j 번째사람 = Σ k Points( j) C( i 1, k) 3 O(NM) 동적계획법.. 32 하지만, M 2 라면어떨까?
The Recurrence Is A Linear Transform C i Ci 1(3) + Ci 1(7) + Ci 1(8) ( 0) = 3 C i Ci 1(0) + Ci 1(3) ( 1) = 3 C i Ci 1(0) + Ci 1(1) + Ci 1(5) + Ci 1(7) ( 2) = 3.. 행렬로바꿔서써보자! C = [ A] C [ ] M i i 1 C = A C M 0 우와, Fast Matrix Exponentiation 이되네요!
Lessons Learned 최적화문제의답안계산하기 K- 번째답안계산하기 계산게임 현재상태에대한 f(state) 의점화식을푼다 Minimax algorithm 상태에사이클이있는경우에는 DP 로풀수없다 Exponential State Space Bitmask trick 들을잘알면도움이된다 Problems w/ Linear Recurrence Matrix exponentiation 으로바꿔서풀수있다