프로그래머스 - 세 소수의 합

1. 문제

2. 소스코드(Python3)

def Eratos(n):     if n<10: return []     odd = [i for i in range(n-4)]     odd[0], odd[1] = 0, 0     for i in range(2, n-4):         if odd[i] == 0: continue         for j in range(i*2, n-4, i):             odd[j] = 0     return [i for i in odd if odd[i]]   def add(odd, n):     ans = 0     for x1 in range(len(odd)):         for x2 in range(x1+1, len(odd)):             for x3 in range(x2+1, len(odd)):                 if odd[x1] + odd[x2] + odd[x3] == n:                     ans += 1     return ans   def solution(n):     odd = Eratos(n)     return add(odd, n)

 

3. 고찰

1) Eratos : 에라토스테네스의 체 함수

(1) 알고리즘

대표적인 소수 판별 알고리즘.

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

(2) 코드 구현

이 문제는 세 소수의 합으로 주어진 수를 표현할 수 있는 경우의 수를 구하는 문제이다.

세 소수의 합의 최솟값은 2 + 3 + 5 = 10이다. 따라서 n이 10보다 작으면 세 소수의 합으로 나타낼 수 없기 때문에 계산하지 않고 종료한다.

두 소수의 합의 최솟값은 2 + 3 = 5이다. 따라서 n까지 소수를 구하는 것이 아니라, n-5까지의 숫자 중에서 소수를 구하여 약간의 시간 효율성을 높였다.

odd리스트에 각 인덱스를 입력하고, 해당 숫자가 소수가 아니면 해당 인덱스의 값을 0으로 초기화하였다.

소수가 아닌지 찾는 방법은, 

    (1) i는 2부터 시작하여 n-4까지 반복

    (2) i가 소수가 아니라면 continue

    (3) 소수인 i에 대해서 j는 i*2부터 i를 더하며 n-4까지 반복. 즉, 소수 i에 대해서 j는 i의 배수이다.

    (4) odd[j]를 0으로 초기화한다.

    (5) 모든 for loop를 반복한 후에, 값이 0이 아닌 인덱스의 리스트를 리턴한다.

 

(3) 시간복잡도

i에 대한 for loop -> N번 반복

    j에 대한 for loop -> N/i번 반복

따라서 위 함수의 시간 복잡도는 O(N^2)이다.

 

2) add : 세 소수를 더하는 함수

1) 알고리즘

odd의 세 원소를 꺼낸다.

세 값을 더한 결과가 주어진 수 n과 같은지 비교하여 횟수를 센다.

 

2) 시간복잡도

odd의 원소 개수가 N이라고 하자.

odd의 세 원소에 대해 삼중 for문 -> O(N^3)

 

3) solution : main함수

1) 알고리즘

n이하의 소수를 모두 구하여 odd리스트에 저장한다.

add함수를 이용하여 세 숫자를 더하여 n이 되는 경우의 수를 센다.

 

2) 시간복잡도

Eratos함수의 시간 복잡도는 O(N^2)이다.

add함수는 주어진 입력이 N이라 하면 O(N^3)의 시간복잡도를 가지는데,

입력 N이 주어졌을 때, odd의 원소 개수(즉, N이하 소수 개수)는 N보다도 훨씬 작을 것이다. 하지만, 이 개수를 N에 대해 선형, 로그 등의 값으로 표현하기는 어렵다.

N이 커짐에 따라 N^3은 N^2에 비해 기하급수적으로 커진다. 그래서 해당 시간복잡도를 가지는 두개의 함수를 모두 실행하면 전체 시간복잡도는 N^3이 된다.

하지만, N이 커짐에 따라 N이하 소수 개수 또한 N에 비해 훨씬 작은 값을 가질 것이다.

따라서 위 코드의 시간복잡도는 아마 O(N^2)이 되지 않을까 예상해본다.