🦊 9. Math & Logic puzzles

9. Math & Logic puzzles

소수

모든 자연수는 소수의 곱으로 나타낼 수 있다는 규칙이 있다.

가분성(divisibility)

어떤 수 x로 y를 나눌 수 있으면 x를 소수의 곱으로 분할하였을 때 나열되는 모든 소수는 y를 소수의 곱으로 분할하였을 때 나열되는 모든 소수들의 부분집합이어야 한다.

소수판별

• 2에서 n-1까지 루프를 돌면서 나누어지는 경우가 있는지 확인해보는 것

boolean primeNaive(int n) {
		if (n < 2) {
				return false;
		}
		for (int i = 2; i < n; i++) {
				if (n % i == 0) {
						return false;
				}
		}
		return true;
}

• 루프를 n의 제곱근까지만 도는 경우

boolean primeNaive(int n) {
		if (n < 2) {
				return false;
		}
		int sqrt = (int) Math.sqrt(n);
		for (int i = 2; i < sqrt; i++) {
				if (n % i == 0) {
						return false;
				}
		}
		return true;
}

• 에라토스테네스의 체

boolean[] sieveOfEratosthenes(int max) {
		boolean[] flags = new boolean[max+1];
		int count = 0;

		init(flags);
		int prime = 2;

		while (prime <= Math.sqrt(max)) {
				crossOff(flags, prime);
				prime = getNextPrime(flags, prime);
		}
		return flags;
}

void crossOff(boolean[] flags, int prime) {
		for (int i = prime * prime; i < flags.length; i += prime) {
				flags[i] = false;
		}
}

int getNextPrime(boolean[] flags, int prime) {
		int next = prime + 1;
		while (next < flags.length && !flags[next]) {
				next++;
		}
		return next;
}

1부터 max까지의 리스트에서 2,3,5,7,11 등 소수로 나뉘는 모든 수들을 리스트에서 삭제해 나가면

구간 내에 있는 모든 소수 리스트가 만들어진다.

확률

A ∩ B 의 확률

• 베이즈 정리(Bayes’ Theorem)

P(A

B) = P(B

A) P(A) / P(B)

A ∪ B 의 확률

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

독립성

A와 B가 독립사건이라면, A가 B에 아무런 영향을 끼치지 않으므로

P(A ∩ B) = P(A) P(B)

상호 배타성

A와 B가 상호 배타적이라면 P(A ∩ B) = 0 이 되므로

P(A ∪ B) = P(A) + P(B)

입을 열라

수수께기 같은 문제를 만나도 알고리즘 문제와 마찬가지로 문제를 어떻게 공략해 나가는지 면접관들에게 보여주라

규칙과 패턴을 찾으라

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

최악의 경우는?

수수께끼의 많은 수가 최악의 경우를 최소화하는 것과 연관이 있다.

어떤 행동을 최소화하거나, 지정된 횟수 안에 처리해야 하는 문제일 수도 있다.

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

알고리즘적 접근법

수수께끼처럼 보이는 문제들 중 상당수는 기술적인 측면을 제거한 알고리즘 문제인 경우가 많다.

초기 사레로부터 확장법, 스스로 풀어보기가 유용하게 쓰일 수 있다.