[Baekjoon] 백준 #11653번 파이썬 해답

 

baekjoon online judge의 단계별로 풀어보기 중 수학 부분입니다.

 

기본 수학 2, 일명 소인수분해 입니다.

 

분명 기본 수학이라고 되어있지만, 기본 단계는 아닌것 같습니다.

문제부터 한번 보겠습니다. 내용은 자체는 심플합니다.

 

문제

 

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

입력/출력

 

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

 

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

해답

N = int(input())
if N == 1:
   print('')
else:
     for i in range(2,N+1):
         while N%i == 0:
               print(i)
               N = N / i

 

 

아래는 초등수학 과정에서 우리가 배우는 소인수분해를 유도하는 과정입니다.

 

 

 

이 문제를 풀면서 소인수분해의 개념 자체를 되짚어 가는 것도 좋은 접근방법으로 보입니다.

 

숫자 N을 소인수분해 한다고 했을때, 먼저 N의 약수 중 가장 작은 수를 찾습니다.

가장 작은 수로 나누었을 때, 몫을 구하고 그 몫의 약수 중 가장 작은 수를 찾습니다.

다시 가장 작은 약수로 나눠주고 그 몫을 구하여 가장 작은 약수를 반복하는데요.

 

이 과정을 끝없이 반복하다가 약수로 나눈 몫이 '소수' 즉 1과 자기 자신으로만 나눠지는 수가 될때

분해하는 과정을 종료합니다.

 

그리고 약수와 몫들을 전부 찾아주는 것이죠.

 

이쯤 되면 파이썬으로 접근하는 방식에 감이 오기 시작합니다.

중요한 포인트는 이렇듯 약수가 소수가 될때까지 끝없이 나눗셈을 반복한다는 부분인데요?

그래서 while문을 사용합니다.

 

이쯤 되면 파이썬으로 접근하는 방식에 감이 오기 시작합니다.

 

   while N%i == 0 :
         print(i)
         N = N/i

 

for문을 넣어주고, 독특하게도 N이 1인 경우 아무것도 출력하는 조건이 있었습니다.

 

if N == 1:
   print('')
else:
     for i in range(2,N+1):
         while N%i == 0:
               print(i)
               N = N / i

 

잘못된 코드 예시

 

N = int(input())

if N == 1:
   print('')
for i in range(1,N+1): # i = 1,2,3,4,5,6,7,8,9,10...
    while N%i == 0 :
          print(i)
          N = N/i

1
1
1
1
...

에러가 발생하는 예시입니다.

 

for 문을 1부터 시작하면 1이 끝없이 생기는 무한 루프가 발생합니다.

1로 나눠도 계 나머지가 0이기 때문이죠

 

range()의 start부분만 유의하시면 되겠습니다.

 

 

N = int(input())
if N == 1:
   print('')
else:
     for i in range(2,N+1):
         while N%i == 0:
               print(i)
               N = N / i

 

BOJ에서 채점시 상당히 시간이 많이 소요되는 부분이 있습니다.
소인수분해를 체크하는데 시간복잡도가 많이 잡히는 경우가 있는 것으로 보입니다.
추후 해결해야 겠습니다.

 

끝.