B1929

개요

백준 문제 1929번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 30분
https://www.acmicpc.net/problem/1929

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

코드

#include <iostream>
const int MAX = 1000001;
bool check[MAX];
	
using namespace std;

void solve()
{
	fill_n(check,MAX,false);
	check[1] = true;
	int M,N;

	cin >> M >> N;
	for(int i=2;i<=N;i++)
	{
		for(int j=2; i*j <= N;j++)
		{
			check[i*j] = true;
		}
	}

	for(int i=M;i<=N;i++)
	{
		if(!check[i])
		{
			cout << i <<"\n";
		}
	}



}

int main()
{
	solve();
}

풀이

문제를 읽고 일반적으로 생각하는 A-1숫자부터 2까지 나머지를 체크하는 방식은 시간초과가 뜰 것 같았다.
그 다음으로는 짝수인 경우가 많을 것이라 생각하여 숫자 (A-1 % 2) == 0 이면 break하도록하여 조금 더 개선했지만
이렇게는 시간복잡도는 줄어들지 않는다.
여기서 아예 내가 모르는 방법이 있구나 하여 검색해보았다.
찾아보니 에라토스테네스의 체라는 방법이 있었다
(A-1 % 2)에서 2 대신 2부터 최대 범위가 되기 전까지의 수를
2부터 곱한 것(2부터 하는 이유는 자기자신을 제외하기 위해)에 마킹을 한다.
연산을 다 마치고 나면 마킹이 되지 않은 것은 소수라는 의미이다.

배울 점, 메모

이번 문제는 한 30분 생각하다 검색해서 정답을 알게 된 문제인데
내 스스로 생각하여 완벽하게 풀지 못한 것이 마음에 걸렸다.
내가 오랫동안 생각했다면 풀 수 있었을까?
오랫동안 생각했다면 그럴만한 가치가 있는가?라는 생각이 곧 떠올랐다.
스스로 생각해본 결과 1시간 이상 넘어간다면 모르는 것으로 간주하고
여러 유형을 배우고 익히는 것이 먼저라는 결론이 나왔다.
항상 스스로 할려고 하는 것은 나쁜게 아니지만,
엄청나게 많은 문제를 풀기 위해서는 조금 다르게 생각해야 할 것 같다
결과론적으로 생각해봤을 때 알고리즘을 잘하는 방법은 많이 풀어보는 수 밖에 없기 때문에
오랫동안 생각했다면 풀 수 있었더라도, 문제를 풀지 못해 스스로에게 실망하더라도
좌절한 시간조차도 노력으로 나중의 나에게 돌려주면 된다고 생각한다.