[이산수학] Mathematical Thinking in computer Science 2주차

예시를 찾는 방법

문제) Magic Squares : 가로 세로 대각선의 합이 같음 1~n^2까지

해설) 범위를 좁히기 - 1~9까지 더하고 3으로 나눈 수가 각 줄의 합이 됨(15)

가운데 숫자는 15/3=5

줄의 합이 될 수 있는 조합을 확인해 문제를 해결한다.

 

문제) Multiplicative Magic Squares : 만약 곱이라면? → 2^x+y = 2^x * 2^y 활용

 

문제) 100으로 시작하고 9127로 나누어지는 6자리숫자 찾기

 

문제) 7/13 플로린 코인으로 1플로린, 2플로린 만들기

 

문제) Paths in a Graph

 

최적성 Optimality

a가 최적이라는 사실에 대한 증명

1. Existential statement : a를 달성하는 방법이 존재한다.

2. Universal statement : 모든 방법은 a보다 더 좋아서는 안된다.

 

문제) 체스판에 룩 최대로 두기 - 대각선으로

 

문제) 체스판에 나이트 서로 공격하지 않게 두기 - 32개

해설) 나이트는 색이 다른 칸으로 이동할 수 있으므로 한 색에만 모두 놓으면 서로 공격할 수 없다.

 

문제) 체스판에 비숍 서로 공격하지 않게 두기 = 14개

 

문제) x와 2x의 하위집합(subset) 찾기

 

Computer Search (다시 공부하기!! )

문제) N queens 체스판에 최대의 퀸 배치하기

Eight queens puzzle

import itertools as it

def is_solution(perm):
    for (i1, i2) in it.combinations(range(len(perm)), 2):
        if abs(i1 - i2) == abs(perm[i1] - perm[i2]):
            return False

    return True

for perm in it.permutations(range(9)):
    if is_solution(perm):
        print(perm)
        exit()

백트래킹 : 해를 찾는 도중 해가 아니면 다시 돌아가기

def can_be_extended_to_solution(perm):
    i = len(perm) - 1
    for j in range(i):
        if i - j == abs(perm[i] - perm[j]):
            return False
    return True

def extend(perm, n):
    if len(perm) == n:
        print(perm)
        exit()

    for k in range(n):
        if k not in perm:
            perm.append(k)

            if can_be_extended_to_solution(perm):
                extend(perm, n)

            perm.pop()

extend(perm = [], n = 20)

문제) 16개의 대각선 그리기

해설) 아래에서 위로 또는 왼쪽에서 오른쪽으로 점차 채우기

한 칸은 3가지 포지션이 가능(왼쪽 아래, 오른쪽 아래, X)

다른 대각선과 만나지 않는지 확인 후 필요 시 백트래킹

 

coursera Introduction to Discrete Mathematics for Computer Science 과정 중

Mathematical Thinking in coumputer Science 2주차 내용 정리