작심큰일 챌린지 - Day 1. 소수 만들기 (미들러, Python)

출처 - 작심큰일 챌린지 메인 페이지

 

스파르타코딩클럽에서 주관하는 작심큰일 챌린지에 참가했다.

 

출처 - 작심큰일 챌린지 메인 페이지

 

해당 챌린지는 8월 4일부터 8월 17일까지 2주간 진행되는 과정으로, Java 또는 Python 언어 중 지원한 언어로 매일 1문제의 알고리즘 문제를 학습 및 회고한다. 주말에는 보너스 문제도 풀 수 있다. 아무튼 좋은거임

 

최근 알고리즘 공부를 거의 안 하고 있어서 Python 코드를 까먹을 지경이라, 스스로에게 강제성을 부여할 수 있는 좋은 기회라고 생각했다.

 

특히 문제를 풀고 나서는 시니어 레벨의 현직 개발자 분의 풀이법 및 해설을 볼 수 있는 점이 학습에 큰 도움이 될 것 같았다. 

 

출처 - 작심큰일 챌린지 메인 페이지

 

간단한 입출력 및 기본적인 자료구조를 알기도 했고, 내 수준보다 좀 더 어려운 알고리즘을 풀기 위해 노력하는 것이 더 좋을 것 같아서, "미들러" 레벨로 지원했다.

 

오늘은 첫날이라 과정 설명이 들어가 있지만, 이후에는 좀 더 간단한 TIL만 2주 동안 작성할 예정이다.

 

---

Day 1. 소수 구하기

 

과제는 별도의 본문이 있는 것 같지는 않고, 문제에 대한 링크를 제공하는 것으로 보인다. 첫 문제는  백준 프로그래밍 1929번 문제였다.

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

예제 입력 1

3 16

 

예제 출력 1

3
5
7
11
13

 

---

풀이 과정

 

풀이 전에 먼저 문제의 핵심적인 부분들을 정리했다.

 

1. 소수는 어떻게 구하는가?
2. 어떻게 M 이상 N 이하의 소수를 구할 수 있는가?
3. 해당 과정을 어떻게 파이썬 코드로 표현할 것인가?

 

해당 질문들에 대한 답을 스스로 적어보면서 문제에 접근했다.

 

---

 

1. 소수는 어떻게 구하는가?

 

먼저 소수를 구할 수 있는 조건에 대해 생각해 봤다.

 

소수는 인수로 1과 자신만을 가지고 있다. 즉, 주어진 수 $n$을 2부터 $\sqrt {n}$까지의 모든 정수로 $n$을 나눠보고, 하나라도 나누어 떨어지는 수 (= 약수)가 없다면 $n$이 소수임을 알 수 있다.

 

가장 먼저 떠오른 방법은 재귀함수였다.

 

def is_prime_recursive(n, divisor=2):
    if n <= 1:
        return False            # 1 이하인 경우 소수가 아님
    if divisor * divisor > n:
        return True             # 제곱근을 넘기면 소수임이 확정
    if n % divisor == 0:
        return False            # 나누어떨어지면 소수가 아님
    return is_prime_recursive(n, divisor + 1)   # 다음 수로 재귀 호출

 

주어진 정수값이 하나라면 소수를 구하기에 충분히 괜찮은 방법이라고 생각한다.

 

하지만 우리는 M 이상 N이하의 각 수의 소수 여부를 확인해야 되기 때문에 재귀로 구현하는 것은 매우 비효율적임을 알 수 있다. 특히 하나의 수가 아니기 때문에 재귀 깊이와 연산량이 기하급수적으로 늘어날 것이 뻔했다.

 

---

 

2. 어떻게 M 이상 N 이하의 소수를 구할 수 있는가?

 

일단 소수를 구하는 기본적인 원리는 알았으니, 먼저 의사 코드를 작성해 보았다.

 

i. M과 N을 입력받음 → map(int, input(). split())
ii. 동적계획법(DP)으로 주어진 값을 미리 할당 → [True] * (N + 1)
iii. 2부터 N의 제곱근까지 배수 지우기

 

문제는 3번 과정에서 발생했다.

 

어떻게 해야 2부터 N의 제곱근까지 배수를 "효율적으로" 지우고 체크할지 감이 잘 오지 않았다.

 

이때, 알고리즘 분류에서 봤던 "에라토스테네스의 체"에 대해 학습했다.

 

에라토스테네스는 고대 그리스의 수학자로, 체(=거름망)로 수를 걸러내는 아이디어를 떠올려 소수를 찾는 효율적이고 체계적인 방법을 고안해 냈다. 에라토스테네스의 체의 작동 원리는 다음과 같다.

 

i. 2부터 N까지 모든 수를 나열
ii. 2부터 시작해서 자기 자신을 제외한 배수를 모두 지움
iii. 지우지 못한 수는 소수
iv. √N까지만 반복
v. 마지막에 남은 수(체로 거르듯 남은 것)가 해당 범위 내 모든 소수

 

필요한 부분들은 충족이 된 것 같으니, 구현 단계로 넘어갔다.

 

---

 

3. 해당 과정을 어떻게 파이썬 코드로 표현할 것인가?

 

이미 앞서 의사 코드로 작성해 본 부분들이 있기 때문에, 에라토스테네스의 체를 알고리즘적으로 표현하기만 하면 됐다.

 

import sys

input = sys.stdin.readline

M, N = map(int, input().split())
is_prime = [True] * (N + 1)
is_prime[0] = is_prime[1] = False

# 에라토스테네스의 체
for i in range(2, int(N ** 0.5) + 1):
  if is_prime[i]:
    for j in range(i * i, N + 1, i):
      is_prime[j] = False

# M 미만을 모두 False로
for idx in range(M):
    is_prime[idx] = False

# 출력
for num in range(M, N + 1):
    if is_prime[num]:
        print(num)

 

생각해 보는 과정이 어려웠지만, 직접 코드로 적고 구현하는 과정 자체는 크게 어렵지 않았다. 어렵지 않았다고 했지 한 번에 했다고는 안함

 

오히려 무서웠던 건...

 

출처 - 위키백관

 

이 아저씨였다.

 

출처 - tumblr kpfun

 

“합성수는 반드시 소인수분해로 표현할 수 있다”는 사실, 그리고 “이미 작은 소수 배수에서 걸러진 수는 굳이 다시 체크하지 않아도 된다”는 점을 경험적, 논리적으로 알았다는 것인데... 정말 무서울 따름이다.

 

---

개선점

 

스스로 알고리즘을 상당히 유사하게 구현한 것 같아 뿌듯했지만, 여전히 개선점은 존재했다.

 

시니어 해설(반말? 느낌으로 해설이 적혀있는데 친근해서 좋았다)에서 짚어준 핵심 포인트는 다음과 같았다.

 

- 소수의 정의를 명확히 이해할 것
- 제곱근까지만 나눠보는 방식이 최적화의 핵심
- for-else 문법으로 깔끔하게 조건 처리

 

소수의 정의나 제곱근까지 나누는 최적화 부분은 괜찮았는데, 의외로 for-else 문법으로 깔끔하게 조건 처리하는 부분을 생각하지 못했다.

 

내가 작성한 코드가 개인적으로 좀 더 이해하기는 편하다는 생각은 들었는데, 끝까지 최적의 효율을 보여준 코드는 아니었다고 생각한다.

 

굳이 순회 후 다시 해당 배열을 순회해서 출력하는 것보다는 순회하면서 체를 모두 통과한 수는 소수로 바로 표시하는 것이 더 깔끔하다는 점에서 크게 동의했다.

 

N, M = map(int, input().split())

for i in range(N, M + 1):
    if i == 1:
        continue
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            break
    else:
        print(i)

 

결국 코드가 길어지면 가독성이 떨어지는 것이 맞고, 해설 코드가 한 줄로 작성된 극한의 압축도 아니었기 때문에 이해하는데 충분했다.

 

첫날부터 많은 배움이 된 것 같다.