논리적 사고를 기르는 알고리즘 수업(2024.06.21)

논리적 사고를 기르는 알고리즘 수업

논리적 사고를 기르는 알고리즘 수업

Ch 6 전체

체크인 (기분/근황/기대하는 바)

• 성큼이
  • 무덤덤
  • 이래저래 분주함
  • 새로운 챕터 잘 봤으면
• Wayne
  • 조금 피곤하고 몸이 좋지 않음
  • 어제 잠을 잘 못 잠
  • 새로운 것 잘 배우고 갔으면
• 상호
  • 좋음
  • 일이 다시 많아지고 있음
  • 즐겁게 공부했으면

문제풀이

연습문제 6.5

성냥 한 무더기에서, 한 번에 m개에서 n개까지의 성냥을 가져갈 수 있는 성냥개비 게임을 생각해보자. 몇 가지 간단한 예시를 고려해서(예를 들어, m=1이고 n은 임의의 수, 또는 m=2이고 n=3 등), 어느 쪽이 승리 위치이고 어느 쪽이 패배 위치인지 일반적인 규칙과 이기는 전략을 구성해 보아라.

완전한 풀이를 무작정 추측하는 것은 지양하라. 승리 위치와 패배 위치가 묶이는 간단한 패턴을 찾아라. 어떻게 묶이는지 표현하기 위해 적절한 변수를 만들고, 그 변수들의 값을 계산하라

1. m = 1의 경우

0개는 패배위치, 1개 ~ n개는 승리위치. n+1개는 패배위치. n+2 ~ 2n+1개는 승리위치. 2n+2개는 패배위치 ...

따라서, 자연수 k에 대해서 k * (n + 1)은 패배위치, 나머지는 승리위치

2. m = 2, n = 3 의 경우

0, 1개는 패배위치. 2, 3, 4는 승리 위치, 5, 6은 패배위치, 7, 8, 9는 승리위치, 10, 11은 패배위치, ...

따라서 5로 나눴을 때 나머지가 0, 1인 경우 패배위치, 나머지는 승리위치

3. 일반적인 경우

가설: (m + n)으로 나눴을 때 나머지가 m 미만인 경우 패배위치, 나머지는 승리 위치.

증명: 성냥의 갯수가 $k * (m + n) + r, (단, r < m + n, k \in \mathbb{N}, r \in \mathbb{N})$ 라고 하자. $r < m$ 이면 패배위치, 나머지는 승리위치

base case(k = 0인 경우): $r < m$이면 $m$개를 제거할 수 없으므로 패배위치이다. $m \leq r < m + n$ 인 경우, 적당한 숫자를 제거해서 상대방을 패배위치로 보낼 수 있으므로 승리위치이다.

k 일 때 성립한다고 가정하고 k + 1인 경우:

$r < m$이면 m개부터 n개 사이의 어떤 숫자만큼 제거하더라도 상대방이 승리 위치로 가게 된다. 따라서 패배위치

$m \leq r < m + n$ 인 경우, 적당한 숫자를 제거해서 상대방을 위의 패배위치로 보낼 수 있으므로 승리위치이다.

회고 (좋았던 점/ 아쉬웠던 점/ 다음주 이 시간까지 할 일)

• 성큼이
  • 수학적 귀납법을 머리를 돌려봤다. 승리위치 패배위치 따지는 거 리뷰했다.
  • 좀 귀찮은 부분이 있었다
  • 연습문제 6.5 풀이를 정리하겠다
• Wayne
  • 귀납법 풀어봤다
  • 중간에 수학 공식이 많이 나오는 부분이 복잡했다
  • 잘 쉬고 오겠다
• 상호
  • 귀납법에서 n^2의 합을 어떻게 푸는지 알게 됐다
  • 많이 없다
  • 열심히 일하다 오겠다.

나머지 공부