[백준/파이썬] 11653번(소인수분해 풀이)

역시나 첫 포스트는 백준 문제 풀이가 되었군요!
간단한 문제였으나, 제 경우 시간 초과 오류가 나서 풀이를 개선하느라 굉장히 풀고 나서 뿌듯했던 문제입니다!

-문제

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

-소스코드(시간 초과 오류 개선 전)

import math
num = int(input())

T = []
	
SS = [2]

for i in range(3, num):
	Yaksu = []
	for j in range(1, len(SS)+1 ):
		if i % SS[j-1] == 0:
			Yaksu.append(SS[j-1])
			
	if len(Yaksu) == 0:
		SS.append(i)
		


for w in range(1, len(SS)+1):
	while num % SS[w-1] == 0:
		num /= SS[w-1]
		T.append(SS[w-1])
	if num == 1:
		break
if len(T) == 0:
	T.append(num)

for f in range(1, len(T)+1):
	print(T[f-1])

-소스코드(최종 정답)

import math
num = int(input())

T = []
SS = [2]

for i in range(3, int(math.sqrt(num))+2):
	Yaksu = []
	for j in range(1, len(SS)+1 ):
		if i % SS[j-1] == 0:
			Yaksu.append(SS[j-1])
			
	if len(Yaksu) == 0:
		SS.append(i)
		


for w in range(1, len(SS)+1):
	while num % SS[w-1] == 0:
		num /= SS[w-1]
		T.append(SS[w-1])
	if num == 1:
		break
		
if num != 1:
	T.append(int(num))

for f in range(1, len(T)+1):
	print(T[f-1])

-풀이 과정

소인수분해는 결국, 주어진 숫자에 대해서, 주어진 숫자보다 작은 소수들을 지속적으로 나눠가면서 숫자를 구성하는 모든 소수를 출력하는 것이 핵심인 문제이죠.
그래서 저는 입력값보다 작은 소수들을 모두 구해서 SS리스트에 추가했어요.
이미 기존 SS리스트를 정의할 때 기본적으로 가장 작은 소수인 2를 추가했기 때문에 소수를 구할 때에는 'SS리스트에 포함된 숫자들에 대해서 단 한번도 나누어 떨어지지 않으면 소수다'라는 논리를 적용하면 되었어요.
이렇게 입력값보다 작은 소수를 모두 구하고, 이 소수들로 입력값을 나누어보며 입력값을 나누어 떨어지게 하는 소수들을 T리스트에 넣어서 최종적인 답을 출력했어요.
하지만 이런 직관적인 풀이과정을 코드에 그대로 대입하다보니, 3부터(1은 소수가 아니고, 2는 소수라는 사실을 알기에 이미 SS리스트에 추가해놓아서 제외) '입력값-1'까지를 모두 소수가 아닌지 판별하는 과정에서 너무나 불필요한 연산을 하게 되었어요.
그래서 시간 초과가 되었고, 이를 해결하기 위해 꽤나 단순한 이치를 사용했어요.
바로 어떤 수를 두 수의 곱으로 나타낼 때, 그 두 수는 타겟이 되는 수의 제곱근을 기준으로 크고 작음이 나누어진다는 거에요.(물론 어떤 수가 4와 같은 제곱수라면 2와 2의 곱처럼 동일한 수 두개의 곱으로 나타날 수 있곘지만요)
예를 들어 20이라는 수가 있다고 해보아요.
20은 1과 20의 곱으로 표현 되고, 그 이후로는 2과 10의 곱으로 표현될 수 있겠죠? 하지만 점점 작은 수를 크게 만들면서 짝을 이루게 하다보면 마지막에 4와 5의 곱으로 짝이 지어지는데 이 4와 5는 20의 제곱근보다 각각 크고 작다고 볼 수 있어요.
그렇기 떄문에 20이든 어떤 수든 간에 그 수를 두 수의 곱으로 나타내고자 할 때에는 그 수에 제곱근을 씌운 값 이하인 수만 구하고, 그 수에 직접 나누어줌으로서 해당 수를 나누어 떨어지게 하는 모든 조합을 구할 수 있어요.
그렇기 때문에 시간 초과 오류를 개선한 코드에서는 소수를 구하는 과정을 입력값 -1 까지 진행하는 것이 아니라, (입력값//2 +1) 까지 진행하는 걸로 대폭 연산량을 감소시켰어요.
이런 다사다난한 과정을 통해 최종 소스코드가 나왔답니다!