[오늘의 정수 정수 정상수] 에라토스테네스의 체

잡소리

많은 사람들이 '꾸준히'를 목표로 많이 잡는다. 나도 그렇다. 그랬었다. 어제는 그렇지 못했다.
흔히 말하는 번아웃이 왔다고 핑계대고 싶지만 번아웃이 올만큼 꾸준히 열심히 공부를 안했던 거 같지만
어제는 번아웃인 걸로 계산하도록 해야겠다.
(하루 통째로 아무 것도 안하고 쳐 놀아놓고 핑계를 대는 중이다.)

어제의 나는 무기력 그 자체였다. 인간 무기력 김무기징역씨는 그렇게 하루 종일 슬더스를 했으며
단검 도적의 참 맛을 통해 카타르시스를 느끼고 무언가 잘못된 것을 직감한 시간은 새벽 5시였다고 한다.
지나간 것은 지나간대로 그런 의미가 있다고 하지만, 지난 날에 머물러 있는 나의 코딩 실력은 그렇게 의미가 있지 않다고 소리치고 있다. 그래서 오늘은 이 악물고 알찬 구현의 시간을 가져보기 위해 백준에 들어갔고, 내 눈에 보인 태그는 #에라토스테네스의_체 였다.

에라토스테네스의.... 체.....체....췤 디싸웃 나는 정상쑤! 백발백중 하는 명 사 쑤!
예전에 개요를 찾아봤으니 한번 더 복습을 하고 바로 문제풀이로 들어갔으며,
실딱이였던 나는 골3 문제를 풀어내는 기염을 토해냈다.

고맙습니다 상수형님.....

#Sieve of Eratosthenes (기울어진 영어폰트는 항상 뭔가 그럴싸해 보일 때 좋다.)
비빔면 끓일 때 쓰는 체보다 유용하다!

자연수 n보다 작거나 같은 소수(prime number)들을 찾아내는 가장 간단하고 빠른 방법으로,
보이지 않는 수들이 걸러져 나가는 모습을 시각화할 수 있는 아름다운 방법이다.

방법은 굉장히 심오하지만 간단하다.
n까지 숫자를 쭉 나열하고 앞에서부터 소수들을 제외하고 싹 모가지를 치는 것이다.
단, 모가지를 치는데 규칙이 있을 뿐이다.

(100까지를 예로 들어보자면)
i. 우선 '1', 1등만 기억하는 더러운 세상을 미워하는 마음으로 제거한다.
(1은 소수도, 합성수도 아니니깐 지우는거다. 그냥 지우고 싶어서 지우는게 아니다.)

ii. '2'를 제외한 2의 배수들을 모두 해고시킨다. (4, 6, 8, 10 ...... 100)
iii.'3'을 제외한 3의 배수들을 모두 짤라버린다. ((6), 9, (12), (15) .... 99)
(중간에 괄호 처리 된 것은 ii에서 이미 지워진 친구들이란 것을 나름 열심히 표현해 본 것이다.)

4의 차례가 찾아왔다. 근데 아쉽게도 4는 지금 단계까지 버티지 못하고 ii에서 중간에 짐을 싸서 나가버렸다. 그렇다면 어떻게 해야할까?
iv. 4의 빈자리 옆에 5는 자신의 미래를 알지 못하고 웃으며 앉아 있다. 이 친구의 배수들도 제거해주자.

이런 식으로 쭉쭉 전개를 해준다. 언제까지? 100의 제곱근 전까지!
( 10보다 작은 수들에 대해서 지워주는 과정을 해주는 것이니 2, 3, 5, 7에서 그 과정이 일어난다.)

그 뒤으 숫자들은 소수 * 소수인 친구들만 지워주면 된다. ex. (7 x 7), (7 x 11), (7 x 13)

짧게 설명하고 가자면, 100 = a x b로 표현할 때, a , b중 하나는 무조건 sqrt(100) 이기 때문이다.
11 x 2는 이미 2 x 11에서 제거 당했고, 11 x 3 은 3 x11에서 제외빔을 맞았기 때문이다.
나는 이를 좀 더 그럴싸하게 '수의 Daechingseong'이라고 말해볼까 한다.

코드로 구현한 에라토스테네스 선생님의 체

void ft_prime(int n) {
	for (int i = 2;i <= n;i++)
		arr[i] = i;
	for (int i = 2; i <= n;i++) {
		if (arr[i] == 0) continue;
		for (int j = i * 2;j <= n;j += i)
			arr[j] = 0;
	}
}

이 것이 n까지의 소수들이 살아남는 더 췌 오브 에라토스테네스 이다.

동작 원리를 잠깐 설명해보자면

for (int i = 2;i <= 100;i++)
		arr[i] = i;

(편의상 n == 100인 경우로 설명해보자.)
이 부분에서 int 배열 arr에 자기자신에 해당하는 i에 숫자들이 들어간다. (arr[2] = 2, arr[3] = 3 ...)

for (int i = 2; i <= n;i++) 전체 반복문의 범위는 2부터 n까지 돌면서

if (arr[i] == 0) continue; 만약 이미 정리해고를 당했으면 뒤의 작업은 생략하고,

for (int j = i * 2;j <= n;j += i) arr[j] = 0; 그게 아닐 경우 이제 체로 거르는 과정을 시작한다.
이 반복문에서 유의해서 봐야할 것은 i 본인은 살아남는 다는 것이다. ( 시작점 j가 ix2부터 시작이니깐)
반복문이 돌아가는 과정을 보면, i x 2, i x 3, i x 4 ..... 이렇게 지워져 나간다.

• 위에서 언급했던 작업 중에 sqrt(100)까지만 작업하고 뒤에 예외를 처리하는 방식보다
  그냥 100까지 확인하며 밀어버리는 작업을 택한 이유는.... 예외처리 힘들다....
  내가 비싼 돈주고 컴퓨터를 고용했으니 컴퓨터에게 반복문을 처음부터 끝까지 돌라고 하자.

이 작업을 모두 마친 뒤, 보기 좋게 새로운 int 배열에다가 한 줄로 옮겨주는 작업을 거쳐보았다.

int ft_mkarr(int n) {
	int a = 0;
	for (int i = 2;i <= n;i++)
		if (arr[i] != 0) {
			ans[index] = i;
			index++;
		}
	return index;
}

그냥 arr[i] 가 0이 아닌 경우 ans[index]에다가 차근차근 넣어주는 것 뿐이다. 그리고 그 index값을 main에서 재활용하기 위해서 int함수로 잡고, return을 index 값으로 반환한 것이다.

체를 돌린 결과가 이렇게 이쁘게 잘 나온다.

그렇다 아무리 '두뇌 풀가동!'을 외쳐도 6과 8은 이 체를 뚫고 들어가지 못한다.
아마 저 6도 구멍이 막혀있을 것이다.....

혼란을 틈탄 자기자랑 ( 백준 1644번 풀이)

결국 이 글을 쓴 이유가 뭐냐? 앞에서도 얘기했던 것처럼 오랜만에 Gold 문제 풀이에 성공했다.
맞았습니다!가 뜨고 신나서 친구들에게 자랑하려고 핸드폰을 봤지만, 앗차차..... 나 친구 없었지.....
그래서 다시 블로그에 글을 쓰는거다. 언제가 될 지 모르겠지만 이 글을 보게될 당신, 나를 위해 축하를 해주지 않겠나......

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

	3 : 3 (한 가지)
	41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
	53 : 5+7+11+13+17 = 53 (두 가지)
    
하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 
7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 
또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력 범위 : N ( 1 ≤ N ≤ 4,000,000 )

출력 방법 : N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수

응애 나 애기블로거 캡처하면 안 이쁜데 이쁘게 꾸밀 방법을 몰라서 코드에 복붙해서 꾸밈

이 문제는 더 췌 오브 에라토스퉤네스 를 이용한 뒤 두 포인터 풀이 방식을 채택하면 된다.

#include<stdio.h>

int arr[4000001] = { 0 };
int ans[2000001] = { 0 };

void ft_prime(int n) {
	for (int i = 2;i <= n;i++)
		arr[i] = i;
	for (int i = 2; i <= n;i++) {
		if (arr[i] == 0) continue;
		for (int j = i * 2;j <= n;j += i)
			arr[j] = 0;
	}
}

int ft_mkarr(int n) {
	int a = 0;
	for (int i = 2;i <= n;i++)
		if (arr[i] != 0) {
			ans[a] = i;
			a++;
		}
	return a;
}

여기까지는 위에 언급한 에라토스테네스의 체 + 소수들만 옹기종기 모여있는 배열 만들기 함수다.

int main() {

	int n, index, sum;
	int left = 0;
	int right = 0;
	int cnt = 0;
    
	scanf("%d", &n);
    
	ft_prime(n);
	index = ft_mkarr(n);
    
	sum = ans[0];
    
	while (left <= right && right < index) {
		if (sum >= n) {
			if (sum == n)
				cnt++;
			sum -= ans[left++];
		}
		else {
			right++;
			sum += ans[right];
		}
	}
    
	printf("%d", cnt);
    
	return 0;
}

이게 풀이 해결해낸 main 함수
index = ft_mkarr(n); 를 통해서 탐색 범위를 지정해줌과 동시에 위의 함수를 써서 환경변수로 나가계신 ans 배열이 채워진다.

두 포인터 풀이 방식을 간단히 설명하고 넘어가자면, left 와 right라는 변수를 포인터로 활용해서
ans 배열의 left ~ right 사이의 값들을 다 더한 것을 n과 비교해보며 이하의 작업을 계속 반복한다.

• sum > n 인 경우, left를 오른쪽으로 한칸 땡긴다.
• sum == n 인 경우, 경우의 수 1개를 체크하고, left를 오른쪽으로 한칸 땡긴다.
• sum < n 인 경우, right를 오른쪽으로 한칸 뒤로 민다.

이 작업을 계속해서 반복하다가 left가 right를 넘어가 버리거나, right가 index와 같아져 버리면 반복문 끝!
( 언젠가 그림판으로 그려가며 설명하는 글을 쓰도록 해보자)

그 결과

내가 해냈다 이제 성불해도 된다.

아이디는 개인정보라 유출시 위험하다고..... 우리 엄마가 그랬다 반박시 패드리퍼

결국 월요일에 골드찍겠다고 선언하고 4일만에 (하루 놀았지만) 골드 달성 성공했다.

오늘은 기분 좋게 놀 수 있을거 같다. 다음에 더 알차고 유익한 정보글을 쓰고 싶게 된다면 다시 찾아오도록 하겠습니다. 그렇다면 이만 주인장 슬더스 하러간다~