개요

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

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
using namespace std;

void solve()
{
	int num;
	cin >> num;
	if(num == 0)
	{
		cout << 1;
		return;
	}
	else
	{
		int result = 1;
		while(num != 1)
		{
			result *= num ;
			num--;
		}
		cout << result;
	}
}


int main()
{
	solve(); 
}

풀이

배울 점, 메모

개요

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

문제

소인수분해 구하기

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <iostream>
using namespace std;

void solve()
{
	int num;
	int modNum = 2;
	cin >> num;


	while(num != 1 && num != 0)
	{
		if(num % modNum == 0)
		{
			cout << modNum << endl;
			num /= modNum;
		}
		else
		{
			modNum++;
		}


	}

}

int main()
{
	solve();


}

풀이

배울 점, 메모

개요

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

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.
4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.
이 추측은 아직도 해결되지 않은 문제이다.
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

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

void checkPrimeNum(int val)
{
	for(int i=2;i<=val;i++)
	{
		for(int j=2;i*j<=val;j++)
		{
			check[i*j] = true;
		}
	}
}


void solve()
{
	int val = -1;
	int count = 0;
	int maxVal = 0;
	fill_n(problem,MAX,0);
	fill_n(frontVal,MAX,0);
	fill_n(check,MAX,false);
	fill_n(backVal,MAX,0);
	do
	{
		cin >> val;
		if(val != 0)
		{
			problem[count++] = val;
		}
		if(maxVal < problem[count-1])
		{
			maxVal = problem[count-1];
		}

	}while(val != 0);
	
	checkPrimeNum(maxVal);

	for(int testCase=0;testCase<count;testCase++)
	{
		for(int iter = 3;iter < problem[testCase]; iter++)
		{
			if(!check[iter] && !check[problem[testCase] - iter])
			{
				cout << problem[testCase] << " = " << iter << " + " << problem[testCase] - iter<< "\n";
				break;
			}
		}
	}

	
}

int main()
{
	solve();
}

풀이

이전에 배웠던 알고리즘인 에라스토테네스의 채 알고리즘으로 해결할 수 있는 문제이다.
처음에는 이 접근 방식 자체는 맞았지만 시간 초과가 뜨길래 뭔가 더 최적화 해야하는 줄 알고 몇가지 시도를 했었으나 그것이 문제가 아니었고 내 코드의 문제는 다음과 같았다.
if(!check[iter] && !check[problem[testCase] - iter])
이 부분은 앞의 값 + 뒤의 값 = 더한 값이면서 소수인 값을 찾는 부분인데,
나는 이 뒤의 값을 찾을때 바보같이 더한 값에서부터 -1을 하면서 찾았다.
그냥 당연히 A + B = C라면 B = C - A인데 이 점을 생각하지 못했다..
어쨌건 그부분은 검색을 통해 알아냈고 수정하니 바로 AC가 떴다.

배울 점, 메모

좀..수학이 약한듯
문제에서부터 어떤 규칙이나 명백한 식같은걸 이끌어 내야함

개요

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

문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#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시간 이상 넘어간다면 모르는 것으로 간주하고
여러 유형을 배우고 익히는 것이 먼저라는 결론이 나왔다.
항상 스스로 할려고 하는 것은 나쁜게 아니지만,
엄청나게 많은 문제를 풀기 위해서는 조금 다르게 생각해야 할 것 같다
결과론적으로 생각해봤을 때 알고리즘을 잘하는 방법은 많이 풀어보는 수 밖에 없기 때문에
오랫동안 생각했다면 풀 수 있었더라도, 문제를 풀지 못해 스스로에게 실망하더라도
좌절한 시간조차도 노력으로 나중의 나에게 돌려주면 된다고 생각한다.