C++ STL - algorithm

1 minute read

ํ—ค๋”ํŒŒ์ผ algorithm์— ์†ํ•œ ํ•จ์ˆ˜ ์ •๋ฆฌ

sort ํ•จ์ˆ˜

  • ์ •๋ ฌ ํ•จ์ˆ˜
#include <algorithm>
#include <vector>

sort(์‹œ์ž‘์ฃผ์†Œ, ๋์ฃผ์†Œ, ๋น„๊ตํ•จ์ˆ˜)
// ๋์ฃผ์†Œ๋Š” ํฌํ•จํ•˜์ง€ ์•Š๋Š”๋‹ค.

// ๋‚ด๋ฆผ์ฐจ์ˆœ. ์™ผ์ชฝ์— ํฐ ์ˆ˜๊ฐ€ ์˜ค๋„๋ก ์ •๋ ฌ
bool cmp1(const int& a, const int& b){
    return a > b;
}

// ์˜ค๋ฆ„์ฐจ์ˆœ. ์™ผ์ชฝ์— ์ž‘์€ ์ˆ˜๊ฐ€ ์˜ค๋„๋ก ์ •๋ ฌ
bool cmp2(const int& a, const int& b){
    return a < b;
}

// ๋ฌธ์ž์—ด ์‚ฌ์ „์ˆœ์œผ๋กœ ์ •๋ฆฌ
bool cmp3(const string&s1, const string&s2){
  return s1 < s2;
}

vector<int> v1(10);
sort(v.begin(), v.end(), cmp1);

// ๋ฌธ์ž์—ด์˜ ๊ฒฝ์šฐ ์•„์Šคํ‚ค์ฝ”๋“œ๊ฐ’์— ๋”ฐ๋ผ ์ •๋ ฌ๋œ๋‹ค.
vector<string> v2(10);
sort(v.begin(), v.end(), cmp3);


  • ์ปจํ…Œ์ด๋„ˆ๋‚˜ ๋ฐฐ์—ด์˜ ์›์†Œ๋“ค์„ ํŠน์ • ๊ธฐ์ค€์— ๋งž์ถ”์–ด ์ •๋ ฌํ•  ๋•Œ ์‚ฌ์šฉํ•˜๋Š” ํ•จ์ˆ˜์ด๋‹ค
  • ๋น„๊ตํ•จ์ˆ˜ ์ธ์ž ์ƒ๋žต ์‹œ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.
  • ์ปจํ…Œ์ด๋„ˆ์˜ ์ž๋ฃŒํ˜•์— ๋”ฐ๋ผ ๋น„๊ตํ•จ์ˆ˜์— ์ „๋‹ฌ๋˜๋Š” ์ธ์ž์˜ ์ž๋ฃŒํ˜•๋„ ๋‹ฌ๋ผ์ ธ์•ผ ํ•œ๋‹ค.
typedef struct Point{
  int x;
  int y;
}

// x ๊ฐ’์— ๋”ฐ๋ผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค. x๊ฐ’์ด ๊ฐ™๋‹ค๋ฉด y๊ฐ’์— ๋”ฐ๋ผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.
bool cmp(const Point& p1, const Point& p2){
  if(p1.x == p2.x){
    return p1.y < p2.y
  }
  else{
    return p1.x < p2.x
  }
}
  • ๊ตฌ์กฐ์ฒด๋ฅผ ํŠน์ • ์กฐ๊ฑด์— ๋”ฐ๋ผ ์ •๋ ฌํ•˜๋Š” ๋ฐฉ๋ฒ•
  • ๋น„๊ตํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ์ง์ ‘ ์ •์˜ํ•œ๋‹ค.

์ตœ๋Œ“๊ฐ’๊ณผ ์ตœ์†Ÿ๊ฐ’ ์ฐพ๊ธฐ

  • max_element(์‹œ์ž‘์ฃผ์†Œ, ๋์ฃผ์†Œ)
  • min_element(์‹œ์ž‘์ฃผ์†Œ, ๋์ฃผ์†Œ)
  • ๋์ฃผ์†Œ๋Š” ํฌํ•จํ•˜์ง€ ์•Š๋Š”๋‹ค.
  • ์ฃผ์†Œ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋ฏ€๋กœ ๊ฐ’์„ ์ฐธ์กฐํ•˜๋ ค๋ฉด * ์—ฐ์‚ฐ์ž๋ฅผ ์ด์šฉํ•œ๋‹ค.
#include <algorithm>

vector<int> v(10);
int max = *max_element(v.begin(), v.end());
int min = *min_element(v.begin(), v.end());

binary_search ํ•จ์ˆ˜

  • ์ด์ง„ํƒ์ƒ‰ ํ•จ์ˆ˜
#include <iostream>
#include <algorithm>

binary_search(low_iter, high_iter, key)
// ํƒ์ƒ‰์— ์„ฑ๊ณตํ•˜๋ฉด (key๋ฅผ ์ฐพ์œผ๋ฉด) true ๋ฐ˜ํ™˜

if(binary_search(v.begin(), v.end(), key)){
  // doing something
}

  • ์ด์ง„ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•˜๋ ค๋ฉด ๋ฐฐ์—ด์ด ๋ฐ˜๋“œ์‹œ ์ •๋ ฌ๋˜์–ด ์žˆ์–ด์•ผํ•œ๋‹ค. (์˜ค๋ฆ„์ฐจ์ˆœ)
  • ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(log2(n))

reverse ํ•จ์ˆ˜

  • ๋ฌธ์ž์—ด์„ ๊ฑฐ๊พธ๋กœ ๋’ค์ง‘๋Š” ํ•จ์ˆ˜
#include <algorithm>

std::reverse(first_iter, last_iter);
// [first, last) ๋ฒ”์œ„๋กœ ๋งˆ์ง€๋ง‰ ์ธ๋ฑ์Šค๋Š” ํฌํ•จํ•˜์ง€ ์•Š๋Š”๋‹ค.

std::string str = "Bokyoung";
std::reverse(str.begin(), str.end());

next_permutation ํ•จ์ˆ˜

  • ์ˆœ์—ด์„ ๊ตฌํ•˜๋Š” ํ•จ์ˆ˜
  • ์ปจํ…Œ์ด๋„ˆ๊ฐ€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ๋˜์–ด ์žˆ์–ด์•ผ ํ•จ
#include <algorithm>
#include <vector>

std::next_permutation(first_iter, last_iter);
// bool ๋ฐ˜ํ™˜ํ˜•์œผ๋กœ ๋” ์ด์ƒ ์ •๋ ฌํ•  ์ˆ˜ ์žˆ๋Š” ์ˆ˜์—ด์ด ์—†์œผ๋ฉด false ๋ฐ˜ํ™˜

std::vector<int> v = {1, 3, 5 ,7, 9};

do{
  for(auto iter : v){
    std::cout << iter << " ";
  }
  std::cout << "\n";
} while(std::next_permutation(v.begin(), v.end()));

Categories:

Updated:

Leave a comment