기차표 예매를 위하여 줄을 섰을 때, 이들 중 생일이 같은 사람이 존재 할 확률은 얼마일까?
계산을 해보면, 23명 이상 일 때 부터 50%가 넘어가고, 57명이 넘어가면 99%가 넘어간다.
파이썬으로 짜보면 아래와 같다.
import matplotlib.pyplot as plt
prev = 1
result = [0]
for m in range(57):
prev = prev * (365-m)/365
result.append(1-prev)
x = [ n for n in range(len(result))]
plt.scatter(x, result)
plt.axvline(x=23, color='RED', linestyle='-', linewidth=0.2)
plt.axhline(y=0.5, color='RED', linestyle='-', linewidth=0.2)
plt.show()
import time
import math
def is_valid(used_pattern, stack, max_point):
if len(stack) < max_point:
return 0
checked_point = [False] * 9
checked_point[stack[0]] = True
for i in range(1, len(stack)):
prev_x = stack[i-1] % 3
prev_y = math.floor(stack[i-1] / 3)
cur_x = stack[i] % 3
cur_y = math.floor(stack[i] / 3)
"""
0 1 2
3 4 5
6 7 8
아래와 같은 이동한 경우,
이동시 가운데 점이 기존 패턴에 포함 되지 않은 경우
유효 하지 않다.
0 <-> 2 | 0 <-> 6 | 0 <-> 8
2 <-> 8 | 6 <-> 8 | 2 <-> 6
1 <-> 7 | 3 <-> 5
예)
0 -> 1 -> 0 -> 2 : OK
0 -> 2 : Not OK
유효하지 않은 경우를 판단하기 위하여
각 버튼의 위치를 (y, x)로 나타내면 (0,0) ... (2,2) 까지이다.
0 -> 2 => (0,0) -> (0, 2)
0 -> 6 => (0,0) -> (2, 0)
여기서 문제 경우의
두 좌표의 합을 구하면 x, y가 모두 2의 배수가 된다.
그래서 아래와 같이 이동 전후의 좌표의 합이 모두 2의 배수가 되는 경우에서
Not OK 경우만 걸러 주면 된다.
0 -> 1 -> 0 -> 2 : OK
0 -> 2 : Not OK
"""
if ((prev_x + cur_x) % 2 == 0) and ((prev_y + cur_y) % 2 == 0):
mid_x = math.floor((prev_x + cur_x) / 2)
mid_y = math.floor((prev_y + cur_y) / 2)
if checked_point[mid_y * 3 + mid_x] == False:
return 0
checked_point[stack[i]] = True
return 1
def check_pattern(used_pattern, stack, max_point):
if len(stack) > max_point:
return 0
result = is_valid(used_pattern, stack, max_point)
for p in range(0, 9):
if used_pattern[p]:
continue
used_pattern[p] = True
stack.append(p)
result = result + check_pattern(used_pattern, stack, max_point)
stack.pop()
used_pattern[p] = False
return result
def main():
used_pattern = [False] * 9
stack = []
result = []
for max_point in range(1, 10):
result.append(check_pattern(used_pattern, stack, max_point))
for c in range(0, len(result)):
print ("{0}: {1}".format(c, result[c]))
print("4-9 patterns count:", sum(result[3:]))
if __name__ == '__main__':
start_time = time.time()
main()
print('\n', time.time() - start_time)
위 코드를 C로 바꾸면 아래와 같다.
#include <stdio.h>
int stack_idx;
int stack[9] = {0, };
int is_valid(int used) {
int checked = 0;
if (stack_idx < 4) {
return 0;
}
checked |= 1 << stack[0];
for (int i = 1; i < stack_idx; i++) {
int prev_x = stack[i-1] % 3;
int prev_y = stack[i-1] / 3;
int cur_x = stack[i] % 3;
int cur_y = stack[i] / 3;
if (((prev_x + cur_x) % 2 == 0) &&
((prev_y + cur_y) % 2 == 0)) {
int mid_x = (prev_x + cur_x) / 2;
int mid_y = (prev_y + cur_y) / 2;
int pos = mid_y*3 + mid_x;
if (!(checked & (1 << pos))) {
return 0;
}
}
checked |= (1 << stack[i]);
}
return 1;
}
int check_pattern(int used) {
int result = 0;
if (stack_idx == 10) {
return 0;
}
result = is_valid(used);
for (int i = 0; i < 9; i++) {
if (used & (1 << i)) {
continue;
}
stack[stack_idx++] = i;
result += check_pattern(used | (1 << i));
--stack_idx;
}
return result;
}
int main(int argc, char **argv) {
printf("%d\n", check_pattern(0));
return 0;
}
약간 변경해서, 1^1 + 2^2 + ... + 10000^10000 의 결과 중 끝 50자리를 출력하는 형식으로 바꿔보았다.
from multiprocessing import Pool
import time
MAX_COUNT = 10**50
def mypower(num):
result = 1
for i in range(num):
result = result * num
if result < MAX_COUNT:
continue
result = result % MAX_COUNT
return result
def get_sum(num):
assert num > 0
numbers = [i for i in range(1, num+1)]
assert len(numbers) == num
pool = Pool(processes=4)
return sum(list(pool.map(mypower, numbers))) % MAX_COUNT
if __name__ == '__main__':
start_time = time.time()
print(get_sum(10000))
print(time.time() - start_time)
대부분 한번은 해보았을 지뢰찾기 규칙은 대부분 알기에 아래와 간단히 개발 바운더리를 정하였습니다.
1. 구현목표 * 윈도우 지뢰찾기 게임의 클론
2. 요구사항
2.1 운영체제 * Android에서 동작 한다
2.2 게임의 구성 * 화면의 타일의 크기는 10x10 이다 * 지뢰의 개수는 12개 이다 * 지뢰의 위치는 매번 랜덤하게 정해 진다
2.3 게임의 동작 * 지뢰가 없는 빈 칸을 클릭시, 해당 칸을 중심으로 8칸 안에 있는 지뢰의 개수가 표시 된다. * 1초 마다 시간이 업데이트 된다 * 5999초가 넘어가면 자동으로 게임 오버가 된다 * 깃발/지뢰 선택 버튼을 클릭시 깃발->지뢰 순으로 표시 된다. * 깃발을 표시 할 때 마다, 표시 할 수 있는 남은 깃발의 개수가 업데이트 된다. * Pause 상태로 돌입시, 현재의 게임 상태가 유지 되어야 한다. * 게임 플레이 중 언제든지 Pause 상태로 변경 할 수 있어야 한다. * Pause 상태에서는 이어하기와 새 게임 하기가 가능해야 한다. * 깃발 선택 상태에서 타일을 클릭시 깃발이 사라지거나 표시된다. * 지뢰 상태에서 버튼을 클릭시 타일이 열린다. 이때 지뢰가 있으면, 게임 오버가 된다.
5. 설계 하기
5.1 UML
먼저 게임의 상태를 IDLE / PLAY / PAUSE / WIN / GAMEOVER 로 정의 하고,
이를 반영하여 UML를 그리면 위와 같습니다.
Play상태에서 지뢰를 모두 찾거나, 혹은 지뢰를 누른 경우,
Game State를 Win State 또는 Game over state 상태로 변경하기 위하여,
위와 같이 NotifyCallBack interface를 PLAY state가 가지도록 합니다.
package com.chobocho.minesweeper;
public interface MineSweeperNotifyCallback {
public void setWinState();
public void setGameOverState();
}