🐢 9. Math & Logic puzzles

🫧 소수

• 모든 자연수는 소수의 곱으로 나타낼 수 있다
• 많은 소수의 지수 부분이 0 임
• 가분성 (divisibility)
  • 어떤 수 x로 y를 나눌 수 있으려면 x/y 또는 mod(y, x) = 0 으로 표현
  • x를 소수의 곱으로 분할하였을 때 나열되는 모든 소수를 y를 소수의 곱으로 분할하였을 때 나열되는 모든 소수들의 부분집합이 되어야 함
• 소수판별
  • 어떤 수 n이 소수인지 여부를 판별하는 갖는 단순한 방법은 2 에서 n-1 까지 루프를 돌면서 나눠지는 경우가 있는지 확인

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

• 소수 목록 만들기: 에라토스테네스의 체
  • 소수 목록을 만드는 굉장히 효율적인 방법
  • 소수가 아닌 수들을 반드시 다른 소수로 나누어진다는 사실에 기반하여 동작
    • 주어진 리스트는 1부터 max 까지 모든 수로 구성
    • 처음에는 2로 나누어지는 모든 수를 리스트에서 없앤다
    • 다음 소수, 즉 지워지지 않은 수 중 가장 작은 수 찾는다
    • 그 수로 나뉘는 모든 수를 리스트에서 제거한다
    • 2에서 max 까지의 구간 내에 있는 모든 소수들의 리스트가 만들어진다

🫧 확률

• 논리적인 추론이 가능한 몇 가지 법칙에 기반

• 교집합

  

  • 두 사건 A 와 B 의 겹치는 부분
  • 집합 A와 B의 공통된 원소들만 골라낸 집합. (A∩B)

  • 교집합을 조건제시법으로 나타내면 ➜ A ∩ B = { x

    ( x ∈ A ) ∧ ( x ∈ B )}

• 합집합

  

  • 사건 A와 B 의 점유하고 있는 모든 영역
    • 집합 A와 B의 원소들을 합친 것처럼 모두 모은 집합. (A∪B)

    • 합집합을 조건제시법으로 나타내면 ➜ A ∪ B = { x

      ( x ∈ A ) ∨ ( x ∈ B )}

      • 조건 부분에 논리연산 사용.➜ 합집합의 원소 x가 A에 속한다는 명제(x∈A) 와 B에 속한다는 명제(x∈B)가 논리합(OR)연산으로 연결.
    • 위의 벤 다이어그램으로 나타낸 예의 합집합 ➜ A ∪ B = {1, 2, 3, 4, 6, 8}
    • 주의) 합집합 A∪B의 크기를 구할 때.

      • 두 집합 A와 B의 원소 개수를 단순히 더하면 안되고, 교집합 A∩B에 포함되는 원소들이 양쪽으로 중복하여 계산되기 때문에 교집합의 크기를 빼주어야 합니다. ➜ (

        A ∪ B

        =

        A

        +

        B

        -

        A ∩ B

        )

  • 독립성
    • A와 B가 독립사건이라면 A가 B에 아무런 영향을 미치지 않는다
  • 상호 배타성
    • A와 B가 상호 배타적이라면 다른 사건이 발생할 수 없다는 관계가 존재

🫧 규칙과 패턴 찾기

• 규칙이나 패턴은 나중에 쉽게 기억할 수 있음
• 규칙을 나열하는 과정을 통해 문제를 쉽게 풀 수 있음

🫧 최악의 경우

• 최악의 경우를 최소화하는 것
• 어떤 행동을 최소화 하는 문제
• 지정된 횟수 안에 처리해야 하는 문제
• 최악의 상황을 균형 맞추도록 하면 도움이 된다
• 즉, 초기의 어떤 결정을 통해 최악의 경우가 한쪽 방향으로 쏠리면, 그 결정을 다른 방식으로 바꿔서 최악의 경우가 균형 잡히도록 할 수 있다