BAEKJOON#9020 골드바흐의 추측

골드바흐의 추측

C++ since 2020.12.12

어제부터 C++를 공부하기 시작했다.

쉬운 문제들부터 25문제 정도를 풀어봤는데, python을 하다가 c++로 푸니까 굉장히 답답하다. 당연한 부분이지만. C++도 꾸준히 풀어나가서 익숙해져야겠다. Python이 느리다는 문제 때문에 답답했다면, C++은 파이썬에서는 당연하게 여겨지는 부분을 따로 처리해 주어야 한다는 것이 답답하다.

예를 들어서 2^100을 하는 상황에서 Python은 별도의 처리 없이 계산해 주면 되지만, C++에서는 unsigned long long으로도 범위를 커버하지 못해 문자열로 바꿔준 다음에 몇 가지 처리를 추가적으로 해줘야 했다.

이제 2일차니까 5개월 후에는 지금 내가 파이썬을 푸는 정도로 편하게 풀 수 있게 만들어야겠다.

문제분석

에라토스 테네스의 채를 활용해서 소수를 구했다.

Crepe

회색으로 남아있는 숫자가 소수이다.

2-20사이의 숫자들 중 소수를 구해보자.

2부터 오름차순으로 숫자를 방문한다. 방문한 숫자가 소수일 때, 해당 숫자의 배수들은 소수가 아님으로 색을 칠해서 소수가 아니라고 표시한다. 방문한 숫자가 소수가 아닐 때는 해당 숫자의 배수들은 이미 모두 소수가 아니라고 표시되어 있는 상태이다. c=a*b(a는 소수) 를 만족하는 숫자 c를 가정해보자. a를 방문했을 때, c는 소수가 아니라고 표시되게 된다. 이후 c차례가 되어 c를 방문하면, c의 배수들은 이미 a에 의해 모두 소수가 아니라고 표시되어 있는 상태이다. 따라서, 방문한 숫자가 소수가 아닐 때는 추가로 해당 숫자의 배수들을 찾아서 소수가 아니라고 표시해 줄 필요가 없다.

2를 방문했을 때, 2를 제외한 짝수들이 모두 걸러진다. 3을 방문하면, 6, 9, 12, 15, 18이 걸러진다. 4를 방문해보자. 4는 색이 칠해져 있음으로, 소수가 아니다. 그냥 지나치자. 이렇게 쭉 탐색해 나가면 결국 소수들만 회색으로 남게 된다.

C++ - vector

vector는 STL에서 제공하는 컨테이너이다. 배열과 다르게 동적으로 원소를 추가할 수 있다는 특징을 가지고 있다.

vector.front() - 첫 번째 원소

vector.back() - 마지막 원소

vector.begin() - 첫 번째 위치

vector.end() - 마지막 다음 위치

vector.size() - 원소 갯수

vector.push_back() - vector의 끝에 원소를 추가

vector.insert(3,4) - index 3에 4를 추가

vector.pop_back() - 마지막 원소 제거

vector.erase(vec.begin()+2); - index 2번째 값 제거

vector.erase(vector.begin(), vector.begin()+2); - index 0 - 2 번째 값 제거

이 문제를 풀면서 vector 내의 원소들 중 최댓값을 찾아야 했다.

최댓값을 구하는 코드는 아래와 같다.

//추가 - #include<algorithm>
int max = *max_element(vector.begin(), vector.end());

max_element에 vector 원소들의 첫 번째 위치와 마지막 위치를 인자로 넘겨준다. max_element는 이 구간 사이에서 최댓값을 찾아 그 원소를 return 하는 것이 아니라, 원소의 주소를 return 해준다. 포인터 앞에 *를 붙여 원소를 찾아내고, 이를 변수에 저장시켜 주었다.

max_element는 주소를 return 해주기 때문에. erase() 등 위의 함수들에서 편리하게 사용할 수 있다. **원소를 return 하면, 다시 그 원소의 위치를 찾아야 하는 반면, 주소를 return 하면, 해당 주소로 바로 찾아갈 수 있다.

CODE

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector <int>num;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		num.push_back(a);
	}
    //주어진 숫자들 중 가장 큰 값 까지만 탐색
	int max = *max_element(num.begin(), num.end());
	int arr[10001];
	for (int i = 0; i < 10001; i++) {
		arr[i] = 1;
	}

	for (int i = 2; i < max;i++) {
		if (arr[i]) {
			for (int j = i * 2; j < max+1; j+=i) {
				arr[j] = 0;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0 ; j <= num[i]/2; j++) {
			if (arr[num[i]/2-j] & arr[num[i] / 2 + j]) {
				cout << num[i] / 2 - j <<" "<< num[i] / 2 + j <<"\n";
				break;
			}
		}
	}
}

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]