22846번: 인증된 쉬운 게임 (acmicpc.net) 모니터에 1이 쓰여있는데, 두 사람이 선공부터 번갈아가며 모니터에 쓰인 수의 약수를 더해간다. 이 때 제한 k를 초과한 사람이 패배하게 된다. k가 주어질때, 항상 완벽하게 플레이하는 두 사람중 누가 이길까 이런 게임 문제는 보통 1부터 최선의 전략으로 해보면 눈치로 풀면 풀리는 경우가 종종 있더라 실제로 해보면 k = 2,6의 경우에만 선공이 이길 수 있고 나머지는 후공이 반드시 이긴다 k = int(input())if k == 2 or k == 6: print('Kali')else: print('Ringo') 근데 언제까지 이렇게만 할 수는 없지 그리고 이렇게 찾기 힘든 문제도 있더라 개념을 확실히 알아야돼 1) 상..
31648번: Palindrome Game (acmicpc.net) 돌 무더기에 s개의 돌이 있는데, A,B가 양의 정수 x개만큼 돌을 가져간다. 여기서 x는 palindrome이어야 한다. palindrome은 앞에서 읽어도 뒤에서 읽어도 같은 수이다. 예를 들어 1, 121, 9009는 palindrome이다. 앞에 0을 붙이는 것은 허용하지 않는다. 예를 들어 990은 palindrome이 아니다. s가 주어질때, 최선을 다해 게임하는 둘에 대해 선공이 이기는지 후공이 이기는지 판단 -----------------------------------------------------------------------------------------------------------------------..
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) 큐에서 하나씩 뽑은 다음, 게임판 배열을 순회해서 둘 수 있는..
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중 하나로 끝을 ..
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개 있을때, 게임 자체가 성립하지 않는다. 맨 처음 시작하..
1. 님 게임(Nim game) 게임이론에서 가장 중요한 게임 형태중 한가지라고 할 수 있다. ""수학적 전략 게임으로, 여러 개의 돌 무더기가 있다고 가정하자. 두 사람이 서로 차례를 번갈아가며 게임을 한다. 자신의 차례에 하나의 돌 무더기를 선택하고, 1개이상의 원하는 만큼의 돌을 제거한다. 마지막 남은 돌을 제거하는 사람이 게임에서 승리한다."" 2. 게임의 수학적 기술 현재 시점에 n개의 돌 무더기에 있는 돌의 개수가 $x_{1}, x_{2}, ... , x_{n}$이라고 하자. 내가 어떤 돌 무더기를 하나를 선택하여 돌을 가져가고 나서 변화된 돌의 개수는 $y_{1}, y_{2}, ... , y_{n}$이라고 하자. 만약 k번째의 돌 무더기를 선택하고 돌을 가져갔다면.. 돌의 개수는 줄어드니까 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
