알고리즘

비수정 시퀀스 연산 (Non-modifying Sequence Operations) 읽기와 탐색이 중심인 연산입니다. 다만 std::for_each에 전달한 함수가 변경 가능한 참조를 받는다면 요소를 바꿀 수 있으므로, 호출 가능 객체의 부수 효과도 함께 확인해야 합니다.

• std::for_each: 범위 내의 모든 요소에 대해 지정된 함수를 적용합니다.
• std::find: 특정 값을 검색하여 해당 값을 가리키는 반복자를 반환합니다. 찾지 못하면 end()를 반환합니다.
• std::count: 범위 내에서 특정 값과 일치하는 요소의 개수를 셉니다.
• std::count_if: 특정 조건(프레디케이트)을 만족하는 요소의 개수를 셉니다.

  #include <vector>
  #include <algorithm> // for_each
  #include <iostream>
  #include <iterator>  // distance
  void print(int n) {
      std::cout << n << " ";
  }
  int main() {
      std::vector<int> v = {10, 20, 30, 40, 50};
      std::cout << "std::for_each: ";
  
      // std::for_each 사용 예시
      std::for_each(v.begin(), v.end(), print); // 각 요소에 대해 print 함수 호출
      std::cout << std::endl; // 출력: 10 20 30 40 50
  
      // 람다 함수 사용 (C++11 이상)
      std::cout << "std::for_each with lambda: ";
      std::for_each(v.begin(), v.end(), [](int n){
          std::cout << n * 2 << " "; // 각 요소를 두 배로 만들어서 출력
      });
      std::cout << std::endl; // 출력: 20 40 60 80 100
  
      // std::find 사용 예시
      auto it_find = std::find(v.begin(), v.end(), 30);
      if (it_find != v.end()) {
          std::cout << "Found 30 at position: " << std::distance(v.begin(), it_find) << std::endl;
      } else {
          std::cout << "30 not found.\n";
      } // 출력: Found 30 at position: 2
  
      // std::count 사용 예시
      std::vector<int> v2 = {1, 2, 2, 3, 2, 4};
      int count_2 = std::count(v2.begin(), v2.end(), 2);
      std::cout << "Count of 2s: " << count_2 << std::endl; // 출력: 3
  
      // std::count_if 사용 예시
      int count_even = std::count_if(v2.begin(), v2.end(), [](int n){ return n % 2 == 0; });
      std::cout << "Count of even numbers: " << count_even << std::endl; // 출력: 4
  }

수정 시퀀스 연산 (Modifying Sequence Operations) 컨테이너의 내용을 변경하는 작업을 수행합니다.

• std::sort: 컨테이너의 요소들을 정렬합니다. 임의 접근 반복자를 지원하는 컨테이너에만 적용됩니다. (예: vector, deque, 배열)

  #include <vector>
  #include <algorithm> // sort
  #include <functional> // greater
  #include <iostream>
  #include <list> // list 예시
  int main() {
      std::vector<int> v = {5, 2, 8, 1, 9};
      std::sort(v.begin(), v.end()); // 오름차순 정렬
      std::cout << "std::sort (vector): ";
      for (int n : v) std::cout << n << " "; // 출력: 1 2 5 8 9
      std::cout << std::endl;
      // 같은 비교식을 정렬과 이진 탐색에 사용
      const auto descending = std::greater<int>{};
      std::sort(v.begin(), v.end(), descending);
      std::cout << "std::sort (desc): ";
      for (int n : v) std::cout << n << " "; // 출력: 9 8 5 2 1
      std::cout << std::endl;
      bool has_8 = std::binary_search(v.begin(), v.end(), 8, descending);
      std::cout << "contains 8: " << has_8 << std::endl; // 출력: 1
      // std::list는 sort() 멤버 함수를 제공 (양방향 반복자는 std::sort 사용 불가)
      std::list<int> l = {5, 2, 8, 1, 9};
      l.sort(); // list의 멤버 함수 sort 호출
      std::cout << "std::list::sort(): ";
      for (int n : l) std::cout << n << " "; // 출력: 1 2 5 8 9
      std::cout << std::endl;
  }

  원 vector를 오름차순으로 정렬하면 1·2·5·8·9이고, 내림차순으로 다시 정렬하면 9·8·5·2·1입니다. 이진 탐색에도 descending을 넘기는 이유는 탐색이 같은 비교 관계로 앞뒤 영역을 나눠야 하기 때문입니다. 오름차순 기본 비교로 바꿔도 같은 결과가 보장된다고 생각하면 안 됩니다.

  std::sort에 전달하는 비교 함수는 엄격 약순서(strict weak ordering)를 만들어야 합니다. std::binary_search는 각 요소 e에 대해 comp(e, value)와 !comp(value, e) 두 표현으로 범위가 각각 분할되어 있어야 합니다. 고전 std::binary_search 비교 함수 오버로드에서는 두 방향의 비교가 모두 가능해야 하고, comp(e, value)가 참인데 comp(value, e)도 참인 모순을 만들면 안 됩니다. 보통 같은 비교식으로 먼저 정렬해 이 전제를 보장합니다. 반환값은 존재 여부를 나타내는 bool뿐이므로 위치가 필요하면 같은 순서 관계로 std::lower_bound를 사용합니다.

• std::copy: 한 범위의 요소를 다른 위치로 복사합니다.

  #include <vector>
  #include <algorithm> // copy
  #include <iostream>
  int main() {
      std::vector<int> source = {1, 2, 3, 4, 5};
      std::vector<int> destination(source.size()); // 복사할 크기만큼 미리 할당
      std::copy(source.begin(), source.end(), destination.begin());
      std::cout << "std::copy: ";
      for (int n : destination) std::cout << n << " "; // 출력: 1 2 3 4 5
      std::cout << std::endl;
  }

• std::transform: 한 범위의 요소를 변환하여 다른 위치(또는 동일한 위치)에 저장합니다.

  #include <vector>
  #include <algorithm> // transform
  #include <iostream>
  int main() {
      std::vector<int> original = {1, 2, 3, 4, 5};
      std::vector<int> squared(original.size());
      std::transform(original.begin(), original.end(), squared.begin(), [](int n){
          return n * n;
      });
      std::cout << "std::transform (squared): ";
      for (int n : squared) std::cout << n << " "; // 출력: 1 4 9 16 25
      std::cout << std::endl;
  }

• std::remove: 일치하지 않는 요소를 범위 앞쪽으로 이동하고 새 논리 끝을 반환합니다. 컨테이너 크기는 바뀌지 않으며, 새 논리 끝부터 기존 end()까지의 값은 유효하지만 지정되지 않은 상태입니다. 실제 크기를 줄이려면 erase와 함께 사용합니다.

  #include <vector>
  #include <algorithm> // remove
  #include <iostream>
  int main() {
      std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
  
      auto new_end = std::remove(v.begin(), v.end(), 2);
      // [v.begin(), new_end)는 {1, 3, 4, 5}
      // [new_end, v.end())의 값은 유효하지만 지정되지 않음
  
      v.erase(new_end, v.end()); // 컨테이너의 실제 크기를 줄임
      std::cout << "std::remove + erase: ";
      for (int n : v) std::cout << n << " "; // 출력: 1 3 4 5
      std::cout << std::endl;
  }

• std::min_element, std::max_element: 범위 내에서 최소/최대 요소를 가리키는 반복자를 반환합니다.

  #include <vector>
  #include <algorithm> // min_element, max_element
  #include <iostream>
  int main() {
      std::vector<int> v = {10, 20, 5, 30, 15};
      auto min_it = std::min_element(v.begin(), v.end());
      auto max_it = std::max_element(v.begin(), v.end());
      if (min_it != v.end() && max_it != v.end()) {
          std::cout << "Min element: " << *min_it << std::endl; // 출력: 5
          std::cout << "Max element: " << *max_it << std::endl; // 출력: 30
      }
  }

  빈 범위에서 std::min_element와 std::max_element는 last를 반환하므로, 반환 반복자를 역참조하기 전에 경계와 비교해야 합니다.

• std::accumulate: 범위 내의 요소들을 합산합니다.

  #include <vector>
  #include <numeric>   // accumulate
  #include <iostream>
  #include <string>
  int main() {
      std::vector<int> v = {1, 2, 3, 4, 5};
      int sum = std::accumulate(v.begin(), v.end(), 0); // 초기값 0
      std::cout << "Sum: " << sum << std::endl; // 출력: 15
      // 문자열 연결도 가능
      std::vector<std::string> words = {"Hello", " ", "World", "!"};
      std::string concat = std::accumulate(words.begin(), words.end(), std::string(""));
      std::cout << "Concatenated string: " << concat << std::endl; // 출력: Hello World!
  }

  std::accumulate의 누산기와 반환 타입은 초깃값의 타입으로 정해집니다. 예를 들어 double 요소를 실수로 누적하려면 정수 0 대신 0.0 같은 초깃값을 사용합니다. 반환값을 마지막에 double 변수에 담는 것만으로 중간 int 누적이 실수 누적으로 바뀌지는 않습니다.