님 게임과 그런디 수
XOR로 비편향 게임을 풉니다
님 게임과 그런디 수은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
Nim 게임 만나기
Nim에는 여러 개의 돌무더기가 있습니다. 자신의 차례에 한 무더기에서 원하는 개수만큼 돌을 제거하며, 마지막 돌을 가져간 플레이어가 승리합니다. 🪨
마법의 수량: XOR
게임 전체의 승패는 모든 돌무더기 크기의 XOR로 결정됩니다. 이 하나의 수가 누가 이기는지를 알려 줍니다.
님-합 규칙
돌무더기들의 XOR을 님-합이라고 합니다. 님-합이 0이면 다음 차례인 플레이어가 패배하고, 0이 아니면 그 플레이어가 승리합니다.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= p0이 곤란한 이유
0인 님-합에서는 어떤 수를 두어도 균형이 깨지고, 상대방에게 0이 아닌 합을 넘겨주게 됩니다. 상대방은 그 합을 언제나 다시 0으로 만들 수 있습니다.
승리하는 수 찾기
님-합이 0이 아니면 언제나 님-합을 0으로 되돌리는 수가 있습니다. 그 수를 두면 상대방을 패배하는 위치에 놓을 수 있습니다.
Nim을 넘어: 그런디 수
다른 무편향 게임에서는 각 상태에 그런디 수를 사용합니다. 이는 님-합이라는 개념을 거의 모든 가져가기 게임으로 일반화합니다.
mex 연산
상태의 그런디 값은 mex입니다. 즉, 가능한 수로 도달하는 상태들의 그런디 값에 포함되지 않은 가장 작은 음이 아닌 정수입니다.
def mex(s):
i = 0
while i in s:
i += 1
return i재귀로 그런디 값 계산하기
도달 가능한 모든 상태로 재귀 호출을 하고, 그런디 값들을 모은 다음 그 집합의 mex를 구합니다.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})그런디 수 0은 패배
그런디 수가 0인 단일 게임 상태는 님-합이 0인 경우와 마찬가지로 패배 위치입니다. 0이 아니면 승리입니다.
스프라그-그런디 정리
서로 독립적인 게임을 동시에 플레이할 때는 그런디 수들을 XOR하세요. 이 스프라그-그런디 결과를 이용하면 게임의 합을 Nim으로 바꿀 수 있습니다. ✨
적용되는 경우
그런디 이론에는 무편향 게임이 필요합니다. 두 플레이어가 같은 수를 둘 수 있고, 마지막으로 수를 둔 플레이어가 승리해야 합니다. 사용하기 전에 이를 확인하세요.
빠른 확인
돌무더기 1, 2, 3으로 Nim 게임을 시작합니다. 여러분이 이기고 있을까요?
복습
Nim의 핵심은 돌무더기들의 XOR입니다. 0이면 패배하고 0이 아니면 승리합니다. 그런디 수와 mex를 이용하면 이를 여러 무편향 게임으로 확장할 수 있습니다. 🏆
자주 묻는 질문
“님 게임과 그런디 수” 강의는 무료인가요?
네 — “님 게임과 그런디 수” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“님 게임과 그런디 수”에서 뭘 배우나요?
XOR로 비편향 게임을 풉니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“님 게임과 그런디 수” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 게임의 승리 상태와 패배 상태
- 님 게임과 그런디 수
- 중간에서 만나기
- 빠른 디버깅: 스트레스 테스트와 선별