백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2960 에라토스테네스의 체 편(python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/2960

반응형

---

솔루션 살펴보기!!

def find_kth_erased_number(N, K):
    erased = [False] * (N + 1)  # 소수 판별 리스트. 0과 1은 사용하지 않음.
    count = 0  # 몇 번째 숫자가 지워졌는지 카운트

    for P in range(2, N + 1):
        if not erased[P]:  # P가 아직 지워지지 않았을 때
            # P를 지움 (소수)
            erased[P] = True
            count += 1  # 지운 횟수 증가
            if count == K:  # K번째로 지운 수가 P라면 반환
                return P

            # P의 배수들을 지움
            for multiple in range(P * 2, N + 1, P):
                if not erased[multiple]:  # 아직 지워지지 않은 배수를 지움
                    erased[multiple] = True
                    count += 1  # 지운 횟수 증가
                    if count == K:  # K번째로 지운 수가 이 배수라면 반환
                        return multiple
                        
    return -1  # 이 코드는 절대로 실행되지 않음 (문제의 조건상 항상 답이 존재)

# 입력 받기
N, K = map(int, input().split())

# K번째 지워지는 수 찾기
result = find_kth_erased_number(N, K)

# 결과 출력
print(result)

코드 설명:

1. erased 리스트 생성: N + 1 크기의 리스트를 만들어, 각 숫자가 지워졌는지 여부를 False로 초기화합니다. 0과 1은 사용하지 않기 때문에 N + 1로 생성합니다.
2. P를 지우고 카운트: 2부터 N까지 차례로 확인하면서, 해당 숫자가 지워지지 않았으면 그 숫자(P)를 지웁니다. 이때 카운트(count)를 증가시키며, 만약 현재 숫자가 K번째로 지워진 숫자라면 바로 반환합니다.
3. P의 배수들을 지우기: 그 후 P의 배수들을 차례로 지우면서, 또 다시 카운트하여 K번째 지워진 수를 확인합니다.
4. 반환: K번째 지워진 수를 찾으면 반환하고, 문제의 조건상 항상 답이 존재하므로 이 경우가 성립합니다.

---

문제 풀이 전략

이 문제는 에라토스테네스의 체 알고리즘을 변형하여 K번째 지워지는 수를 찾는 문제입니다. 일반적인 에라토스테네스의 체 알고리즘은 2 이상의 소수들을 찾아 그 배수들을 차례로 지워가는 방식으로 동작합니다. 이 알고리즘을 응용하여, 소수뿐만 아니라 그 배수들을 차례로 지워나가면서 K번째로 지워지는 수를 추적하는 전략을 사용합니다.

1. 에라토스테네스의 체 기초

에라토스테네스의 체는 주어진 범위 내에서 소수를 찾기 위한 대표적인 알고리즘입니다. 이 알고리즘의 주요 단계는 다음과 같습니다:

1. 2부터 시작하여 소수의 배수들을 지웁니다.
2. 다음으로 지워지지 않은 수를 소수로 간주하고 그 배수들을 다시 지웁니다.
3. 이 과정을 반복하면 범위 내의 모든 소수와 그 배수들이 구별됩니다.

2. 변형된 목표: K번째로 지워지는 수 찾기

문제는 단순히 소수를 찾는 것이 아니라, K번째로 지워지는 수를 찾는 것이기 때문에, 에라토스테네스의 체를 변형하여 지워지는 숫자들의 순서를 추적해야 합니다.

전략 설명

1. 지워짐 여부를 저장할 리스트:
   • erased라는 리스트를 만들어, 각 숫자가 지워졌는지 여부를 추적합니다. 이때 리스트는 N + 1 크기로 설정되며, 인덱스 0과 1은 사용하지 않으므로 False로 초기화합니다.
2. 소수 및 배수 지우기:
   • P = 2부터 시작하여, 지워지지 않은 숫자 P를 찾습니다. 이 숫자는 소수이며, 그 자체로 K번째 지워질 가능성이 있습니다.
   • 그 후 P의 배수들을 차례로 지워나가며, K번째로 지워지는 수가 발견되면 해당 값을 반환합니다.
3. 카운트 추적:
   • 숫자가 지워질 때마다 count 변수를 1씩 증가시킵니다. 이 카운트가 K에 도달하면 그때의 숫자가 바로 K번째 지워지는 수입니다.

3. 세부 동작 과정

1. 초기화:
   • erased = [False] * (N + 1)로 모든 숫자를 아직 지워지지 않은 상태로 초기화합니다.
   • count = 0으로 지워진 숫자의 개수를 세기 시작합니다.
2. 소수 및 배수 지우기:
   • 2부터 N까지의 모든 숫자 P를 확인합니다. erased[P]가 False이면 아직 지워지지 않았다는 의미이며, 소수임을 의미합니다.
   • 소수 자체를 지우고, 그 배수들을 지워 나갑니다. 이때, 각 숫자가 지워질 때마다 count를 증가시킵니다.
3. K번째 숫자 확인:
   • 숫자를 지울 때마다 카운트를 증가시키고, count == K가 되는 순간, 그 숫자를 바로 반환합니다.
4. 최종 반환:
   • 문제의 조건에 따르면 K번째 지워지는 숫자는 항상 존재하므로, 알고리즘은 반드시 답을 찾습니다. 만약 답이 없다면(이론적으로는 불가능하지만), -1을 반환하도록 해 두었습니다.

4. 최적화 측면

• 불필요한 작업 방지: 배수를 지울 때, 이미 지워진 수는 다시 지우지 않도록 하여 불필요한 작업을 방지합니다.
• 효율적인 배수 처리: range(P * 2, N + 1, P)를 통해 P의 배수들만 순차적으로 지우므로, 소수의 배수들을 빠르게 처리할 수 있습니다.

전체 전략의 흐름:

1. 소수를 찾으며 카운트: 2부터 시작하여 소수를 찾고, 그 소수와 배수들을 지워나가면서 K번째 지워지는 수를 추적합니다.
2. 배수 처리: 소수의 배수들을 차례로 지우고, 지워진 수마다 카운트를 증가시킵니다.
3. K번째 지워진 수: K번째로 지워진 수가 나올 때까지 이 과정을 반복합니다.

이 방식은 에라토스테네스의 체와 거의 유사한 효율성을 유지하면서도, 지워지는 숫자를 카운트하는 변형 문제를 해결할 수 있는 최적화된 전략입니다.

---

코드 면접시 알아야할 주요 개념

1. 에라토스테네스의 체 (Sieve of Eratosthenes)

에라토스테네스의 체는 주어진 범위 내에서 소수를 찾기 위한 효율적인 알고리즘입니다. 이 코드는 에라토스테네스의 체를 변형하여 소수 및 그 배수들을 지우는 과정을 통해 K번째로 지워지는 수를 찾습니다.

핵심 아이디어:

• 소수의 배수들은 소수가 아닌 숫자이므로, 소수를 차례로 찾아가며 그 배수들을 지워 소수와 아닌 수를 구분합니다.
• 이 알고리즘의 시간 복잡도는 O(N log log N)으로 매우 효율적입니다. 배수들을 한 번씩만 지우기 때문에 많은 범위의 수에 대해 소수 판별을 빠르게 할 수 있습니다.

면접 질문 예시:

• 에라토스테네스의 체의 시간 복잡도는 어떻게 계산되는가?
• 소수 판별 문제에서 이 알고리즘은 왜 효율적인가?
• N이 큰 경우 이 알고리즘은 어떻게 최적화할 수 있는가?

2. 배열의 사용과 불리언 배열

코드에서 erased라는 불리언 배열을 사용하여 각 숫자가 지워졌는지 여부를 추적합니다. 불리언 배열은 각 인덱스에 대해 True/False 값을 저장하는 배열로, 주어진 범위의 상태를 효율적으로 추적할 수 있는 방법입니다.

면접 질문 예시:

• 불리언 배열을 사용하는 것의 장점은 무엇인가?
• 이 문제에서 불리언 배열을 사용하지 않고 다른 자료구조를 사용할 수 있을까?

3. 시간 복잡도 분석

이 코드의 주요 작업은 에라토스테네스의 체와 유사하게 각 소수의 배수를 지우는 것이므로, 이 코드의 시간 복잡도는 O(N log log N)입니다. 또한 각 숫자가 최대 한 번씩만 지워지기 때문에 불필요한 반복이 없습니다.

면접 질문 예시:

• 이 코드의 시간 복잡도를 분석하시오.
• N이 매우 클 때 이 알고리즘의 성능은 어떻게 변하는가?
• 지워진 숫자의 순서를 저장하는 대신 카운트하는 방식이 어떻게 효율성을 높이는가?

4. 문제 해결 전략

면접에서 중요한 부분은 단순히 알고리즘을 구현하는 것뿐만 아니라 문제를 해결하는 방법을 설명하는 능력입니다. 이 문제는 **"K번째로 지워지는 숫자를 찾는 문제"**로, 단순한 소수 찾기 문제와는 차이가 있습니다. 소수뿐만 아니라 배수들도 카운트해야 하므로, 순서 추적과 지워지는 수를 동시에 관리하는 로직이 중요합니다.

면접 질문 예시:

• 소수를 찾는 알고리즘을 변형하여 K번째 지워지는 수를 찾는 방법은?
• 일반적인 에라토스테네스의 체와 이 코드의 차이점은 무엇인가?
• 만약 배수가 아닌 무작위로 숫자를 지워야 한다면 어떻게 접근할 것인가?

5. 반복문과 조건문 사용

이 코드에서 반복문과 조건문은 매우 중요한 역할을 합니다. 먼저 외부 반복문에서는 소수 자체를 찾고, 내부 반복문에서는 해당 소수의 배수들을 지웁니다. 또한 지워진 숫자의 순서를 관리하기 위해 if 조건문을 사용하여 count가 K에 도달하는 시점을 찾습니다.

면접 질문 예시:

• for 루프를 사용하여 문제를 해결할 때 어떤 점에 주의해야 하는가?
• 조건문을 통해 순서를 추적하는 방법에 대해 설명하라.
• 코드를 더 최적화할 방법이 있는가?

6. 기본적인 수학적 개념: 소수와 배수

이 문제는 소수(prime number)와 배수(multiple)에 대한 기본적인 수학 개념을 잘 이해하고 있어야 합니다. 소수는 1과 자기 자신 외에는 약수가 없는 수를 의미하며, 소수의 배수는 항상 소수 자신이 아닌 합성수입니다.

면접 질문 예시:

• 소수란 무엇이며, 소수를 효율적으로 구하는 방법은?
• 배수를 효율적으로 처리할 수 있는 자료구조나 알고리즘은?
• 소수를 구하는 다른 방법은 무엇이 있을까? (예: Trial Division, Miller-Rabin Primality Test 등)

7. 문제의 변형 가능성

면접에서는 종종 주어진 문제를 변형하거나 응용하여 질문하는 경우가 많습니다. 예를 들어, **"K번째 소수를 찾는 문제"**로 변형하거나, 특정 범위 내에서 소수가 아닌 수 중 K번째 수를 찾는 문제로 응용될 수 있습니다. 또는 문제를 최적화하는 방법이나, 메모리 사용량을 줄이는 방식에 대해서도 질문을 받을 수 있습니다.

면접 질문 예시:

• 만약 K번째로 소수만 지우고 싶다면 어떻게 변경할 수 있는가?
• 이 알고리즘에서 메모리 사용량을 줄이려면 어떤 방법을 사용할 수 있는가?
• 소수를 구하는 다른 최적화 기법은?

8. 테스트 케이스 및 디버깅

면접에서는 코드를 작성한 후 이를 다양한 테스트 케이스로 검증하는 것도 매우 중요합니다. 이 코드의 경우, K가 매우 크거나, N이 작은 경우, 또는 K가 N보다 큰 경우 등에 대한 테스트를 통해 오류를 방지할 수 있습니다.

면접 질문 예시:

• 이 알고리즘이 항상 K번째 지워지는 수를 올바르게 찾는지 어떻게 검증할 수 있는가?
• 예외 처리나 엣지 케이스는 어떻게 다루어야 하는가?
• 테스트 케이스를 만들 때 고려해야 할 사항은?