책너두 (코딩 인터뷰 완전분석) 20일차 (~182p, 6.1, 6.2)

메모

소수

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

가분성(divisibility)

소수판별

• 어떤 소수 n이 소수인지 여부를 판단하는 방법

boolean primeNaive(int n) {
    if (n < 2) {
        return false;
    }

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

    return true;
}

• 가장 단순한 방법은 2에서 n-1까지 루프를 돌면서 나누어지는 경우가 있는지 확인하는 것임.
• 위 코드를 살짝 개선해 보면, 루프를 n이 아닌 n의 제곱근까지만 돌면 됨.

boolean primeSlightlyBetter(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;
}

• 루트 n 까지만 검사해보면 충분함.
  • n이 소수가 아니라면 나누는 모든 숫자 a는 그에 대한 보수 b가 반드시 존재하기 때문임.
  • a > 루트n 이라면 b < 루트n임.
  • 따라서 n이 소수인지 알아보기 위해 a까지 검사할 필요는 없음.

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

• 소수 목록을 만드는 굉장히 효율적인 방법임.
  • 소수가 아닌 수들은 반드시 다른 소수로 나누어진다는 사실에 기반해서 동작함.

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

    init(flags); // 0과 1번 인덱스를 제외한 모든 원소값을 true로 초기화한다.
    int prime = 2;

    while (prime <= Math.sqrt(max)) {
        // prime의 배수들을 지워나간다.
        crossOff(flags, prime);

        // 그 다음 true로 세팅된 인덱스를 찾는다.
        prime = getNextPrime(flags, prime);
    }

    return flags;
}

void crossOff(boolean[] flags, int prime) {
    // prime의 배수들을 제거해나간다. k < prime인 k에 대한 k * prime 은
    // 이전 루프에서 이미 제거되었을 것이므로 prime * 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;
}

• 개선의 여지가 있는 코드임
  • 간단하게 배열에 홀수만 저장하는 방법이 있음
  • 메모리 공간을 반으로 줄일 수 있음.

확률

• 논리적인 추론이 가능한 몇 가지 법칙에 기반함.
  • A ∩ B 확률
    • P(A ∩ B) = P(B | A) P(A) = P(A | B) P(B)
    • 이 수식을 베이즈 정리(Bayes’ Theorem)라고 부름
  • A ∪ B 확률
    • P(A) + P(B) - P(A ∩ B)
• 독립 사건(independent event) 혹은 상호 배타적인 사건(mutually exclusive event) 확률을 구하는 특수 규칙을 쉽게 얻을 수 있음.

독립성

• A와 B가 독립사건 이라면 A가 B에 아무런 영향을 끼치지 않으므로 P(B | A) = P(B)가 됨. 따라서 P(A ∩ B) = P(A)P(B)가 됨.

상호 배타성(mutual exclusivity)

• A가 B와 상호 배타적이라면 (한 사건이 일어난 경우 다른 사건은 발생할 수 없는 경우) P(A ∩ B) = 0 이 됨.
  • 따라서 P(A ∪ B) 계산할 때, P(A ∩ B) 항은 제거해도 됨.
  • 따라서 P(A ∪ B) = P(A) + P(B) 임.

입을 열라

• 수수께끼 같은 문제를 만나면 당황하지 말라.
  • 알고리즘 문제와 마찬가지로 면접관들은 여러분이 문제를 어떻게 공략해 나가는지 보는 것임.

규칙과 패턴을 찾으라

• 문제를 풀다가 발견하는 ‘규칙’이나 패턴을 따로 적어두면 도움이 됨.
  • 반드시 적어두는게 나음.
  • 이렇게 해야 과거에 발견한 규칙이나 패턴을 나중에 쉽게 기억해 낼 수 있음.

최악의 경우는?

• 수수께끼 종류의 문제는 많은 수가 최악의 경우를 최소화하는 것과 연관이 있음.
  • ex) 어떤 행동을 최소화하는 문제
  • ex) 지정된 횟수 안에 처리해야 하는 문제
    • 최악의 상황을 ‘균형 맞추도록’ 하면 도움이 됨.
    • 초기의 어떤 결정을 통해 최악의 경우가 한쪽 방향으로 쏠리면 그 결정을 다른 방식으로 바꿔서 최악의 경우가 균형 잡히도록 할 수 있음.
    • ex) 나인볼 문제

면접 문제

6.1 무거운 알약

• 약병 20개가 있다. 이 중 19개에는 1.0그램짜리 알약들이 들어 있고, 하나에는 1.1그램짜리 알약들이 들어 있다. 정확한 저울 하나가 주어졌을 때, 무거운 약병을 찾으려면 어떻게 해야 할까? 저울은 딱 한 번만 쓸 수 있다.

6.2 농구

• 농구 골대가 하나 있는데 다음 두 게임 중 하나를 해 볼 수 있다.
• 게임 1 : 슛을 한 번 쏴서 골대에 넣어야 한다.
• 게임 2 : 슛을 세 번 쏴서 두 번 골대에 넣어야 한다.
• 슛을 넣을 확률이 p라고 했을 때 p가 어떤 값일 때 첫 번째 게임을, 혹은 두 번째 게임을 선택하겠는가?