게임이론 기본기 익히기2 - 2~9 사이 정수 곱하기 게임에서 이기는법

4370번: 곱셈 게임 (acmicpc.net)  1  p >= n에 먼저 도달하는 사람이 이길 때, 두 사람이 완벽하게 게임한다면 n에 대하여 선공과 후공중 누가 이길까?  1. 다이나믹 프로그래밍 n의 제한이 너무 크기때문에 dp배열을 초기화해서 해결하기는 어렵다 그래서 dict를 이용해서 배열의 크기는 잡지말고 필요한 값만 저장하도록 하는 dp를 이용 현재 상태가 p라고 한다면, 이 게임은 i = 2,3,..,9중 하나를 곱해서 상태를 변화시킬 수 있고 이기거나 지거나 둘중 하나이고 완벽하게 게임하므로  현재 이기는 상태라면 상태 변화를 통해 상대가 지는 상태가 되는거고 현재 지는 상태라면, 상태 변화를 통해 상대가 이기는 상태가 된다 p = 1부터 시작해서 재귀적으로 모든 i = 2,3,4,..,..

• format_list_bulleted 게임이론
• · 2024. 9. 5.
• textsms

돌 무더기에서 팰린드롬(palindrome)인 정수 개수만큼 가져갈 때 이기는 방법

31648번: Palindrome Game (acmicpc.net)   돌 무더기에 s개의 돌이 있는데, A,B가 양의 정수 x개만큼 돌을 가져간다. 여기서 x는 palindrome이어야 한다.  palindrome은 앞에서 읽어도 뒤에서 읽어도 같은 수이다. 예를 들어 1, 121, 9009는 palindrome이다. 앞에 0을 붙이는 것은 허용하지 않는다. 예를 들어 990은 palindrome이 아니다. s가 주어질때, 최선을 다해 게임하는 둘에 대해 선공이 이기는지 후공이 이기는지 판단 -----------------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 게임이론
• · 2024. 5. 6.
• textsms

틱택토 게임(tic tac toe)에서 가능한 모든 경우의 수를 찾는 방법

1. 틱택토 게임 3*3 게임판에서 O와 X를 서로 번갈아 둔다. 가로나 세로, 대각선으로 1줄(3개)이 서로 같게 만들면 승리 3*3 게임판에서 각각의 cell은 O, X, '.' 3가지중 한가지가 들어갈 수 있으므로.. 모든 가능한 게임판의 경우는 $3^{9} = 19683$가지로 몇가지가 없다 이 경우 중간에 게임이 끝나서 더 이상 둘 수 없는 경우가 있기 때문에 그런 경우를 고려해서 제외하면 된다. BFS를 이용해서 모든 가능한 경우를 조사할 수 있다. 1) deque에 (['.']*9, (첫 시작이 두는 수))를 먼저 넣고 BFS를 수행 특히 배열이 9칸이기 때문에 배열을 deepcopy해도 시간이 그렇게 오래걸리지 않는다. 2-1) 큐에서 하나씩 뽑은 다음, 게임판 배열을 순회해서 둘 수 있는..

• format_list_bulleted 게임이론
• · 2024. 3. 13.
• textsms

필승 전략 게임 - 베스킨라빈스 31 게임에서 반드시 이길 수 있을까?

1. 베스킨라빈스 31 술게임에서 많이 하는 게임이다. 규칙은 다음과 같다. 두 사람이 게임을 하는데 1부터 시작해서 3개까지 숫자를 부를 수 있고 31을 먼저 부르면 지는 게임이다. 예를 들어 A가 1,2,3을 부르면 B는 4,5를 부르고 A는 다시 6,7을 부르고.... 상대방이 나한테 선공을 양보했다. 술을 못마시는 나는 최대로 집중해서 이 게임에서 반드시 이기고 싶다. 어떻게 해야 내가 이 게임에서 반드시 이길 수 있을까? 2. 게임의 필승 전략1 결국 내가 게임을 이길려면 마지막에 30을 불러야 게임에서 이길 수 있게 된다. 그 전에 내가 불러야 하는 숫자는 얼마일까? 상대방이 27, 28, 29중 하나로 끝을 내야 내가 마지막에 30을 부를 수 있다 상대방이 27, 28, 29중 하나로 끝을 ..

• format_list_bulleted 게임이론
• · 2023. 6. 5.
• textsms

필승 전략 게임 - 돌 줍기 게임에서 반드시 이기는 방법

1. 돌 줍기 게임 1) A부터 시작하여, A와 B가 번갈아가며 쌓여 있는 돌 무더기에서 돌을 1개 이상 집어온다. 2) 자기 차례가 되어 돌을 집어 올때는, 반드시 상대방이 조금 전에 집어간 돌의 개수의 2배 이하로 집어와야 한다. 예를 들어, A가 2개를 집고 차례를 넘겼다면, B는 1개~4개까지 범위에서 돌을 집어와야한다. 이제 B가 3개를 집고 넘겨준다면, A는 다시 1개~6개 범위에서 마음대로 돌을 집어갈 수 있다. 3) 마지막 돌을 집어간 사람이 게임에서 승리한다. 4) 맨 처음 시작하는 사람이 돌을 다 집어갈 수는 없다 2. 반드시 이길 수는 없나? A,B가 최선의 전략으로 게임할때, 누가 이기는지 예측할 수 있을까? 1) 돌멩이가 1개 있을때, 게임 자체가 성립하지 않는다. 맨 처음 시작하..

• format_list_bulleted 게임이론
• · 2023. 5. 23.
• textsms

알고리즘 문제 해결(PS)을 위한 게임이론 기초지식 - 님 게임(Nim game) 배우기

1. 님 게임(Nim game) 게임이론에서 가장 중요한 게임 형태중 한가지라고 할 수 있다. ""수학적 전략 게임으로, 여러 개의 돌 무더기가 있다고 가정하자. 두 사람이 서로 차례를 번갈아가며 게임을 한다. 자신의 차례에 하나의 돌 무더기를 선택하고, 1개이상의 원하는 만큼의 돌을 제거한다. 마지막 남은 돌을 제거하는 사람이 게임에서 승리한다."" 2. 게임의 수학적 기술 현재 시점에 n개의 돌 무더기에 있는 돌의 개수가 $x_{1}, x_{2}, ... , x_{n}$이라고 하자. 내가 어떤 돌 무더기를 하나를 선택하여 돌을 가져가고 나서 변화된 돌의 개수는 $y_{1}, y_{2}, ... , y_{n}$이라고 하자. 만약 k번째의 돌 무더기를 선택하고 돌을 가져갔다면.. 돌의 개수는 줄어드니까 ..

• format_list_bulleted 게임이론
• · 2023. 5. 15.
• textsms