프로그래밍(c++)/Effective STL(C++)

Effective STL - Chapter5 [알고리즘(Algorithms)

정체불명의 모모 2021. 10. 25. 19:34

이번 장은 '알고리즘'입니다.

언제나 어려운 알고리즘...

이번 장의 목적은 2가지 입니다.

1. 편하게 해줄 알고리즘 소개

2. 알고리즘을 사용하면서 자주 만나게 되는 문제를 피하는 방법

위 목적을 달성하기 위해 정리를 할 겁니다.

그럼... Start!

알고리즘의 데이터 기록 범위는 충분히 크게 잡자
: 이 항목에서는 객체 삽입시 일어나는 문제에 대해 해결책을 제시 해주고 있습니다.

 

문제 : 객체를 컨테이너에 삽입(insert) 할때 아무런 객체가 없는 경우

 

▽ 예제 코드 ( transform함수를 이용하여 values객체에 있는 값을 * 10 한 값을 results에 기록하기)

values의 값을 10 곱해 results에 값을 넣으려 한다.

▽ 결과

ERROR!

왜 저런 에러가 발생했을까??

그 이유는 현재 results 컨테이너(results.end( )) 안에는 아무런 객체가 없기 때문입니다.

있지도 않은 객체에 대입 한다니 될 수가 없습니다.

해결 방법은

"transform의 처리 결과를 results 컨테이너의 끝에 넣어주세요" 라고

하면 된다.

결론적으로 말하면 목적지 범위의 시작을 지정해 줘야 한다는 것이다.

 

▽  수정 ( back_inserter를 통한 범위 시작 지정 )

목적지 범위의 시작을 정확히 지정을 한 후 컴파일이 되는것을 확인 할 수 있다.

 

 주의  back_inserter가 반환하는 반복자는 push_back을 호출하도록 되어 있기 때문에 back_inserter와 함께 쓸 수 있는

컨테이너는 push_back을 꼭 지원해야 합니다.(표준 시퀀스 컨테이너는 다 됨)

 

back_inserter(push_back) : 컨테이너 뒤에 front_inserter(push_front) : 컨테이너 앞에
모든 시퀀스 컨테이너 가능 deque , list

 

back_inserter(push_back) : 컨테이너 뒤에 front_inserter(push_front) : 컨테이너 앞에 inserter(임의의 위치 지정)
모든 시퀀스 컨테이너 가능 deque , list 모든 시퀀스 컨테이너 가능

 

삽입전 reserve 함수를 이용해 컨테이너의 용량(capacity)를 증가시켜 놓으면, 메모리를 다시 재할당 할 필요가
없어 집니다.
  또한, reserve를 호출 하면, 용량은 증가 하지만, 컨테이너의 요소 크기는 변하지 않습니다.
그러니 삽입 반복자를 사용하여 push_back or push_front 함수를 불러와 요소를 삽입해야 합니다.

▽ 최종 수정 예제

최종 수정 예제
예제 컴파일 결과

 

목적지 범위를 지정해야 하는 알고리즘을 사용할 때는

언제나 목적지 범위의 크기를 미리 확보하고, 알고리즘이 실행될 때 자동으로

요소가 증가하도록 만들어야 한다는 것 입니다.

(그러니, 삽입 반복자를 이용하세요.)

 

정렬시의 선택 사항들을 제대로 파악해 놓자
: 정렬할때 수많은 선택 사항들이 있다. 정렬시, 최선의 알고리즘을 이용하자!
  • 정렬의 범위
    - 전체 정렬 : sort
    - 부분 정렬 : partial_sort
    ㆍpartial_sort : 두 번째 인수로 지정한 SortEnd부분 직전까지만 정렬하고 나머지 뒷부분은 정렬되지 않은 채로
       내버려 둔다.

  • 부분 정렬 방법
    - 부분 순서 정렬 : partial_sort
    - 부분 순서 x 정렬 : nth_element 
       ㆍnth_element : 두번째 인수로 지정한 n에 n번째 값을 놓고 그 왼쪽에 n 보다 작은 값을 , 오른쪽에 n 이상의
          값으로 구간을 분할한다. 
          n의 위치만 정확하며 나머지 좌우 구간의 정렬 상태는 보증 되지 않는다.
      ㆍnth_element의 사용 목적 
         - 주어진 범위 내의 중앙값을 찾기
         - 백분위 위치에 있는 값을 찾아내기
         - 상위 n개의 요소나 특정 위치의 요소를 찾아 내기만 할 때
       
           (적은 데이터의 양에서는 좌우 구간이 정렬이 되어 있지만, 데이터의 양이 많으면 보장되지 않는다.)

적은양으로 인해 정렬이 완벽히 되어있다.
1000개의 랜덤 수에서 50번째 인수 구간의 정렬을 했다.(작아서 안보이네..;)
확대해 보면 근접 수만 정렬이 되어 있는것을 확인할 수 있다.(조건 : 50번째 인수)

  • 동등한 값의 정렬
    - 순서 유지 정렬 : stable sort
    - 순서 유지 x 정렬 : partial_sort / nth_element 등

    ㆍ순서 유지 정렬 이란? 
       : 두 개의 값이 동등하다면 정렬 후에도 그 둘의 상대적인 위치가 변하지 않습니다.

  • 주어진 범위에 요소의 위치 재배열
    - 동등한 값 정렬 : stable_partition
    - 동등한 값 정렬 x : partition
list의 경우 위 정렬 알고리즘을 사용할 수 없습니다. 
자체적으로 sort라는 멤버 함수를 제공하고 있습니다.(순서 유지성을 가진)

 

위 알고리즘 리소스를 적게 먹는 순서

1. Partition

2.stable_partition

3. nth_element

4.partial_sort

5.sort

6.stable_sort

 

참으로 다양한 정렬 알고리즘 함수들이 있는데요.

본인에게 필요한 상황에 맞춰 쓰면

훨씬 자원을 아낄 수 있습니다.

요소를 정말로 제거하고자 한다면 remove류의 알고리즘에는 꼭 erase를 붙여 사용하자.
: 제대로 remove의 의미를 파악하자

우선 remove의 정체에 대해 알아보자

 

▷ remove 

: 리무브는 자신이 조작할 데이터 요소의 범위를 나타내는 한쌍의 반복자를 받아들입니다.

  컨테이너를 받아들이지 않기 때문에, 어떤 컨테이너가 요소를 가지고 있는지는 알 방법이 없습니다.

  또한, 컨테이너의 정체를 밝혀 내는 것 자체도 불가능 합니다.

template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T & value);

Q. 어떻게 컨테이너도 모르는 알고리즘이 요소를 제거 할 수 있나요?

A : 아래의 예제 코드를 확인 후 얘기하겠습니다.

 

▽ 예제 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void printV(vector<int> values)
{
    for(int value : values)
    {
        cout << value << " " ;
    }
    
    cout << endl;
}

int main()
{
    vector<int> v;
    v.reserve(10);  // 공간 예약
    for(int i = 1 ; i <= 10; i++)
        v.push_back(i);
    
    cout << v.size() << endl;
    
    v[3] = v[5] = v[9] = 99;
    cout << " ============== remove 후 ============== " << endl;
    remove(v.begin(), v.end(), 99);
    
    cout << v.size() << endl;
    printV(v);
    
    return 0;
}

결과 값

A : remove함수를 이용하여 요소를 지우려 해봤지만, 요소는 지워지지 않았습니다.

     remove는 어느것도 "진짜로" 없애지 않는다. 없앨 수 없기 때문이다.  <= 저자가 강조하는 말

 

- remove가 요소를 지우지 못하는 이유 : remove는 자신이 제거하려고 하는 요소를 가진 컨테이너가 무엇인지 모르기 때문에, 진짜로

   요소를 제거할 때 필요한 멤버 함수를 호출할 방법을 전혀 가지고 있지 않습니다.

 

- remove가 하는일 : remove는 주어진 범위 내의 요소를 재배열 합니다.

   이 때 "제거 되지 않은" 요소를 범위의 앞쪽에 가져다 놓습니다. 그리고 "제거되지 않은" 요소 중 마지막 것의 바로 뒤를 가리키는
   반복자를 반환하는 것으로 자신의 동작을 마칩니다.

 

     사실, remove는 "제거된" 요소를 주어진 범위의 끝 부분에 옮기는 식으로 동작하지 않으며,

   단지 "제거되지 않는" 요소를 범위의 앞부분으로 옮기는 일만 충실히 할 뿐입니다.

 

      내부적으로 , remove는 주어진 범위를 처음부터 끝까지 훑어 가면서, "제거될" 요소의 위치에다가 그 뒤에 있는 "그대로 유지될"
   요소의 값을 덮어 씁니다. (실제로 덮어쓰기 동작은 대입으로 이루어 집니다.)

    

Q. 진짜로 요소를 제거 하는 방법은??

A : remove 와 컨테이너의 멤버 함수인 erase이용 하기!

vector<int> v;
v.erase(remove(v.begin() , v.end() , 99) , v.end());
list에서는 erase-remove 합성문 대신에 remove 멤버 함수가 훨씬 효율적 입니다.
(list의 remove는 remove + erase 합성 한 함수)

erase-remove 이용한 후 컨테이너 요소 확인

※ unique는 요소의 범위를 가지고 있는 컨테이너가 무엇인지 알지 못하는 상태에서 데이터(중복되는 인접한 값들)을 없애는 함수 입니다.

    (unique도 중복된 요소를 진짜로 없애려면 erase를 같이 호출해야 한다.)

remove와 비슷한 알고리즘을 포인터의 컨테이너에 적용할 때에는 조심하자.

상황 : 컨테이너에 들어 있는 포인터를 그냥 erase - remove 해버림

결과 :  그냥 포인터를 없애 버리면 그 포인터가 가리키는 것을 삭제해 버릴 수 없습니다.

           (메모리 누수가 일어나게 됩니다!!!!!)

설명 : Widget 객체가 B와 C를 가리키고 있었지만 "제거되는" 포인터 자리에, 그 뒤에 있는

"제거되지 않는" 포인터의 값이 덮어 쓰여진 것 입니다. 

결국 자신을 가리키던 포인터를 잃었기 때문에 delete 되지 않게 됩니다.

ㅁ 해결 방법

 

1. 참조 카운팅 기능을 가지고 있는 스마트 포인터 이용하여 자동으로 소멸하게 만들어 주기 ( smart_ptr )

2. remove 와 유사한 알고리즘을 호출하기 전에 포인터에 대한 메모리를 미리 해제 하고 null로 세팅

 

위 두 방법으로 erase - remove 하기 전에 컨테이너의 포인터 객체에 대해 어떻게 메모리 해제 할 지 생각해 봅시다!

정렬된 범위에 대해 동작하는 알고리즘이 어떤 것들인지 파악해 두자
: 알고리즘 소개 시작~!

 

1. binary_search , lower_bound , upper_bound , equal_range 탐색 알고리즘

: 위 알고리즘은 반드시 정렬된 범위가 필요합니다. 

  내부적으로 이진 탐색을 사용하여 값을 찾기 때문입니다.

  (대략 로그 시간의 탐색 효율을 보장해준다. -> 임의 접근 반복자일 경우 , 양방향 반복자인 경우에는 선형의 시간이 걸림)

binary_search 단순히 검색하는 알고리즘 입니다. 찾는 값이 있으면 true, 아니면 false를 return 해줍니다.
lower_bound lower_bound는 찾으려 하는 key값이 "없으면" key값보다 큰 가장 작은 정수 값을 찾습니다.
upper_bound upper_bound는 key값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것 입니다.
(오름차순으로 정렬되어 있어야 함)
equal_range lower_bound 와 uppder_bound 를 같이 묶어 리턴해줍니다.

ex ) equal_range(v.begin() , v.end() , 3);
해당 범위 내에서 처음으로 3과 같거나 큰 원소의 반복자, 해당 범위 내에서 처음으로 3보다큰 원소의 반복자

2. set_union , set_intersection , set_difference, set_symmetric_difference

: 집합(set) 조작 알고리즘 이며 , 선형 시간의 효율을 보입니다.

   정렬된 범위를 넣는 이유는 정렬하지 않은 범위는 터무니 없이 너무너무 느려서 정렬 후 동작 시키는 것 입니다.

 

3. merge와 inplace_merge

: 두 개의 정렬된 범위를 받아 이것을 합쳐 정렬된 하나의 범위로 만드는 알고리즘, 선형의 시간이 걸린다.

  (두 범위 중 하나라도 정렬되어 있지 않으면 동작하지 않습니다.)

 

4. includes

: 어떤 범위 안에 우리가 원하는 값이 들어 있는지의 여부를 알아볼 때 사용합니다.

   includes는 자신이 받아들이는 범위내의 데이터가 정렬되어 있음을 가정하고 동작하기 때문에 선형 시간의 효율을 보입니다.

ㅁ 그 외, 정렬되지 않은 범위에서 사용하는 알고리즘

- unique , unique_copy(위에 설명이 있습니다.)

: 위 두 알고리즘은 범위가 정렬되지 않은 상태에서도 잘 동작합니다.

정렬된 범위에 대해 동작하는 모든 알고리즘은 두 개의 값이 같은지를 판정할 때 동등성을 기준으로 삼습니다.
 이와 반대로 unique 와 unique_copy는 상등성에 의해 두 객체의 같음을 판정합니다.
대소문자를 구분하지 않는 문자열 비교는 lexicographical_compare를 써서 간단히 구현할 수 있다.

strcmp가 넘보기에 힘든 언어별 문자열이나 영어 이외의 다른 언어로 쓰여진 텍스트를 가진

문자열의 대소문자를 구분하는 방법을 알아보자

 

ㅁ lexicographical_compare

: strcmp를 일반화한 알고리즘 입니다.

  즉, strcmp는 문자 배열에 대해서만 동작하는 반면 lexicographical_compare에 들어가는 범위 안의

  데이터는 어떤 타입도  될 수 있습니다.

   또 한, strcmp는 두 개의 문자를 코드 값으로 비교해서 같은지, 작은지 ,큰지를 점검하는 반면,

  lexicographical_compare에는 비교되는 두 요소의 대소 관계를 정할 수 있는 기준을 만들어 넣어줄 수 있습니다.

bool ciCharLess(char c1 , char c2)
{
    return tolower(static_cast<unsigned char>(c1))
    < tolower(static_cast<unsigned char>(c2));
}

bool ciStringCompare(const string & s1, const string & s2)
{
    return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), ciCharLess);
}
copy_if를 적절히 구현해 사용하자
: 여기서는 copy_if를 사용하는 방법에 대해 설명하겠습니다.
  • copy(InputIt first , InputIt last , OutputIt d_first) : 함수는 first 부터 last 전 까지의 모든 원소들을 d_first 부터 시작하는 곳에 복사한다.
  • copy_if(InputIt first , InputIt last , OutputIt d_first , UnaryPredicate pred) : pred가 true를 리턴하는 원소만 복사하게 된다. 이때 원소들의 상대적인 순서는 유지된다.(pred - 조건을 확인하는 함수)

▽ 간단한 copy_if 예제

bool test(int n)
{
	if (N % n == 0)
		return true;

	return false;
}

int main()
{
	list<int> src;
	list<int> dest;

	for (int i = 1; i <= N; i++)
		src.push_back(i);

	copy_if(src.begin(), src.end(), back_inserter(dest), test);

	cout << N << "의 약수 : ";

	for_each(dest.begin(), dest.end(), [](int n) {cout << n << " "; });

	return 0;
}
범위 내의 데이터 값을 요약하거나 더하는 데에는 accumulate나 for_each를 사용하자

"범위를 요약한다." : 예를 들어 컨테이너 안의 string의 길이의 합을 구한다든지, 주어진 범위의 숫자들의 곱을 구한다

든지 하는 거죠. 이런 1차원적인 정보가 아니라 좌표 같은 2차원 이상의 값들의 평균을 구하고 싶을 때를 통칭하여

'범위를 요약한다.' 라고 합니다.

 

ㅁ 수치 알고리즘인 'accumulate' (header -> numeric)

 

ㆍ accumulate 란? : 지정한 구간에 속한 값들을 모두 더한 값을 계산한다.

    - 첫번째 형태 : 두 개의 반복자와 초기 값을 받아들여 범위 내의 값의 합을 초기 값에 더한 결과를 반환합니다.

 

list<double> ld;
...
double sum = accumulate(ld.begin() , ld.end() , 0.0);

  ※ 주의 사항으로 초기값이 '0.0' -x-> '0'으로 설정할 경우 double로 값을 받아야 하는데, int로 인지하고 결과 값이

     바뀔 수 있습니다.(그러니 , 반환값의 데이터형과 초기값의 데이터형을 잘 맞추어야 합니다.)

ㆍ두번째 형태 : 초기값과 요약용 함수를 받아 동작합니다.

 

▽ 두번째 형태 예제(string 객체의 문자열 길이의 합을 구하기)

string::size_type stringLengthSum(string::size_type SumSoFar, const string & s)
{
	return sumSoFar + s.size();
}

set<string> ss; 
...  
string::size_type lengthSum =
  accumulate(ss.begin() , ss.end() , 0, stringLengthSum);

ㅁ for_each란? : 이 알고리즘은 범위 내의 데이터를 요약할 수 있는 또하나의 알고리즘입니다.

for_each는 범위와 그 범위 내의 요소에 대해 호출할 함수를 받아들이는데, 이 알고리즘에 넘겨지는 함수는 자신이 처리할  단 하나의 요소만을 받아들이며, for_each는 자신의 수행을 마칠 때 이 함수를 반환합니다.(함수의 사본)

 

▷ for_each 와 accumulate의 다른 점

  • 첫 번째 : 'accumulate'는 "범위를 요약한다"라는 느낌이 강한 반면, 'for_each'는 "범위 내의 모든 요소에 어떤 일을 한다" 라는게 강합니다.(저자의 왈)
  • 두 번째 : 'accumulate'는 우리가 원하는 요약 결과를 바로 반환 하지만, 'for_each'는  자신이 매개 변수로 받은 함수 객체를 반환하기 때문에 이 객체에서 요약 정보를 뽑아 내야 합니다.
    'for_each'는 넘기는 함수자 객체에다가 요약 정보를 얻어낼 수 있는 멤버 함수를 추가해야 한다는 의미 입니다.

 

오늘은 매우 다양한 알고리즘에 대해 공부해 보았는데요.

알고리즘의 세계는 언제나 아득합니다.

그럼... 이만...

다들... 공부합시다..