백준 11653 소인수분해 파이썬 풀이

🧩 파이썬 문제풀이: 소인수분해 (백준 11653)

안녕하세요! 오늘은 백준 알고리즘 문제 중 하나인 11653번 소인수분해 문제를 직접 풀어본 경험을 바탕으로, 내가 어떻게 문제를 이해하고, 접근하고, 구현했는지 단계별로 정리해보겠습니다.

📌 문제 요약

정수 N이 주어졌을 때, 이를 소인수분해한 결과를 한 줄에 하나씩 출력하는 문제입니다.

조건:

• N이 1인 경우에는 아무것도 출력하지 않음
• 그 외에는 소수로만 구성된 인수를 오름차순으로 한 줄에 하나씩 출력

💭 내가 문제를 풀기 전에 했던 생각들

1️⃣ "소인수분해"가 뭐지?

처음에 "소인수분해"라는 단어 자체가 헷갈렸습니다.
그래서 이런 식으로 스스로 질문을 던지며 접근했습니다:

• 소인수분해란? → 어떤 수를 소수의 곱으로 나누는 것
• 소수란? → 1과 자기 자신만을 약수로 가지는 수
• 약수는 어떻게 구하지? → 어떤 수 n을 k로 나눴을 때 n % k == 0이면 k는 n의 약수

결론:

2부터 시작해서 num이 나눠떨어질 때마다 출력하고, 나누고,
안 나눠지면 k를 하나씩 올리자!

✅ 내가 처음 작성한 코드

# 입력받기
num = int(input())

while num > 1:
    k = 2
    while k <= num:
        if num % k == 0:
            print(k)
            num = num / k
        else:
            k = k + 1

🔍 코드 설명

• num > 1인 동안 계속 나눕니다.
• 매번 2부터 시작해서 k <= num인 동안 나눠질 수 있는 k를 찾습니다.
• num % k == 0이면 k는 소인수 → 출력하고 num을 k로 나눕니다.
• 나눠지지 않으면 k += 1로 다음 후보를 확인합니다.

🔎 실행 예시

입력:

72

출력:

2
2
2
3
3

72 = 2 × 2 × 2 × 3 × 3

⚠ 개선할 점 (피드백)

사용자님의 코드도 정확히 동작하지만, 몇 가지 개선 포인트가 있습니다.

📌 1. 매번 k를 2부터 다시 시작할 필요는 없음

현재 코드는 num > 1인 동안 계속 k = 2부터 다시 시작합니다.
이럴 필요 없이, k는 한 번만 초기화하면 됩니다.
즉, 바깥 while문은 필요 없습니다.

📌 2. 나눌 때는 //를 써야 함

지금은 num = num / k → 이건 실수형(float)이 됩니다.
정수만 다뤄야 하므로 // 연산자를 써야 합니다.

📌 3. 시간 효율 개선 가능

이 문제에서는 제한 범위가 1 ≤ N ≤ 10,000,000이기 때문에
sqrt(N)까지만 반복해도 충분히 빨리 동작합니다.
하지만 여기서는 단순한 코드로 이해를 먼저 하고, 효율 개선은 나중에 공부해도 좋습니다.

✨ 개선된 코드 (깔끔한 버전)

n = int(input())
k = 2

while n > 1:
    if n % k == 0:
        print(k)
        n //= k
    else:
        k += 1

변경 사항 요약:

• k를 함수 밖에서 한 번만 정의
• 나눗셈을 정수 나눗셈 //로 변경

📚 핵심 개념 요약

개념	설명
소인수분해	어떤 수를 소수들로 나누어 떨어지게 분해하는 것
소수	1과 자기 자신만을 약수로 가지는 수
방법	2부터 시작해서 나눠지면 나누고 출력, 안 되면 다음 수로 진행
반복 범위	이 문제에서는 최대 10,000,000까지 처리해야 하므로 효율적 구현도 중요

C++ 코드

#include <iostream>

using namespace std;

int main(void)
{
	int N;
	cin >> N;

	while (N > 1)
	{
		
		int k = 2;
		while (k <= N)
		{
			
			if (N % k == 0)
			{
				cout << k << endl;
				N = N / k;

			}
			else
			{
				k++;
				
			}

			
		}
	}
	return 0;
}

✅ 마무리

이 문제를 풀면서 느낀 점은:

쉬워 보이는 문제도 개념부터 정확히 이해하고,
작동 원리를 단계별로 생각하면서 구현해야 더 잘 풀린다!