[C/Python] 약수, 배수와 소수 2

🚀 [알고리즘 정복] 약수, 배수와 소수: 기초에서 최적화까지

오늘은 백준의 '약수, 배수와 소수 2' 단계를 파헤치며, 단순한 반복문이 아닌 수학적 통찰을 통해 코드를 최적화하는 과정을 기록합니다.

1. 에라토스테네스의 체와 누적 합 (베르트랑 공준)

소수를 매번 구하는 것은 비효율적입니다. 미리 소수 지도를 그려두는 **'에라토스테네스의 체'**를 사용했습니다.

• 핵심 아이디어: 2부터 시작해 그 배수들을 모두 지워나가면 남는 것은 소수뿐이다!
• 최적화 팁: n보다 크고 2n보다 작은 소수의 개수를 빠르게 구하기 위해 누적 합(Prefix Sum) 배열을 도입했습니다.
• C언어 주의점: 배열 크기가 커지면 char 자료형은 오버플로우가 발생하므로 반드시 int 이상을 사용해야 합니다.

---

2. 골드바흐의 추측 (17103번, 9020번)

"2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다"는 흥미로운 문제를 풀었습니다.

• 문제 해결 전략:
  1. 미리 소수 배열(check)을 만든다.
  2. 입력받은 짝수 m에 대해, j가 소수이고 m - j도 소수인지 체크한다.
• 최적화: 2부터 m / 2까지만 검사하면 중복 없이 모든 파티션을 찾을 수 있습니다.
• C언어 메모리 관리: malloc으로 할당받은 메모리는 free로 반드시 해제하며, scanf 실패 시에도 자원이 누수되지 않도록 break 문을 활용한 예외 처리를 적용했습니다.

---

3. 창문 닫기 (제곱수의 비밀)

n개의 창문을 n명이 규칙에 따라 열고 닫을 때, 마지막에 열려 있는 창문을 찾는 문제입니다.

• 반전의 수학: 이 문제는 사실 **"약수의 개수가 홀수인 숫자가 몇 개인가?"**를 묻는 문제입니다.
• 결론: 약수의 개수가 홀수인 수는 오직 제곱수뿐입니다.
• 최적화의 정점: O(N \log N)의 시뮬레이션 코드를 **O(1)**의 sqrt(n) 한 줄로 줄이는 쾌거를 이뤘습니다.

---

💡 오늘 배운 C언어 자료형 체급 정리

알고리즘의 성능만큼 중요한 것이 올바른 자료형 선택입니다.

• char (1 byte): 매우 작은 숫자나 상태 값 (256가지)
• short (2 bytes): 3만 안팎의 데이터
• int (4 bytes): 일반적인 카운팅, 약 21억까지
• long long (8 bytes): 천문학적인 숫자나 21억을 넘어가는 계산

---

📖 정보처리기사 실기 포인트 (2026 대비)

• 단락 평가(Short-circuit): if (A || B)에서 A가 참이면 B는 검사하지 않는다.
• 메모리 누수: malloc 후 free를 하지 않으면 자원이 낭비된다.
• 알고리즘 복잡도: 반복문을 수학 공식으로 대체하는 것이 최상의 최적화이다.