본문 바로가기

공부/알고리즘

[알고리즘] 동적 계획법(dynamic programming) - 6

반응형

이번에는 조합 게임을 하는 경우에서 사용하는 동적계획법입니다!


바로, 체스나 바둑, 오목처럼 두 사람의 참가자가 하는 게임이죠!

이 게임의 문제를 해결한다는 것은, 게임의 상태가 주어졌을때 완벽한 수를 찾아내는 알고리즘, 다시 말하면 자신이 최대한으로 이길 수 있는 수를 찾아내는 것이죠!


이런 수는 어떻게 찾아내면 될까요?


어떠한 경우에도 결국 게임이 끝나는 부분은 존재할 것입니다! 거기서 게임의 승/패는 갈리게 되겠죠.





여기서 A는 당연히 A가 이기는 결과로 갈 것입니다! 즉, 해당 차례인 사람의 차례에서 이기는 루트가 있다면 바로 이기는 수를 두게 되고, 해당 차례 사람은 이기게 되는 것이죠!



만약, B 차례인데 B가 이기는 경우가 없다면 어떻게 될까요?


위와 같은 경우는 어떻게 하더라도 A가 이기는 것이 되기 때문에 B는 지게 됩니다.


그럼 그 전에 A 차례인 경우에는 당연히 이쪽 루트를 선택하겠죠!

그리고 이 과정을 반복하면, 결국 트리의 루트까지 올라가게 되고, 어디에 두어야 최선의 수가 되는지 알 수 있게 됩니다.


자! 이렇게 맨아래(bottom)으로부터 결과를 처음으로 올라가면서(up) 찾는 방법을 bottom-up 방식이라고 합니다! 


또한, 여기서 보면, 어떤 차례가 됬을 때 어떻게 경로에 도달했는지는 중요하지 않습니다. 결국, 현재의 상태만이 중요하다는 것을 알 수 있고,이 때문에 메모이제이션을 이용할 수 있는 것 입니다!!!


다만, 만약에 다음 상태로 갔는데 이전 상태로 복귀할 수 있는 경우는 어떨까요??? 그런 경우에는 사이클이 생길 수 있기 때문에 동적 계획법으로 해결하기는 무리가 생기겠죠.



오늘의 동적 계획법은 여기까지 입니다!

반응형