[2022 겨울학기] 2주차 - 벡터, 페어, 정렬, 에라토스테네스의 체

1. 정의

-벡터란?

요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경할 수 있는 시퀀스 컨테이너

 

-페어란?

어떤 자료형을 쌍으로 묶어서 한 쌍으로 표현

 

-정렬이란?

데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 것

 

-에라토스테네스의 체란?

소수판별법: 입력 받은 숫자보다 작은 모든 숫자로 나누어본다

                  입력 받은 숫자의 제곱근(루트 씌우기)보다 작은 모든 숫자로 나누어본다

                  에라토스테네스의 체

 

---

 

2. 동작 원리

-일차원 벡터

vector <자료형> 객체이름(초기크기);

push_back( ): 현재 벡터의 마지막 위치에 새로운 원소 삽입, 백터의 크기 1 증가

pop_back( ): 벡터의 마지막 원소 제거, 벡터가 비어있을 경우 오류 발생

size( ): 벡터의 원소 개수(벡터의 크기) 반환

empty( ): 벡터에 원소가 존재하지 않으면 true, 존재하면 false

clear( ): 벡터의 모든 요소 제거, 할당된 메모리는 그대로

begin( ): 벡터의 첫 번째 원소

end( ): 벡터의 마지막 원소의 다음을 가리킴(마지막 원소보다 한 칸 뒤)

 

-이차원 벡터

벡터의 요소로 또 다른 벡터를 가지는 벡터(각 행에 일차원 벡터가 삽입되는 벡터)

vector< vector<자료형>> 벡터이름; -> 행이 모두 비어있는 빈 벡터 생성, 각 행에 저장된 자료형에 대해 명시

                                                     행과 열 모두 가변

vector< 자료형 > 벡터이름[행의 길이]; -> 명시된 행의 길이만큼 각 행에 빈 벡터 생성, 행은 고정 열은 가변

                                                       각 행에 저장된 자료형에 대해 명시    

초기화: vector< vector<자료형>> 벡터이름( 전체 벡터의 크기, vector<자료형> (크기, 값));

전체 벡터에 대한 정보(행에 대한 정보): 벡터이름.멤버함수( )

각 행 벡터에 대한 정보(열에 대한 정보): 벡터이름[행의 위치].멤버함수( )

벡터이름[row].push_back( ): 지정된 행 벡터에 삽입할 값

벡터이름[row].pop_back( ): 지정된 행 벡터의 마지막 요소 삭제, 빈 벡터인지 확인 필수

벡터이름[row].size( ): 지정된 행 벡터의 원소 개수(벡터의 크기) 반환

벡터이름[row].empty( ): 지정된 행 벡터에 원소가 존재하지 않으면 true, 존재하면 false

 

 

-페어

pair<자료형, 자료형> 변수이름;

first: 첫 번째 원소, second: 두 번째 원소

 

-정렬

sort(시작 범위, 끝 범위, compare);   -> 시작 범위 <= scope < 끝범위

compare: 각 원소를 비교하기 위한 compare함수

배열: sort(arr, arr+n)

벡터: sort(v.begin( ), v.end( ))

 

-에라토스테네스의 체

2부터 n까지 모든 수를 나열한다

2는 소수임을 확인하고, 2의 배수를 n까지 모두 지운다

지워지지 않는 수는 소수임을 확인하고, 그 소수의 배수를 모두 지우는 과정을 반복한다

n의 제곱근까지 과정을 반복한 후에 남은 수는 모두 소수가 된다

 

---

 

3. 코드

//오름차순(sort는 기본적으로 오름차순으로 실행됨)
bool compare(int a, int b) {
	return a < b;
}

//내림차순
bool compare(int a, int b) {
	return a > b;
}

sort(arr, arr + n, compare);
sort(v.begin(), v.end(), compare);

//에라토스테네스의 체

int visited[1005] = { 1, 1 };

for (int i = 2; i < sqrt(1000); i++) {
	if (visited[i]) continue;
	for (int j = i + i; j <= 1000; j += i) {
		if (visited[j]) continue;
		visited[j] = true;
	}
}

for (int i = 2; i <= 1000; i++) {
	if (!visited[i])
		printf("%d ", i);
}

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!