1. Sorting array (selection sort)

선택 정렬을 이용한 배열 정렬

배열을 정렬한다는건 배열의 모든 element를 특정 조건에 맞는 순서로 정렬하는걸 의미한다
ex) 연락처 이름순, 이메일 최신순

배열을 정렬하게 되면 사람뿐 아니라 컴퓨터에서도 배열 검색을 효율적으로 만들 수 있다
ex) 이름 검색 시 가나다 순으로 정렬되어 있으면 더 효율적으로 검색 가능

심지어 정렬하게 되면 배열 검색 자체를 하지 않아도 되는 상황도 많이 존재한다 (최대, 최소 찾기)

일반적으로 정렬이란 배열 element 쌍을 비교하고 기준에 충족하면 교환하는 방식으로 설계한다, 굉장히 다양한 정렬 알고리즘이 존재한다

C++ STL에는 두 element를 교환할 수 있게 해주는 std::swap()함수가 정의되어 있다

	#include <utility>  // std::swap을 사용하기 위함

    int a{ 10 };
    int b{ 20 };

    std::swap(a, b); //a에 20, b에 10이 들어가게 된다

selection sort

다양한 정렬 방법중에 이해하기 가장 쉽지만 가장 느린 정렬 중 하나인 선택 정렬이다

배열의 element를 오름차순으로 정렬한다고 가정했을때 선택 정렬은 다음과 같은 단계들을 수행한다

1. 배열 index 0에서 시작해서 전체 배열을 검색 후 가장 작은 값을 찾는다
2. 배열에서 찾은 가장 작은 값을 index 0값과 교환
3. 다음 인덱스부터 다시 시작해서 1, 2단계를 반복한다

예를들어 { 30, 20, 50, 80, 70 }이 있다고 가정하면 1번 단계를 거치면 20, 30, 50, 80, 70이 된다, 이 단계를 반복하여 수행해서 20 30 50 70 80을 만드는것이다

선택 정렬을 C++로 구현해보면 다음과 같다

	int array[]{ 30, 20, 50, 80, 70 };
    constexpr int length{ static_cast<int>(std::size(array)) };

    for (int start{ 0 }; start < length - 1; ++start) //마지막은 어차피 정렬된 상태기 때문에 -1
    {
        int smallestIndex{ start };

		for (int current{ start + 1 }; current < length; ++current)
		{
			if (array[current] < array[smallestIndex])
			{
				smallestIndex = current;
			}
		}

		std::swap(array[start], array[smallestIndex]);
    }

이러한 배열 정렬은 C++ STL에 std::sort()로 구현되어 있다 (algoritm헤더를 include해야함)

    int array[]{ 30, 20, 50, 80, 70 };

	std::sort(std::begin(array), std::end(array)); //오름차순으로 정렬한다

내부적으로 위의 직접 구현한 selection sort와 유사하게 동작하지만 실제로는 더 효율적인 알고리즘을 사용한다 (intro sort)

std::begin()과 std::end()는 각각 container의 시작, 끝 다음을 가리키는 iterator를 return한다

2. Iterator

Iterator

컨테이너를 순회하는 작업은 굉장히 자주 있는 일이다, 이제까지 for, while, for-each와 같은 loop와 포인터 연산을 사용하여 순회하는 방법을 정리했다

index를 사용하여 순회하는 것은 몇가지 단점이 존재한다, 우선 list와 같은 컨테이너들은 element에 대한 직접 접근이 불가능하기 때문에 사용이 불가능하며 단순히 element에 접근하는 용도로만 사용한다면 필요 이상의 타이핑이 생길 수 있다

또한 포인터 연산으로 컨테이너의 element 순회는 배열과 같은 컨테이너처럼 element가 연속적으로 있을때만 작동한다 (list, map과 같은 컨테이너는 그렇지 않다)

물론 포인터 연산 없이, 포인터는 일부 비순차적 구조를 순회하는데 사용할 수 있다 (linked list의 각 element는 포인터를 통해 이전 element에 연결된다 -> 따라서 포인터 체인으로 list 순회가 가능하다)

for-each는 컨테이너를 순회할 수 있다 (array, list, tree, map 등 거의 다 동작), 그렇다면 전부 각기 다른 컨테이너인데 for-each는 어떻게 전부 동작이 가능한걸까? 바로 iterator를 사용하기 때문이다

iterator는 컨테이너를 순회하도록 설계된 객체이다 (각 element에 접근을 제공한다)

컨테이너들은 다양한 종류의 iterator를 제공한다, 예를들어 배열 컨테이너는 배열을 순방향으로 탐색하는 순방향 iterator와 반대로 역방향으로 탐색하는 역방향 iterator를 제공한다

이러한 iterator 객체가 제공하는 인터페이스를 사용하여 컨테이너를 순회할 수 있다

pointer iterator

가장 간단한 종류의 iterator는 포인터이다, 앞서 정리한대로 포인터 연산을 이용하여 순회한다 (따라서 메모리에 순차적으로 저장된 데이터에 대해 작동한다)

	std::array arr{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	auto begin{ &arr[0] }; //std::array인 arr의 0번째 element를 가리키는 포인터
    
	auto end{ begin + std::size(arr) };
    auto end{ arr.data() + std::size(arr) }; //이렇게도 가능!

	for (auto ptr{ begin }; ptr != end; ++ptr) //순회
	{
		std::cout << *ptr << std::endl; //역참조로 값 가져오기
	}

여기서 중요한 점은 std::size(arr)을 이용하여 인덱싱을 하게 되면 out of bound값을 역참조 하기 때문에 정의되지 않은 동작이 발생할 수 있다

	arr[std::size(arr)]; //crash!

또한 C-style 배열과 같은경우에는 다음과 같이 사용이 가능하다 (decay)

	int arr[7];
    int* end{ arr + std::size(arr) };

STL iterator

모든 STL 컨테이너는 순회를 지원한다, 위 코드처럼 직접 begin과 end를 계산하는 방식보다 컨테이너의 begin()과 end() 멤버함수를 통해 더 편리하게 시작점과 끝점을 얻을 수 있다

	#include <iterator>

	std::array arr{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	auto begin{ arr.begin()};
	auto end{ arr.end()};

	for (auto ptr{ begin }; ptr != end; ++ptr)
	{
		std::cout << *ptr << std::endl; //역참조로 값 가져오기
	}

C-style 배열을 위한 begin()과 end()는 < iterator > 헤더에 존재하며 std::로 사용이 가능하다 (물론 STL 컨테이너에 사용도 가능함)

	int temparr[10]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	std::begin(temparr);
	std::end(temparr);

std::array외에 vector나 다른 컨테이너들도 begin과 end가 멤버함수로 정의되어 있다 (해당 컨테이너 헤더파일에 정의됨, 결국 이러한 헤더파일들은 내부적으로 < iterator >헤더를 include 하고 있음)

iterator 사용 시 operator >와 operator !=

일반적으로 for-loop에서 숫자 비교를 할 때 !=보다는 >를 권장한다, 하지만 iterator는 !=를 더 권장한다 (원하는 곳까지 도달했는지 체크하기 위해서)

	for(auto it{ begin }; it != end; ++it)

왜냐하면 일부 iterator타입은 > 비교가 불가능하기 때문이다, !=는 모든 iterator 타입에 대해 잘 작동한다

for-each 동작

begin(), end() 멤버함수를 가지고 있거나 std::begin(), std::end()에 사용할 수 있는 타입은 전부 for-each loop에서 사용할 수 있다

	std::array arr{ 1, 2, 3 };
    for(int i : arr)
    {
    }

for-each loop는 내부적으로 순회할 컨테이너 타입의 begin()과 end()를 호출한다, 따라서 위에 arr은 std::array이고 begin(), end() 멤버 함수가 존재하기 때문에 for-each loop에서 사용이 가능하다

C-style 배열도 위에서 정리했듯 std::begin, std::end 사용이 가능한 컨테이너 타입이기 때문에 for-each loop에서 사용이 가능하다

단 동적 C-style 배열이나 포인터 타입으로 decay된 C-style 배열은 for-each에서 사용이 불가능하다 (std::end 개념이 없기 때문, 타입 정보에 길이 정보가 없다)

이러한 for-each loop 이외에도 다양한 알고리즘에서 iterator를 사용한다

iterator invalidated

순회하려는 컨테이너의 element가 파괴되거나 주소가 변경되면 기존의 iterator는 dangling 상태가 될 수 있다 (포인터, 참조와 같이)

이때 iterator가 invalidated되었다고 하며 invalidated 된 iterator에 접근 시 정의되지 않은 동작 및 크래시가 발생할 수 있다

컨테이너를 수정하는 작업 ex) std::vector에 capacity가 부족하여 메모리 재할당 후 element 추가가 될 때 컨테이너의 element주소가 변경되는 현상이 있을 수 있다(vector의 모든 element가 새 메모리 위치로 복사/이동 되기 때문에), 이렇게 되면 결국 기존 iterator는 invalidated되게 되고 사용하지 않아야 한다

    std::vector<int> v{ 1, 2, 3, 4, 5, 6, 7 };

    auto it{ v.begin() }; // it는 v의 첫 번째 요소(1)를 가리킴

    ++it; // 두 번째 요소(2)로 이동
    std::cout << *it << '\n'; // 정상: 2를 출력

    // v.erase(it)는 it가 가리키는 요소(2)를 삭제
    v.erase(it);

    // erase()는 삭제된 요소 (및 그 이후 요소들)에 대한 iterator를 무효화
    // 따라서 iterator "it"는 이제 무효화됨

     ++it;             // 정의되지 않은 동작: 무효화된 이터레이터를 증가시키려고 함
     std::cout << *it << '\n'; // 정의되지 않은 동작: 무효화된 이터레이터를 역참조

여기서 erase()는 삭제된 element 바로 다음 element를 가리키는 iterator를 return한다 (이때 마지막 element가 erase()되면 end()를 return한다)

	std::vector<int> v{ 1, 2, 3, 4, 5, 6, 7 };

    auto it{ v.begin() };

    ++it;
    
    std::cout << *it << '\n'; //2

    it = v.erase(it); //3을 가리키는 iterator

    ++it;             
    std::cout << *it << '\n'; //4

3. STL algorithm

STL algorithm

컨테이너를 정렬, 카운팅, 검색 등과 같은 작업은 굉장히 자주 사용되는 작업인 만큼 STL에 이미 정의되어 있다 (프로그래머가 직접 함수를 만들어 사용하면 휴먼 에러가 발생할 가능성이 높다, 이미 검증된 STL algorithm을 사용하는걸 권장한다)

사전에 테스트되어 검증되고 효율적이며 다양한 컨테이너에서 작동한다, 또한 다수의 algorithm은 멀티 스레딩을 지원한다

대부분의 STL algorithm은 다음 세 가지 카테고리에 속하게 된다

• Inspector (검사)
  컨테이너의 데이터를 보기 위해 사용된다 (수정은 아님), 검색이나 갯수 카운팅이 있다

• Mutator (변경)
  컨테이너의 데이터를 수정하기 위해 사용된다 (정렬, 셔플링)

• Facilitator (조력)
  데이터 멤버의 값을 기반으로 결과를 생성한다 (값을 곱해주는 객체, element쌍이 어떤 순서로 결정되어야 하는지 결정하는 객체)

std::find

std::find는 컨테이너에서 특정 값의 첫 번째 발생을 검사한다, 총 3개의 매개변수를 받는다 (시작 element를 가리키는 iterator, 끝 element를 가리키는 iterator, 검색할 값)

element를 찾으면 해당 element를 가리키는 iterator를 return하고 찾지 못한다면 해당 컨테이너의 end iterator를 return한다

	std::array array1{ 1, 4, 3, 4, 5 };

	auto found{ std::find(array1.begin(), array1.end(), 4) };

	std::cout << *found << std::endl; //제일 앞에있는 4를 가리키는 iterator임

std::find_if

정확한 값 대신 특정 조건을 만족하는 값이 컨테이너에 있는지 확인하고 싶을때 사용한다

std::find와 유사하게 동작하지만 검색할 특정 값을 전달하는 대신 함수 포인터나 람다 함수 전달이 필요하다, find_if는 이렇게 전달된 함수를 호출하고 true/false를 return할 수 있다

    bool containBlue(std::string_view str)
    {
        return str.find("blue") != std::string_view::npos;
    }

    int main() 
    {
        std::array<std::string_view, 4> arr{ "red", "redorange", "blue", "bluegreen" };

        auto found{ std::find_if(arr.begin(), arr.end(), containBlue) };

        std::cout << *found << std::endl; //blue

        return 0;
}

string_view::find()로 부분 문자열을 찾지 못하면 std::strig_view::npos를 return하고 찾으면 해당 부분 문자열이 발생한 index를 return한다

containBlue에서 "blue" element가 조건을 만족하여 true를 return했기 때문에 *found 역참조 값은 blue가 된다

std::count & std::count_if

std::count와 std::count_if는 특정 element 혹은 조건을 만족하는 모든 element의 발생을 검색하여 카운팅한다

	bool containBlue(std::string_view str)
    {
        return str.find("blue") != std::string_view::npos;
    }

    int main() 
    {
        std::array<std::string_view, 4> arr{ "red", "redorange", "blue", "bluegreen" };

        auto blues{ std::count_if(arr.begin(), arr.end(), containBlue) }; //2
        auto reds{ std::count(arr.begin(), arr.end(), "red") }; //2

        std::cout << blues << std::endl;

        return 0;
    }

std::sort

이전에 std::sort를 이용하여 오름차순 정렬을 했는데, std::sort에도 함수 포인터나 람다를 넘겨서 원하는대로 정렬이 가능하다

    bool greater(int a, int b)
    {
        return a > b;
    }

    int main() 
    {
        std::array arr{ 20, 10, 30, 60, 40 };
        std::sort(arr.begin(), arr.end(), greater); //60, 50, 30, 20, 10

        return 0;
    }

greater는 분명 2개의 인자를 넘겨야 하지만 아무런 인자도 전달하지 않아도 잘 동작한다, 이는 함수 포인터로 전달하기 때문이다 (배열의 임의의 두 element를 가지고 함수를 호출한다)

이러한 내림차순은 std::greater라는 사용자 정의 타입을 C++에서 제공한다 (< functional > 헤더의 일부임)

	std::array arr{ 20, 10, 30, 60, 40 };
	std::sort(arr.begin(), arr.end(), std::greater{});

C++17 이전에는 std::greater{} 사용 시 element 타입을 반드시 명시해야 했다 (std::greater< int >{})

std::sort가 비교함수를 어떻게 사용하는지 자세히 확인해보자

	//기존의 sort구현
    void sort(int* begin, int* end) 
    {
      // end-1 까지 반복하는 이유는 마지막 요소는 비교 대상이 하나뿐이므로
      // 그 이전까지만 정렬되면 자동으로 정렬되기 때문
      for (auto startElement{ begin }; startElement != end -1; ++startElement) 
      {
          auto smallestElement{ startElement };

          // std::next는 (startElement + 1)과 같이 다음 요소를 가리키는 포인터(iterator)를 반환한다
          for (auto currentElement{ std::next(startElement) }; currentElement != end; ++currentElement) 
          {
              if (*currentElement < *smallestElement) 
              {
                  smallestElement = currentElement;
              }
          }
          std::swap(*startElement, *smallestElement);
      }
	}

    int main() 
    {
        int array[]{ 2, 1, 9, 4, 5 };

        sort(std::begin(array), std::end(array)); // 배열의 시작과 끝 이터레이터(여기서는 포인터)를 전달

        for (auto i : array) {
            std::cout << i << ' ';
        }
        std::cout << '\n';

        return 0;
    }

이제 기존의 sort()에 비교함수를 넣는 방식으로 구현해보자

비교함수를 넣기 위해서는 std::function< bool(int, int)>를 넣어주어야 한다 (추후에 설명)

	#include <functional> // std::function, std::greater를 사용하기 위함
    #include <iostream>
    #include <iterator>   // std::begin, std::end, std::next
    #include <utility>    // std::swap

    void sort(int* begin, int* end, std::function<bool(int, int)> compare) 
    {
        for (auto startElement{ begin }; startElement != end - 1; ++startElement) 
        {
            auto biggestElement{ startElement };

            for (auto currentElement{ std::next(startElement) }; currentElement != end; ++currentElement) 
            {
                // compare는 currentElement가 biggestElement보다 먼저 정렬되어야 하는지 확인
                if (compare(*currentElement, *biggestElement)) 
                {
                    biggestElement = currentElement;
                }
            }
            std::swap(*startElement, *biggestElement);
        }
    }

    int main() 
    {
        int array[]{ 2, 1, 9, 4, 5 };

        // std::greater를 사용하여 내림차순 정렬
        // 직접 만든 sort 함수와 std::sort 간의 충돌을 방지하기 위해
        // 전역 네임스페이스 선택자(::)를 사용
        ::sort(std::begin(array), std::end(array), std::greater{}); // std::greater{} 객체 전달

        for (auto i : array) 
        {
            std::cout << i << ' ';
        }
        std::cout << '\n';

        return 0;
    }

std::for_each

std::for_each는 컨테이너의 모든 element를 사용자 정의 함수에 적용한다

	void doubleNum(int& i) //원본 수정을 위한 참조타입
    {
        i *= 2;
    }

    int main() 
    {
        std::array arr{ 20, 10, 30, 60, 40 };
        std::for_each(arr.begin(), arr.end(), doubleNum); //전부 2배가 됨

        return 0;
    }

그렇다면 그냥 for_each loop을 사용하는것보다 좋은점은 뭘까?

우선 std::for_each를 사용하게 되면 의도가 명확해진다 (모든 element에 대해 특정 함수를 호출하여 적용하라)

for_each loop에는 새로운 변수를 추가해야 한다, 이는 곧 휴먼 에러로 직결될 수 있다

또한 std::for_each는 컨테이너의 시작이나 끝에 있는 element를 건너뛸 수 있다

	std::array arr{ 20, 10, 30, 60, 40 };
	std::for_each(std::next(arr.begin()), arr.end(), doubleNum); //20, 20, 60, 120, 80

C++20부터는 begin()과 end()를 사용하지 않아도 된다, for_each 뿐 아니라 begin, end가 필요한 부분에 std::ranges::를 사용하게 되면 단순하게 컨테이너만 전달해서 사용이 가능하다

	std::ranges::for_each(arr, doubleNum);

std::next()는 다음 element를 가리키는 iterator를 return한다

STL 알고리즘의 많은 알고리즘은 성능이나 실행 순서에 대한 보장을 한다 (std::for_each는 각 element에 한번씩 순차적으로 접근될 것을 보장한다)

따라서 반드시 순차적으로 접근해서 동작해야하는 상황이라면 순차적 실행 순서에대한 보장이 있는 알고리즘을 사용해야 한다
(std::for_each, std::copy, std::copy_backward, std::move, std::move_backward)

이 이외에도 다양한 순방향 iterator를 사용하는 알고리즘들은 암묵적으로 순방향이다

Quiz

개념


1. 배열 정렬(Sorting)의 정의: 배열의 모든 요소를 특정 조건(순서)에 맞춰 나열하는 것.

2. 정렬의 예시: 연락처 이름순, 이메일 최신순 등.

3. 정렬의 이점 1 (검색 효율): 사람뿐만 아니라 컴퓨터가 데이터를 검색할 때(예: 이진 탐색 등) 효율이 높아짐.

4. 정렬의 이점 2 (최적값): 최대값이나 최소값을 찾을 때 검색 절차 자체를 생략할 수 있음.

5. 일반적인 정렬 알고리즘의 매커니즘: 요소 쌍을 비교(Compare)하고 기준 충족 시 교환(Swap)하는 방식.

6. std::swap 함수: <utility> 헤더에 정의되어 있으며, 두 변수의 값을 서로 맞바꾸는 기능을 함.

7. 선택 정렬(Selection Sort)의 특징: 이해하기 가장 쉽지만, 가장 느린 알고리즘 중 하나.

8. 선택 정렬의 동작 단계: (1) 전체 검색 후 최소값 찾기 -> (2) 현재 인덱스와 교환 -> (3) 다음 인덱스로 이동하여 반복.

9. 선택 정렬 구현 시 루프 조건: 외부 루프는 length - 1까지만 수행하면 됨 (마지막 요소는 자연스럽게 정렬되므로).

10. std::sort 함수: C++ STL <algorithm> 헤더에 존재하며, 내부적으로 Intro Sort(인트로 정렬) 등을 사용하여 직접 구현보다 효율적임.

11. std::begin / std::end: 컨테이너의 시작과 끝 다음(past-the-end)을 가리키는 iterator를 반환함.

12. 인덱스(Index) 순회의 단점: 리스트(List) 등 직접 접근 불가 컨테이너에서 사용 불가, 타이핑 양이 많음.

13. 포인터 연산 순회의 한계: 요소가 메모리에 연속적으로 저장된 경우(배열 등)에만 작동함.

14. 포인터의 비순차적 활용: Linked List 등에서는 포인터 체인을 통해 순회가 가능함.

15. Iterator(반복자)의 정의: 컨테이너를 순회하도록 설계된 객체로, 각 요소에 대한 접근을 제공함.

16. For-each 루프의 원리: 내부적으로 Iterator를 사용하여 다양한 컨테이너(Array, List, Map 등)를 모두 순회할 수 있음.

17. Pointer Iterator: 가장 간단한 Iterator 형태로, 배열과 같이 연속된 메모리 공간에서 포인터 연산으로 순회함.

18. 배열 순회 시 주의사항 (Out of bound): arr[std::size(arr)]와 같이 크기만큼의 인덱스에 접근하면 정의되지 않은 동작(Crash) 발생.

19. Decay와 Iterator: C-style 배열은 포인터로 붕괴(Decay)되어 포인터 연산을 통해 end 위치를 계산할 수 있음.

20. STL Iterator 접근법: container.begin(), container.end() 멤버 함수를 사용해 편리하게 시작/끝 지점을 얻음.

21. C-style 배열의 STL Iterator 사용: <iterator> 헤더의 std::begin(), std::end() 전역 함수를 사용하여 처리 가능.

22. Iterator 비교 연산자 권장사항: >나 < 대신 !=를 사용해야 함. (일부 Iterator는 크기 비교를 지원하지 않기 때문).

23. For-each 루프 사용 조건: 멤버 함수 .begin()/.end()가 있거나, 전역 함수 std::begin()/std::end() 사용이 가능한 타입이어야 함.

24. For-each 사용 불가 케이스: 동적 C-style 배열이나, 포인터로 Decay 되어 길이 정보가 사라진 배열은 사용 불가.

25. Iterator Invalidation(무효화) 정의: 요소가 파괴되거나 메모리 주소가 변경되어 기존 Iterator가 Dangling 상태가 되는 현상.

26. Iterator Invalidation 발생 원인: vector의 메모리 재할당(Capacity 부족 시), erase() 등을 통한 요소 삭제 등.

27. erase() 함수의 반환값: 삭제된 요소 바로 다음 요소를 가리키는 Iterator를 반환함. (마지막 삭제 시 end() 반환).

28. STL Algorithm 사용 권장 이유: 검증됨(휴먼 에러 감소), 효율적임, 멀티 스레딩 지원 등.

29. STL Algorithm 카테고리 3가지: Inspector(검사), Mutator(변경), Facilitator(조력).

30. std::find: 특정 값의 첫 번째 발생을 찾음. 찾으면 해당 Iterator, 못 찾으면 end Iterator 반환.

31. std::find_if: 값이 아닌 '특정 조건'을 만족하는 요소를 찾음. 함수 포인터나 람다를 인자로 받음.

32. std::string_view::npos: find 류 함수에서 문자열을 찾지 못했을 때 반환되는 상수.

33. std::count vs std::count_if: 특정 값의 개수를 셀 때는 count, 특정 조건을 만족하는 개수는 count_if.

34. std::sort 커스텀 정렬: 3번째 인자로 비교 함수(함수 포인터, 람다)를 전달하여 정렬 기준(예: 내림차순)을 변경 가능.

35. std::greater: <functional> 헤더에 있으며, 내림차순 정렬 시 사용하는 표준 함수 객체.

36. C++17 std::greater 변경점: 템플릿 인자 타입(예: <int>)을 명시하지 않아도 됨 (std::greater{}).

37. std::function: 함수 포인터, 람다, 함수 객체 등을 담을 수 있는 범용 래퍼 클래스. (예: std::function<bool(int, int)>)

38. std::for_each: 컨테이너의 모든 요소에 대해 사용자 정의 함수를 적용함.

39. std::for_each의 장점: 의도가 명확하고, 루프 변수 관리 실수 방지, 특정 범위(시작/끝 건너뛰기) 지정 가능.

40. C++20 std::ranges: begin/end 쌍 대신 컨테이너 자체를 인자로 전달하여 알고리즘 사용 가능 (예: std::ranges::for_each(arr, func)).

41. std::next(): 현재 Iterator의 다음 위치(기본 1칸, 혹은 n칸)를 가리키는 Iterator를 반환.

42. 알고리즘의 실행 순서 보장: for_each, copy, move 등은 순차적 실행을 보장하지만, 그 외 알고리즘은 암묵적으로만 순방향임.





퀴즈


Q1. 배열의 모든 요소를 특정 조건이나 순서에 맞게 재배열하는 작업을 무엇이라고 합니까?

Q2. 실생활에서 볼 수 있는 정렬의 예시를 2가지 이상 적으시오.

Q3. 컴퓨터 입장에서 배열이 정렬되어 있을 때 얻을 수 있는 검색 측면의 이점은 무엇입니까?

Q4. 배열이 정렬되어 있다면 검색 자체를 수행하지 않고도 알 수 있는 정보는 무엇입니까? (예: 최대/최소)

Q5. 일반적인 정렬 알고리즘은 주로 어떤 두 가지 동작을 반복하며 수행됩니까?

Q6. C++ STL에서 두 변수의 값을 서로 맞바꿀 때 사용하는 함수의 이름과 필요한 헤더 파일은 무엇입니까?

Q7. 선택 정렬(Selection Sort)의 장점과 단점을 각각 하나씩 서술하시오.

Q8. 선택 정렬의 알고리즘 동작 3단계를 간략히 서술하시오.

Q9. 선택 정렬을 구현할 때 외부 루프의 종료 조건이 전체 길이보다 1 작은 이유(length - 1)는 무엇입니까?

Q10. C++ STL에서 제공하는 정렬 함수인 std::sort는 내부적으로 어떤 정렬 방식을 사용하며, 어떤 헤더가 필요합니까?

Q11. std::begin()과 std::end()가 각각 반환하는 것은 정확히 무엇입니까? (특히 end의 위치)

Q12. 인덱스(Index)를 이용한 컨테이너 순회 방식의 단점은 무엇입니까?

Q13. 포인터 연산을 이용한 컨테이너 순회가 작동하기 위한 전제 조건(메모리 구조)은 무엇입니까?

Q14. Linked List와 같이 메모리가 연속적이지 않은 구조에서 포인터를 이용해 순회하는 원리는 무엇입니까?

Q15. 컨테이너의 내부 구조와 상관없이 요소를 순회하고 접근할 수 있도록 설계된 객체를 무엇이라고 합니까?

Q16. For-each 루프가 배열, 리스트, 맵 등 다양한 컨테이너에서 모두 동작할 수 있는 핵심 원리는 무엇입니까?

Q17. 연속된 메모리 공간에서 포인터 연산을 통해 순회하는 가장 간단한 형태의 Iterator를 무엇이라고 합니까?

Q18. 배열 순회 시 arr[std::size(arr)]에 접근하면 어떤 문제가 발생합니까?

Q19. C-style 배열이 함수 등으로 전달되거나 사용될 때 포인터로 변환되는 현상을 이용해 end 포인터를 계산하는 것을 무엇이라 합니까?

Q20. STL 컨테이너(예: std::array)에서 Iterator의 시작과 끝을 얻기 위해 사용하는 멤버 함수의 이름은 무엇입니까?

Q21. 멤버 함수가 없는 C-style 배열에서 STL Iterator 방식을 사용하기 위해 필요한 헤더와 전역 함수는 무엇입니까?

Q22. Iterator를 이용한 루프 조건문에서 < 대신 != 연산자를 권장하는 이유는 무엇입니까?

Q23. For-each 루프(Range-based for loop)를 사용할 수 있는 컨테이너의 조건은 무엇입니까?

Q24. For-each 루프를 사용할 수 없는 C-style 배열의 상태 2가지는 무엇입니까?

Q25. 컨테이너의 요소가 파괴되거나 주소가 변경되어 기존 Iterator가 사용할 수 없는 상태가 되는 것을 무엇이라고 합니까?

Q26. std::vector에서 Iterator Invalidation이 발생할 수 있는 대표적인 상황 2가지를 적으시오.

Q27. std::vector::erase() 함수가 호출된 후 반환하는 값은 무엇입니까?

Q28. 직접 알고리즘을 구현하는 것보다 검증된 STL Algorithm 사용을 권장하는 이유는 무엇입니까?

Q29. STL Algorithm의 세 가지 카테고리(Inspector, Mutator, Facilitator) 중 데이터를 수정하지 않고 검사만 하는 것은 무엇입니까?

Q30. std::find 함수가 값을 찾지 못했을 때 반환하는 값은 무엇입니까?

Q31. 특정 값이 아니라 특정 '조건'을 만족하는 요소를 찾고 싶을 때 사용하는 함수는 무엇이며, 인자로 무엇을 받습니까?

Q32. 문자열 검색 시 find 류 함수가 실패했을 때 반환하는 std::string_view의 상수는 무엇입니까?

Q33. std::count와 std::count_if의 기능적 차이점은 무엇입니까?

Q34. std::sort를 사용하여 오름차순이 아닌 다른 기준으로 정렬하려 할 때, 3번째 인자로 무엇을 전달해야 합니까?

Q35. 내림차순 정렬을 위해 <functional> 헤더에서 제공하는 표준 함수 객체(Functor)는 무엇입니까?

Q36. C++17부터 std::greater 사용 시 문법적으로 간소화된 점은 무엇입니까?

Q37. 함수 포인터, 람다 함수, 함수 객체 등을 모두 담을 수 있는 C++의 범용 함수 래퍼 클래스는 무엇입니까?

Q38. 컨테이너의 모든 요소에 대해 사용자가 지정한 함수를 적용하는 STL 알고리즘은 무엇입니까?

Q39. 일반 For-each 루프 대비 std::for_each 알고리즘 함수를 사용할 때의 장점은 무엇입니까? (예: 범위 지정 관련)

Q40. C++20에서 도입된 기능으로, begin/end를 따로 넘기지 않고 컨테이너 자체를 인자로 넘겨 알고리즘을 수행하게 해주는 네임스페이스는 무엇입니까?

Q41. 현재 Iterator 위치에서 N칸만큼 이동한 위치의 Iterator를 반환해주는 함수는 무엇입니까?

Q42. std::for_each나 std::copy와 달리, 대부분의 STL 알고리즘이 실행 순서에 대해 보장하는 바는 무엇입니까? (순차적 실행 여부)






정답지

A1. 배열 정렬 (Sorting)

A2. 연락처 이름순 정렬, 이메일 최신순 정렬, 파일 크기순 정렬 등

A3. 이진 탐색(Binary Search) 등을 통해 검색 효율을 극대화할 수 있다.

A4. 최대값(Max)과 최소값(Min) (양 끝단에 위치하므로 검색 불필요)

A5. 비교(Compare)와 교환(Swap)

A6. std::swap, <utility> 헤더

A7. 장점: 이해하고 구현하기 쉽다. / 단점: 속도가 매우 느리다($O(N^2)$).

A8. (1) 전체 검색 후 최소값 찾기 (2) 현재 인덱스(0부터)와 교환 (3) 다음 인덱스로 넘어가 반복

A9. 마지막 요소 하나가 남았을 때는 이미 정렬된 상태이므로 비교/교환할 필요가 없기 때문이다.

A10. Intro Sort (인트로 정렬), <algorithm> 헤더

A11. begin()은 컨테이너의 첫 번째 요소를, end()는 마지막 요소의 바로 다음(past-the-end)을 가리키는 Iterator를 반환한다.

A12. 리스트(List)처럼 인덱스로 직접 접근이 불가능한 컨테이너에는 사용할 수 없으며, 타이핑이 번거로울 수 있다.

A13. 요소들이 메모리상에 연속적으로 저장되어 있어야 한다.

A14. 각 요소가 다음 요소의 주소를 저장하는 포인터 체인을 통해 연결되어 순회한다.

A15. Iterator (반복자)

A16. 내부적으로 해당 컨테이너의 Iterator를 사용하기 때문이다.

A17. 포인터 (Pointer)

A18. Out of bound 에러 (정의되지 않은 동작, 크래시 발생 가능)

A19. Decay (배열의 이름이 포인터로 붕괴됨)

A20. .begin() 과 .end()

A21. <iterator> 헤더의 std::begin() 과 std::end()

A22. 모든 Iterator 타입(특히 비순차적 컨테이너)이 크기 비교(>,<)를 지원하지는 않지만, !=는 모든 Iterator에 대해 작동하기 때문이다.

A23. begin()/end() 멤버 함수가 있거나, std::begin()/std::end()를 적용할 수 있는 타입이어야 한다.

A24. 동적 할당된 배열, 함수 인자로 넘겨져 포인터로 Decay된 배열 (길이 정보가 없음)

A25. Iterator Invalidation (이터레이터 무효화)

A26. (1) Capacity 초과로 인한 메모리 재할당 시, (2) erase() 등으로 요소가 삭제/이동되었을 때

A27. 삭제된 요소 바로 다음 요소를 가리키는 Iterator (마지막 요소 삭제 시 end() 반환)

A28. 이미 검증되어 휴먼 에러가 적고, 효율적이며, 멀티 스레딩 등을 지원하기 때문이다.

A29. Inspector (검사)

A30. 해당 컨테이너의 end Iterator

A31. std::find_if, 함수 포인터나 람다 함수(조건자)

A32. std::string_view::npos

A33. std::count는 특정 값과 일치하는 요소의 수를 세고, std::count_if는 특정 조건을 만족(True 반환)하는 요소의 수를 센다.

A34. 비교 함수 (함수 포인터, 람다, 함수 객체 등)

A35. std::greater

A36. 템플릿 인자 타입을 명시하지 않아도 된다. (예: std::greater<int>{} -> std::greater{})

A37. std::function

A38. std::for_each

A39. 의도가 명확하며, std::next 등을 이용해 시작이나 끝의 일부 요소를 건너뛰고 적용하기 쉽다.

A40. std::ranges (예: std::ranges::sort, std::ranges::for_each)

A41. std::next()

A42. 대부분의 알고리즘은 성능 최적화를 위해 순차적 실행 순서를 엄격하게 보장하지 않는다. (반면 for_each 등은 순차 실행 보장)