[Coding Test] Coding Tips 4 : algorithm library

삼성B형을 위한 코딩 팁 시리즈

Python 개발자의 PRO 취득을 위한 C++ 공부 여정

• [Coding Test] Coding Tips 1 : ABS(x) macro used in DFS
• [Coding Test] Coding Tips 2 : Priority Queue, Bit Operator
• [Coding Test] Coding Tips 3 : Iterator
• [Coding Test] Coding Tips 4 : algorithm library
• [Coding Test] Coding Tips 5 : 잡-Skill
• [Coding Test] Coding Tips 6 : vector, deque, list
• [Coding Test] Coding Tips 7 : hash

Algorithm Library

• 주로 컨테이너 반복자(배열 주소 값)로 다양한 작업을 수행하도록 도와준다
• 반복자 없이 값으로만 수행되는 함수도 있음
• function 을 인자로 설정해주기도 함
• range 는 항상 [first, last) 이다. 즉, last 미포함.

함수의 형태는 대부분 아래와 같다.

• func(iterator first, iterator last, T value) : find, count, lower_bound, upper_bound
• func(iterator first, iterator last) : sort, max_element, min_element
• func(iterator first, iterator last, function f) : for-each, find_if, count_if, sort
• func(T a, T b) : swap, max, min
• func({initializer list}) : max, min

이 때, 전달되는 function f 를 설정하는 방법은 다음과 같다.

• naive function

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

• function object

  struct Compare {
    bool operator()(const int a, const int b) const {
        return abs(a) < abs(b);
    }
  } comp;
  

• lambda

  auto comp = [](int a, int b){return abs(a) < abs(b); }
  

sort()

• [first, last) 구간에서 우선순위 기준으로 정렬
• sort(container begin, container last)
• sort(container, begin, container last, container compare)

partial_sort()

• [first, last) 구간에서 우선순위 기준으로 [first, middle) 만 정렬
• heap sort 기반
• default 값과 compare 설정은 sort 와 동일
• O((last - first) log (middle - first))
• 데이터 정렬은 그대로 수행하되, 우선순위가 높은 몇 가지만 추려낼 때 가장 많이 사용되는 함수
• 예를 들어, 100,000 개 중 3 개를 높은 순서로 구하는 속도는 100,000 * log3 이며, 이는 사실상 상수 시간으로 볼 수 있다

nth_element()

• [first, last) 구간에서 comp 기준으로 nth 위치 값을 선택해 왼쪽, 오른쪽에 comp 기준에 맞게 값들을 배치
• 기준으로 보면 nth 위치 값의 왼쪽에는 nth 보다 작거나 같은 값, 오른쪽에는 nth 보다 크거나 같은 값이 들어간다. 그 값들은 정렬되어 있지 않다 → Quick Sort 에서 왼쪽, 오른쪽으로 모으는 방식
• IntroSelect 기반으로 average O(n), worst O(n^2)

결론

• Middle 값이 작으면 작을 수록 partial_sort() 가 nth_element() 보다 더 빠르다
• 그치만, insertion sort 날코딩이 가장 빠름

find()

• [first, last) 구간에서 값이 value 인 첫 번째 element 의 iterator 반환
• auto it = find(arr.begin(), arr.end(), 1);

find_if()

• [first, last) 구간에서 f 의 결과가 true 인 첫 번째 element 의 iterator 반환
• lambda 를 알면 더 편하게 사용할 수 있음
• auto it = find_if(arr.begin(), arr.end(), [](auto x) { return x < 10; })