[C++] Algorithm header에 대하여

Algorithm header에는?

- 코딩테스트를 준비하다보면, 필수적으로 정렬/순열 등을 사용해야 할 때가 있다.
- 이 때, <algorithm> header에 있는 함수 한 두개를 사용함으로써 위 요소들을 구현할 수 있다.
- C++ code에서 Algorithm header를 사용하기 위해서는 <algorithm> header를 include 해주면 된다.
- 코딩테스트 내에서는, 주로 vector container와 함께 사용되는 경우가 많다.

---

Algorithm header에 속한 함수들

* 대수 비교(min, max)

  - 두 수 중 큰 값(작은 값)을 return 해준다.

#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
  int i_A = 10;
  int i_B = 5;

  printf("max: %d\n", max(i_A, i_B)); // 10
  printf("min: %d\n", min(i_A, i_B)); // 5

  double d_A = 10.5;
  double d_B = 5.75;

  printf("max: %lf\n", max(d_A, d_B)); // 10.5
  printf("min: %lf\n", min(d_A, d_B)); // 5.75

  return 0;
}

 

 

* 정렬(sort)

- 기본(default)으로는 수들을 작은 것부터 큰 것으로 정렬하는 오름차순 정렬을 수행한다.
- 내림차순 정렬을 수행하기 위해서는 <functional>의 greater<int>()를 사용해야 한다.
- vector를 정렬하고 싶을 땐, sort 함수의 인자로 container의 시작과 끝 iterator 값을 넣어준다.
- Return value는 none이다.

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

int main(){
  // 오름차순 정렬
  vector<int> v1{7, 5, 4, 1, 3, 2, 6};
  sort(v1.begin(), v1.end()); // v1 = {1, 2, 3, 4, 5, 6, 7}

  for(int i=0; i<v1.size(); i++){
    printf("%d ", v1[i]);
  }
  printf("\n");

  // 내림차순 정렬
  vector<int> v2{7, 5, 4, 1, 3, 2, 6};
  sort(v2.begin(), v2.end(), greater<int>());

  for (int i = 0; i < v2.size(); i++) {
	  printf("%d ", v2[i]); // v2 = {7, 6, 5, 4, 3, 2, 1}
  }
  printf("\n");

  return 0;
}

 

 

* 순열(next_permutation, prev_permutation)

- next_permutation은 현재 vector(또는 array)로 표현된 순열의 다음 순열을 구해준다. (O(n))
- prev_permutation은 현재 vector(또는 array)로 표현된 순열의 이전 순열을 구해준다. (O(n))
- 위 함수들의 인자로 container의 시작과 끝 iterator 값이나 array의 주소값들을 넣어준다.
- 다음(이전) 순열이 있다면 true를, 없다면 false를 반환한다.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  // next_permutation
  vector<int> v1 = {1, 2, 3, 4};

  do {
    for(int i=0; i<4; i++)
	  printf("%d ", v1[i]);
	printf("\n");
	/*
	  1 2 3 4
	  1 2 4 3
	  1 3 2 4
	  ...
	  4 2 3 1
	  4 3 1 2
	  4 3 2 1
	*/
  } while(next_permutation(v1.begin(), v1.end()));

  // prev_permutation
  vector<int> v2 = { 4, 3, 2, 1 };

  do {
	  for (int i = 0; i < 4; i++)
		  printf("%d ", v2[i]);
	  printf("\n");
	  /*
		4 3 2 1
		4 3 1 2
		4 2 3 1
		...
		1 3 2 4
		1 2 4 3
		1 2 3 4
	  */
  } while (prev_permutation(v2.begin(), v2.end()));

  return 0;
}

 

 

* 이분 탐색(binary_search)

- bool binary_search(ForwardIterator first, ForwardIterator last, const T& val);
- 위 함수들의 인자로 (1) container의 시작과 끝 iterator 값이나 (2) array의 주소값들을 넣어준다.
- 컨테이너(배열에) 찾고자 하는 값 val이 있다면 true를, 없다면 false를 반환한다.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  vector<int> v = {10, 11, 12, 13, 14, 15, 16};
  int arr[7] = {20, 21, 22, 23, 24, 25, 26};

  int find_v = 14;
  int find_a = 21;

  if(binary_search(v.begin(), v.end(), find_v))
    printf("the value %d is found in vector v!\n", find_v);
  else
    printf("the value %d is not found in vector v!\n", find_v);

  if (binary_search(arr, arr+7, find_a))
	  printf("the value %d is found in array arr!\n", find_a);
  else
	  printf("the value %d is not found in array arr!\n", find_a);

  return 0;
}