Sprague-Grundy Theorem For Problem Solving
이 글은 Problem Solving를 위한 스프라그-그런디 이론 기초 설명입니다. 먼저 님 게임을 알아봅시다. Nim game 돌 무더기 \(n\)개가 있고, 각 돌 무더기는 \(p_{1}, p_{2}, ... ,p_{n}\)개의 돌로 구성되어 있습니다. 두 명의 플레이어는 자신의 차례마다 돌 무더기 하나를 고른 뒤, 그 돌 무더기에서 $1$개 이상의 돌을 덜어냅니다. 자신의 차례에 덜어낼 돌이 없는 플레이어가 패배합니다. 즉, 마지막 돌을 가져간 플레이어가 승리합니다. 님 게임에서 두 플레이어가 완벽하게 플레이했을 때 선공/후공 중 누가 이기는 지는 정해져 있습니다. 두 플레이어 모두 최적으로 행동한다는 전제하에, winning state에서 턴을 가지는 플레이어는 반드시 승리하며, losing st..
알고리즘
2022. 11. 14. 19:01