----------------
title : C++ 레퍼런스 - algorithm 라이브러리
cat_title : <algorithm>
ref_title : algorithm, <algorithm>
path : /C++ Reference/algorithm
publish_date : 2019-01-16
----------------

##@ cpp-ref-start

#@ <algorithm>

C++ 표준 라이브러리의 `<algorithm>` 라이브러리에는 원소들에 대해 작업할 수 있는 여러가지 함수(검색, 정렬, 원소들 수정하기, 개수 세기 등등) 들을 정의하고 있습니다.

이 때 작업할 원소들은 반복자 혹은 포인터를 통해 가리킬 수 있으며, 아래 함수들의 경우 작업을 시작할 원소와, 작업을 끝낼 원소 **바로 뒤**를 인자로 받게 됩니다. 식으로 표현하자면 `[first, last)` 의 형태로 보시면 됩니다.

### 원소를 수정하지 않는 작업들

* `all_of` : 범위 안에 모든 원소들이 조건을 만족하는지 확인한다.
* `any_of` : 범위 안의 원소들 중 조건을 만족하는 원소가 있는지 확인한다.
* `none_of` : 범위 안에 모든 원소들이 조건을 만족하지 않는지 확인한다.
* `for_each` : 범위 안에 원소들 각각에 대해 전달된 함수를 호출한다.
* `find$algorithm` : 범위 안에 원소들 중 **값**이 일치하는 원소를 찾는다.
* `find_if` : 범위 안에 원소들 중 **조건**과 일치하는 원소를 찾는다.
* `find_if_not` : 범위 안에 원소들 중 조건과 일치하지 않는 원소를 찾는다.
* `find_end` : 어떤 원소들의 나열이 마지막으로 나타나는 위치를 찾는다.
* `find_first_of$algorithm` : 어떤 원소들 중 첫번째로 다른 범위에서 나타나는 원소를 찾는다.
* `adjacent_find` : 최초로 연속되서 나타나는 같은 원소를 찾는다.
* `count` : 특정 값과 일치하는 원소의 개수를 센다.
* `count_if` : 특정 조건을 만족하는 원소의 개수를 센다.
* `mismatch` : 두 원소의 나열들 중 첫번째로 일치하지 않는 위치를 찾는다.
* `equal` : 두 원소의 나열들이 일치하는지 확인한다.
* `search` : 어떤 원소들의 나열을 검색한다.
* `search_n` : 어떤 원소들의 n 번 반복된 나열을 검색한다.

#### 순열 관련

순열(permutation) 이란 원소들을 어떤 순서로 나열한 것을 의미합니다.

예를 들어서 `{1,2,3,4}` 라는 원소들의 순열은 `1,2,3,4` 가 될 수 도 있고 `2,3,1,4` 가 될 수도 있고 `4,3,2,1` 이 될 수도 있겠지요.

* `is_permutation` : 어떤 원소의 나열이 다른 원소의 나열의 순열임을 확인한다.
* `next_permutation` : 특정 원소들의 다음 순열을 얻는다.
* `prev_permutation` : 특정 원소들의 이전 순열을 얻는다.

### 원소를 수정하는 작업들

* `copy` : 원소들을 복사한다.
* `copy_n` : 원소들을 n 번 복사한다.
* `copy_if` : 특정 조건에 만족하는 원소들을 복사한다.
* `copy_backward` : 원소들을 뒤에서 부터 복사한다.
* `move` : 원소들을 이동시킨다.
* `move_backward` : 원소들을 뒤에서 부터 이동시킨다.
* `swap` : 두 원소를 서로 교환한다.
* `swap_ranges` : 두 원소들의 나열을 교환한다.
* `iter_swap` : 두 반복자가 가리키고 있는 원소들을 교환한다.
* `transform` : 특정 범위의 원소들을 변환한다.
* `replace$algorithm` : 특정 범위의 원소들을 치환한다.
* `replace_if` : 특정 범위의 원소들을 조건이 맞을 시에 치환한다.
* `replace_copy` : 특정 범위의 원소들을 (다른데) 복사한 후 치환한다.
* `replace_copy_if` : 특정 범위의 원소들을 조건이 맞을 시에 복사한 후 치환한다.
* `fill` : 특정 범위를 어떤 값으로 채운다.
* `fill_n` : 특정 범위의 n 개의 원소를 값으로 채운다.
* `generate` : 특정 범위를 어떤 함수를 계속 호출해서 채운다.
* `generate_n` : 특정 범위의 n 개 원소를 어떤 함수를 계속 호출해서 채운다.
* `remove` : 특정 값들을 모두 지운다.
* `remove_if` : 특정 조건을 만족하는 원소들을 모두 지운다.
* `remove_copy` : 특정 값들을 복사한 후 지운다.
* `remove_copy_if` : 특정 조건에 만족하는 원소들을 복사한 후 지운다.
* `unique` : 연속적으로 다른 원소들이 나타나도록 같은 원소들을 제거한다.
* `unique_copy` : 연속적으로 다른 원소들이 나타나도록 같은 원소들을 제거하며, 제거된 원소들을 복사한다.
* `reverse` : 특정 범위의 원소들의 순서를 거꾸로 한다.
* `reverse_copy` : 특정 범위의 원소들의 순서를 거꾸로 해서 복사한다.
* `rotate` : 왼쪽으로 원소들을 회전시킨다 (첫번째 원소를 제외한 나머지 원소들을 왼쪽으로 쉬프트 한 후, 맨 왼쪽에 있었던 원소는 맨 뒤로 감)
* `rotate_copy` : 왼쪽으로 원소들을 회전시켜서 복사한다.
* `random_shuffle` : 무작위로 원소들을 섞는다. (C++17 에서 사용 금지됨; 아래 shuffle 사용 할 것!)
* `shuffle` : `generator` 을 이용해서 원소들을 섞는다.

#### 파티션 관련

파티션(partition)이란, 특정 조건을 만족하는 원소들은 앞으로 보내고 나머지들은 뒤로 보내는 작업을 말합니다.

* `is_partitioned` : 특정 범위의 원소들이 파티션 되어 있는지 확인한다.
* `partition` : 특정 범위의 원소들을 파티션한다.
* `stable_partition` : 특정 범위의 원소들를 파티션한다. 이 때 원소들의 상대적 순서는 바꾸지 않는다.
* `partition_copy` : 특정 범위의 원소들을 파티션 한 것을 다른 곳에 복사한다.
* `partition_point` : 파티션 된 원소들을 확인해서, 첫번째 파티션이 끝나는 점을 찾는다.

#### 정렬 관련

* `sort` : 특정 범위의 원소들을 정렬한다.
* `stable_sort` : 특정 범위의 원소들을 안정 정렬(stable sort) 한다. 참고로 안정 정렬 이란, 크기가 같은 원소들의 상대적 순서를 바꾸지 않는 정렬을 말합니다.
* `partial_sort` : 일부 원소들만 정렬한다.
* `partial_sort_copy` : 일부 원소만 정렬 한 것을 다른 곳에 복사한다.
* `is_sorted` : 어떤 원소들이 정렬되어 있는지 확인한다.
* `is_sorted_until` : 첫번째로 순서에서 어긋난 원소를 찾는다.
* `nth_element` : n 번째 원소를 찾는다.

#### 이진 탐색 관련

아래 함수들은 **정렬된 원소들**에 대해서 정확하게 작동합니다.

* `lower_bound` : 특정 값보다 작지 않는 첫 번째 원소를 찾습니다. (하한)
* `upper_bound` : 특정 값보다 큰 첫 번째 원소를 찾습니다. (상한)
* `equal_range` : 특정 원소와 일치하는 원소들의 범위를 찾습니다.
* `binary_search` : 특정 값과 일치하는 원소를 찾습니다.

#### 병합 (merge) 관련

아래 함수들 역시 **정렬된 원소들**에 대해서 정확하게 작동합니다.

* `merge` : 두 개의 정렬된 원소들의 나열을 하나로 합칩니다 (정렬된 상태가 유지되도록)
* `inplace_merge` : 두 개의 정렬된 원소들의 나열을 하나로 합치되 메모리를 추가적으로 사용하지 않습니다.

#### 셋(set) 관련

아래 함수들 역시 **정렬된 원소들**에 대해서 정확하게 작동합니다.

* `includes` : 특정 정렬된 원소들이 다른 정렬된 원소들을 포함하는지 확인한다.
* `set_union` : 두 정렬된 원소들의 합집합을 구한다. ($$A\cup B$$)
* `set_intersection` : 두 정렬된 원소들의 교집합을 구한다. ($$A\cap B$$)
* `set_difference` : 두 정렬된 원소들의 차집합을 구한다. ($$A-B$$)
* `set_symmetric_difference` : 두 정렬된 원소들의 차이를 구한다 ($$(A-B)\cup (B-A)$$)

### 힙(Heap) 관련

* `push_heap` : 힙에 원소를 삽입한다.
* `pop_heap` : 힙에서 원소를 제거한다.
* `make_heap` : 특정 원소들을 힙으로 만든다.
* `sort_heap` : 힙의 원소들을 정렬한다.
* `is_heap` : 특정 범위의 원소들이 힙인지 확인한다.
* `is_heap_until` : 힙 조건을 만족하지 않는 첫 번째 원소를 찾는다.

### 최대/최소 관련

* `min` : 최소 원소를 찾는다.
* `max` : 최대 원소를 찾는다.
* `minmax` : 최소 및 최대 원소를 찾는다.
* `min_element` : 최소 원소를 찾는다. (이 때 해당 원소를 가리키는 반복자를 리턴함)
* `max_element` : 최대 원소를 찾는다. (이 때 해당 원소를 가리키는 반복자를 리턴함)
* `minmax_element` : 최소 및 최대 원소를 찾는다. (이 때 해당 원소를 가리키는 반복자를 리턴함)

### 기타

* `lexicographical_compare` : 사전적 크기 비교를 수행한다.