[C++] algorithm 라이브러리

1. sort

2. make_heap

3. nth_element

4. next_permutation

5. prev_permutation

6. lower_bound, upper_bound

7. unique

 

1. sort 알고리즘

include <algorithm>

void sort(start, end);

algorithm 헤더파일에 sort알고리즘이 속해 있으며 start와 end는 iterator형으로 받는다.

예시로 다음과 같다.

#include<vector>
#include<algorithm>

vector v = {4,3,1,5,6};
sort(v.begin(), v.end());

해당 코드를 수행하면 v의 배열이 정렬화 된다.

 

sort함수는 기본적으로 오름차순 정렬이다.

만약 내림차순으로 정렬하고 싶다면 다음처럼 코드를 작성하면 된다.

#include<vector>
#include<algorithm>

std::vector<int> v = {4,3,1,5,6};
std::sort(v.begin(), v.end(), std::greater<>());

greater가 내림차순으로 정렬해주는 역할을 한다.

기본적으로 sort함수는 O(logn)의 비용이 드는 퀵 정렬을 사용한다. 해당 내용은 나중에 시간이 생긴다면..

 

그리고, sort함수를 원하는 방식으로 정렬을 하고 싶은 경우가 있을 수 있다. 그런 경우 함수를 sort의 인자로 주어 쉽게 해결할 수 있다. 위의 greater<>()와 비슷한 방식이라 생각하면 편하다.

#include <cstdio>
#include <algorithm>

bool compare(int a, int b) {
	return a < b;
}

int main(void) {
	int arr[] = { 6,4,1,2,6,2,7,9 };
	std::sort(arr, arr + 8, compare);
	for (int i = 0; i < 8; i++) printf("%d ", arr[i]);
}

다음과 같은 코드가 있다고 하자. 결과는 오름차순으로 정렬이 된다.

이 코드의 compare함수를 다음과 같이 변경한다면

bool compare(int a, int b){
	return a > b;
}

내림차순으로 정렬이 된다.

a가 배열에서 왼쪽에 있는 요소가 되고, b는 배열에서 오른쪽에 있는 요소가 된다. 이 둘을 비교하여 true가 되는 쪽이 왼쪽으로 가게 되는 것이다. 즉, a > b의 경우 a가 더 크면 true, b가 더 크면 false를 반환하게 되는데, true가 되면 a가 왼쪽, b가 오른쪽에 가게 된다.

 

2.  make_heap 

입력받는 자료구조를 힙 형태로 변환해주는 역할을 한다.

#include <algorithm>

std::vector<int> v(1,2,3,4,5,6,7,8,9);
std::make_heap(v.begin(), v.end());

v를 힙 형태로 변형해준다. 이 과정을 통해 v가 다음처럼 정렬이 되어있다고 하자.

9

7

8

4

5

3

6

2

1

이 상태에서 다음 코드를 실행해야 heap정렬이 정상적으로 작동한다.(heap 삽입를 의미한다)

v.push_back(10);
std::push_heap(v.begin(), v.end());

먼저 v에 마지막 원소에 10을 삽입해 준 뒤, push_heap을 해줘야 한다. push_heap을 통해 heapify가 일어나게 될 것이다. 여기에서  heapify의 의미를 알고 싶다면 우선순위 큐와 관련한 글을 확인하고 오는 것이 도움이 될 것이다.

https://jhcard.tistory.com/69

[C++] queue 라이브러리

다음은 힙 삭제이다.

std::pop_heap(v.begin(), v.end());

해당 문장을 실행한다면 가장 앞에 있는 원소가 v의 가장 맨 뒤 요소로 이동한다. 그러니까 힙에서 배제되는 것이다. 만약 아예 삭제하고 싶다면 다음 문장을 사용해야 한다.

std::pop_heap(v.begin(), v.end());
v.pop_back();

 

3. nth_element

n번째 까지만 정렬을 하는 함수이다.

std::vector<int> v(6,7,3,1,3,5,4);
std::nth_element(v.begin(), v.begin() + 3, v.end());

3번째 요소까지 v를 정렬하는 것이다. 

 

4. next_permutation

원소의 순열을 구해주는 함수이다.

std::vector<int> v(1, 2, 3);
std::nth_element(v.begin(), v.end());
std::next_permutation(v.begin(), v.end(), cmp);

형태를 보면 iterator의 시작과 끝을 인수로 받고, sort에서 살펴본 cmp와 동일한 역할을 하는 cmp도 인수로 넣을 수 있다.

 

return 값은 bool형태로 다음 순열이 존재한다면 컨테이너의 원소를 해당 순열 순서로 변경하고 true반환,

다음 순열이 존재하지 않다면 false를 반환한다.

 

주의할 점은 오름차순으로 순열을 생성한다.

#include <cstdio>
#include <algorithm>

int main(void) {
	int number[3] = { 1,2,3 };

	do {
		for (int i = 0; i < 3; i++) printf("%d ", number[i]);
		printf("\n");
	} while (std::next_permutation(number, number + 3));
}

결과값

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

이걸 중복조합을 구하는데에도 사용 가능한 모양이다.

#include <cstdio>
#include <algorithm>

int main(void) {
	int number[4] = { 1,2,3,4 };
	int tmp[4] = { 1, 1, 0, 0 };

		do {
			for (int i = 0; i < 4; i++) if (tmp[i]) printf("%d ", number[i]);
			printf("\n");
		} while (std::prev_permutation(tmp, tmp + 4));
}

결과값:

1 2
1 3
1 4
2 3
2 4
3 4

 

5. prev_permutation

위에서 설명한 next_permutation의 반대 개념이다. 즉, 이전 순열로 정렬해준다.

#include <cstdio>
#include <algorithm>

int main(void) {
	int number[3] = { 3, 2, 1 };

	do {
		for (int i = 0; i < 3; i++) printf("%d ", number[i]);
		printf("\n");
	} while (std::next_permutation(number, number + 3));
}

결과 값: 

3 2 1

3 1 2

2 3 1

2 1 3

1 3 2

1 2 3

이전 순열을 계속해서 바꿔주고, 더 이상 바꿔줄 수 없을때 false를 반환해준다.

 

6. lower_bound, upper_bound

이진탐색으로 찾고자 하는 값의 iterator를 반환해준다. 즉, 찾고자 하는 값을 찾기 위해서는 찾고자 하는 값이 있는 저장공간이 정렬되어 있어야 한다.

std::vector<int> v{1,3,6,4,2,5};
std::sort(v.begin(), v.end());	// v = [1, 2, 3, 4, 5, 6]
printf("%d", *(std::lower_bound(v.begin(), v.end(), 3))); -> 4의 iterator 반환
printf("%d", *(std::upper_bound(v.begin(), v.end(), 3))); -> 3의 iterator 반환

lower_bound는 찾고자 하는 값보다 크면서 가장 작은 수의 iterator를 반환해준다.

upper_bound는 찾고자 하는 값보다 크거나 같은 값 중에서 가장 작은 수의 iterator반환이다. 

작거나 같은 값의 의미가 아니다.

 

 

7. unique

연속된 값에서 중복되는 값을 삭제해준다. - 연속된 값중에서 중복을 삭제하는 것이기 때문에 사전에 정렬이 필요하다.

정확한 기능은 다음 사진을 참고하자.

이를 이용하여 v.erase(unique(v.begin(), v.end()), v.end())로 쓰레기 값들은 전부 삭제하고, 중복된 값을 제거할 수 있게 된다.

std::unique(v.begin(), v.end())를 사용하여 함수를 사용할 수 있다.