알면 도움되는 코딩 테스트 유형: 12) #Primality_Test

• 이번 글에서는 소수 판정에 대한 개념과 코딩 테스트에서 소수 판정 문제를 해결하는 방법에 대해 알아보겠습니다. 소수는 많은 알고리즘 문제에서 자주 등장하는 중요한 주제 중 하나이므로, 이 글을 통해 여러분의 코딩 실력을 향상시킬 수 있기를 바랍니다.

 

소수의 개념

 

• 소수는 1과 자기 자신만으로 나누어 떨어지는 수입니다. 예를 들어, 2, 3, 5, 7은 모두 소수입니다. 반면에 4, 6, 8은 다른 수로도 나누어지므로 소수가 아닙니다.

 

코딩 테스트에서의 소수 판정 문제 접근 방법

 

• 가장 간단하고 직관적인 방법으로는 대상 숫자 n을 [2, √n] 범위의 모든 수로 나눠보는 것입니다. 만약 어떤 수 i로 n이 나누어진다면 n은 소수가 아닙니다. 이 방법은 시간 복잡도 O(√n)으로 비교적 간단하게 구현할 수 있습니다.
• 에라토스테네스의 체: 좀 더 효율적인 방법으로 에라토스테네스의 체라고 불리는 알고리즘이 있습니다. 이 알고리즘은 주어진 범위 내에서 모든 소수를 찾아내기 위해 사용됩니다.
• 에라토스테네스의 체 알고리즘을 간략하게 설명하자면 다음과 같습니다.

1. 우선, 크기 n+1의 배열을 생성합니다.
2. 배열 내 모든 값을 True로 초기화합니다.
3. 숫자 i가 처음 등장하면(i=2부터 시작), i를 제외한 i의 배수들을 False로 설정합니다.
4. 배열 내 True 값들이 남아있으면 해당 인덱스 값이 소수입니다.

• 이렇게 구현된 에라토스테네스의 체 알고리즘은 시간 복잡도 O(nlog(logn))으로 매우 효율적입니다.
• 소수 판정 문제를 접할 때에는 주어진 조건과 제약 사항을 잘 분석하는 것이 중요합니다. 일반적으로 입력 범위가 작거나 시간 제한이 넉넉하지 않다면 기본적인 방법인 "대상 숫자 n을 [2, √n] 범위 내 모든 수로 나눠보기"를 사용할 수 있습니다.
• 그러나 입력 범위가 매우 크거나 여러 번 반복되어야 할 경우에는 에라토스테네스의 체와 같은 최적화된 알고리즘이 필요할 수 있습니다. 특히 여러 개의 숫자에 대해 동시에 소수 판정을 해야 할 때 에라토스테네스의 체는 유용하게 사용됩니다.

 

2581번: 소수

 

  문제  

 

• 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.
• 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

  해결 방법  

 

• 이 문제에서는 M과 N 사이의 모든 수 중에서 소수를 찾아야 합니다. 우선, 에라토스테네스의 체를 사용해 주어진 범위 내의 모든 소수를 찾아내겠습니다.
• 첫 번째 반복문에서 range(2, int(N**0.5)+1)을 사용한 것은 숫자 n을 [2, √n] 범위 내 모든 수로 나누어 보기만 하면 n이 소수인지 아닌지 판별할 수 있기 때문입니다.

M = int(input())
N = int(input())

prime = [True] * (N + 1)
prime[0] = prime[1] = False

for i in range(2, int(N ** 0.5)+1):
    if prime[i]:
        for j in range(i+i, N+1, i):
            prime[j] = False

in_range = [i for i in range(M, N+1) if prime[i]]

if in_range:
    print(sum(in_range))
    print(min(in_range))
else: print(-1)

 

 

1963번: 소수 경로

 

  문제  

 

• 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

“이제 슬슬 비번 바꿀 때도 됐잖아”
“응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
“그럼 8179로 해”
“흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
“흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
“귀찮아”

• 그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

 

  해결 방법  

 

• 이 문제에서는 두 개의 네 자리 수가 주어졌을 때 한 숫자 A를 다른 숫자 B로 바꾸는 과정에서 A와 B 사이에 경로가 존재하는지 확인해야 합니다. 이때 각 단계마다 네 자리 수 중 하나만 바꿀 수 있으며 해당 네 자리 수 역시 반드시 소수여야 합니다.

from collections import deque
import sys; input=sys.stdin.readline

def bfs(start, end):
    q = deque([[start,0]])
    
    while q:
        num, cnt = q.popleft()
        if num == end: return cnt
        for i in range(4):
            for j in range(10):
                temp = num[:i] + str(j) + num[i+1:]
                if temp[0] != '0' and prime[int(temp)] and not visited[int(temp)]:
                    visited[int(temp)] = True
                    q.append([temp, cnt+1])
    return 'Impossible'

prime = [False, False] + [True] * 9999

for i in range(2, int(10000 ** 0.5)):
    if prime[i]:
        for j in range(i+i, 10000, i):
            prime[j] = False

for _ in range(int(input())):
    start, end = input().split()
    visited = [False] * 10000
    print(bfs(start, end))

• 이 문제에서는 너비 우선 탐색(BFS)을 사용하여 시작 숫자에서 목표 숫자로 가는 경로를 찾았습니다. 이때 각 단계에서 가능한 모든 변환을 시도하고, 그 중 소수이며 아직 방문하지 않은 숫자를 큐에 추가합니다.

 

• 소수 판정은 알고리즘 문제 풀이에 있어 핵심적인 요소입니다. 위의 두 문제는 다양한 접근 방식을 필요로 하지만, 모두 소수 판정의 기본 원칙에 기반하고 있습니다.
• 소수 판정과 관련해서 심화적으로 밀러-라빈 검사(확률론적인 방식으로 정확성과 실행 시간 사이에서 균형점을 찾아내며 임의 정밀도 정확성 검사 기능), 평문 분석(RSA와 같은 공개 키 암호 시스템에서 안전성 보장하기 위해 사용되며 큰 정책 상태 공간(search space)를 탐색하기 위해서도 활용)과 같은 주제들도 공부해보시면 도움이 될 것입니다.