알고리즘에서 시간복잡도를 배운 기념으로 풀어보았다.

• Day 25: Running Time and Complexity 문제 보러가기

문제 풀이

시간복잡도라고도 불리는 러닝타임을 줄이는 방향으로 소수(Prime Number)를 판별해보자

문제 해석

Task

• 소수는 자연수 중 1보다 큰 수로, 1과 자기 자신 외에는 나눠지지 않는 수이다. 소수일 경우 ‘Prime’을, 아닐 경우 ‘Not Prime’을 출력하는 코드를 짜보자.
• 여기서 시간복잡도를 O(n)이 아니라 O(n제곱근)으로 하도록 노력해보라.

Input Format

• 첫 번째 줄은 test case의 개수, T가 입력된다.
• 두 번째 줄부터는 소수인지 판별해야 하는 정수 n이 입력된다.

문제 풀이

시행착오

• 처음에 단순하게 들어오는 수를 num이라는 변수에 받아 2부터 num까지의 range에서 모든 수로 나눈 나머지에 따라 소수인지 판별하게 했더니 1을 입력했을 때의 경우가 소수로 판별되어버렸다.
• 가장 처음에 if num == 1을 넣고 나머지 식을 else문에 넣어주었다.
• 이제는 러닝타임 오래 걸려 불합격. 하긴, 문제 자체가 시간복잡도에 대한 건데 이렇게 무식하게 짜면 안되지… 그러나 내 머리로는 해결이 안돼서 검색찬스. 생각보다 간단한 문제였다.
• 1과 자기자신 사이에서 나눗셈이 가능한 경우는 자기자신/2 까지의 수밖에 없으므로 num/2까지로 range를 제한하면 일단 for문 도는 횟수가 절반으로 준다. 하지만 여전히 시간복잡도는 O(n)
• 더 효율적인 계산을 위해서는, 약수의 중간값까지만 계산하는 것이 바로 O(n제곱근)으로 처리가 가능한 방법이다. 약수는 항상 쌍을 이루므로 그 가운데 값까지만 계산하면 소수인지 아닌지 판별이 가능하다.
  • 여기서 약수의 중간값은 자기자신의 제곱근값에 근사하므로, math를 import하여 math.sqrt(num) 값으로 range의 end값을 넣어준다.
  • range는 정수만을 인수로 받으므로 math.floor로 해당 수보다 작은 수 중 가장 큰 정수를 데려온 후 +1을 해주면 우리가 원하는 범위의 값 안에서만 for문이 돌도록 할 수 있다.

코드 작성하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import math

n = int(input())

for _ in range(n):
    num = int(input())
    msg = 'Prime'   
    if num == 1:
        msg = 'Not prime' 
    else:
        for i in range(2, math.floor(math.sqrt(num))+1):
            if num % i == 0:
                msg = 'Not prime'
                break
    print(msg)

느낀 점

• 이렇게 하면 예컨대 80의 소수판별을 위해 80번 포문이 도는 게 아니라 8번 포문이 돈다. 10%로 시간이 줄어드는 혁신적인 방법이다.
• 머리가 나쁘면 손발이 고생하듯 개발자 머리가 나쁘면 컴퓨터가 고생을 한다. 최대한 컴퓨터가 덜 일하는 쪽으로 잘 해보자.
• range 안의 math 메서드들도 조금 지저분한데 정리할 수 있는 방법은 없을까…