[개념정리] 수학 및 논리 퍼즐

퍼즐 혹은 수수께끼라고 불리는 문제들은 정책적으로 이런 종류의 문제를 면접에 출제하는 것을 금지하고 있지만, 이런 문제를 받게 될 가능성이 있다. 왜냐하면 수수께끼라는 것의 정의 자체가 모호하기 때문이다. 퍼즐 혹은 수수께기 문제의 좋은 점 중 하나는 꽤나 그럴싸하게 공정하다는 것이다. 대체로 문제로 말장난을 하지 않고 거의 대부분 논리적으로 추론이 가능하기 때문이다. 여기서는 이러한 문제들을 푸는데 기본적인 방법들과 반드시 알아야 하는 지식에 대해서 알아볼 것이다.

 

-소수

소수판별 

가장 단순한 방법  : 1 부터 n-1까지 돌면서 나누어지는 경우가 있는지 확인한다. 

개선된 방법 : 1부터 n의 제곱근까지만 돌면서 나누어 지는 경우가 있는지 확인한다. 

import math
def getPrime(n):
    if n < 2 :
        return False
    for i in range(2, math.sqrt(n)):
        if n % i ==0:
            return False
    return True

소수 목록만들기 (에라토스테네스의 체)

처음 리스트는 1부터 max까지 모든 수로 구성되어 있고, 2부터 나누어지는 모든 수를 리스트에서 없애가면서 다음소수(아직 지워지지 않은 숫자)를 찾아 다시 그 수로 부터 나누어지는 모든 수를 리스트에서 없애가면 2부터 max까지의 소수를 구할 수 있다. 

- 몇가지 개선의 방법이 있지만 간단하게는 배열에 홀수만 저장하는 방법이 있다. 

 

-확률

P(A∩B) = P(B|A)P(A)  = P(A|B)P(B) 이므로 

P(A|B) = P(B|A)P(A)/P(B) 로 표현할 수 있고 이것을 베이즈 정리라고 한다. 

A(A∪B) = P(A)+ P(B) - P(A∩B) 이다 

독립성 : 한 사건의 발생과 다른 사건의 발생 사이에 아무런 관계가 없는 경우, P(B|A) = P(B) 가 된다.

상호배타성 : 한 사건이 일어난 경우 다른 사건은 발생할 수 없는 경우, P(A∩B)는 공집합.

 

수수께끼에 접근하는 자세!

1. 입을열라! 

 - 알고리즘과 마찬가지로 면접관들이 원하는 것은 우리가 문제에 어떻게 접근하는 가를 보는 것이다. 

2. 규칙과 패턴을 찾으라!

 - 문제를 풀다가 발견하는 '규칙'이나 패턴을 따로 적어두면 도움이 된다. 

[예시]

문제 :  끈이 두개있다. 각 끈을 태우는데 정확히 한시간이 걸린다. 이 두끈을 사용하여 15분을 재려면 어떻게 해야하는가? 이 끈의 밀도는 균일하지 않아서 절반의 길이를 태우는데 정확히 30분이라는 보장이 없다. 

 

이 문제를 규칙으로 만들어보자 

규칙 1 : 태우는데 x분이 걸리는 끈과 y분이 걸리는 끈이 주어진다면 x+y만큼 시간을 잴 수 있다. 

규칙 2 : 태우는데 x분이 걸리는 끈이 주어진다면 x/2분을 잴 수있다. ( 양끝에 불을 붙여서 끈이 다 타버리는 순간이 x/2분)

규칙 3 : 1번 끈을 태우는데 x분 걸리고 2번 끈을 태우는데 y분 걸린다면 2번 끈을 태우는시간을 (y-x)분이나 (y-x/2)으로 바꿀 수 있다.

( y-x>0 이라면 두 끈에 동시에 불을 붙였을때  x가 모두 타버린 순간이 y-x시간)

 

따라서, 

1. 1번 끈은 양쪽에 불을 붙이고, 2번끈은 한쪽에만 불을 붙인다. 

2. 1번 끈이 모두 타들어간 순간이, 30분이 지난 순간이다. 2번끈이 다 타기 위해 남은시간은 30분이다.

3. 2번끈의 반대편 끝에 불을 붙인다. 

4. 그러면 정확히 15분 후, 2번끈도 모두 불탈 것이다.

- 규칙을 구하면 문제를 해결하는데 훨씬 쉬워진다.

 

- 최악의 경우를 관리하는 방법

수수꼐끼 종류의 문제 중 많은 수가 최악의 경우를 최소화 하는 것과 관련이 되어있다.

이럴때에는 최악의 상황을 "균형 맞추도록"하면 도움이 된다. 

즉, 초기의 어떤 결정을 통해 최악의 경우가 한쪽 방향으로 쏠리면, 그 결정을 다른 방식으로 바꾸어서 최악의 경우가 균형잡히도록 하는것.

[예시]

문제: 공이 아홉개 있다. 이 가운데 여덟 개는 무게가 같고, 하나는 더 무겁다. 여러분들에게 저울이 하나 주어지는데 이 저울로는 왼쪽이 무거운지 오른쪽이 무거운지 밖에 알 수 없다. 저울을 딱 두번만 사용해서 가장 무거운 공을 찾아내라.

 

가장 먼저 생각할 수 있는 방법은, 아홉번째 공을 제쳐 둔 채, 나머지 공을 네 개씩 두 그룹으로 나누는 것이다. 만약 이 두 그룹의 무게가 같다면 아홉번째 공이 가장 무거운 공이다. 그게 아니라면 더 무거운 그룹을 택해 반복한다. 하지만 이 방법에서는 최악의 경우 세번 사용해야 하므로 문제를 해결할 수없다.

이것이 최악의 경우가 균형잡히지 않은 상태이다. 제쳐 둔 공이 무거운 놈인지 알아내는데에는 한번이면 족하지만 남은 공들에게서 무거운 공을 찾아내는 데에는 세번이 걸린다. 만일 우리가 처음에 제쳐 두는 공의 개수를 늘려 잡아 일종의 페널티를 주게 되면, 다른 그룹에 주어지는 부담을 줄일 수있다. 

공들을 세개씩 세그룹으로 나누게 되면 저울을 한번만 사용해서 어떤 그룹에 무거운 공이 있는지 알아 낼 수있다.

자 이제 남은 세개의 공을 같은 방법으로 달아 보면 된다. 공 하나는 제쳐놓고 남은 두개의 공을 저울 양쪽에 하나씩 올려 놓는다. 저울이 기운다면 기운 쪽의 공이 무거운 놈이다. 아니라면 제쳐놓은 공이 가장 무거운 공이 된다.