뇌를 자극하는 C++ STL : 8장. 알고리즘

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 8장. 알고리즘

STL에는 100여개의 알고리즘이 있으며, 크게 7개로 분류가능

 

- 원소를 수정하지 않는 알고리즘

- 원소를 수정하는 알고리즘

- 제거 알고리즘

- 변경 알고리즘

- 정렬 알고리즘

- 정렬된 범위 알고리즘

- 수치 알고리즘

 

이중 2개정도만 글로 아주 간단히 정리하겠습니다.

 

원소를 수정하는 알고리즘

- transform()

순차열의 모든 원소에 사용자의 의도를 적용시키려면 for_each() 나 transform() 알고리즘을 상요합니다.

trandform()이 for_each() 알고리즘과 다른점은 원본은 변함이 없고, 목적지의 순차열로 저장한다는 점 이다.

다음 코드를 통해 확인해보자.

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

using namespace std;

int Func(const int& n)
{
	return n + 5;
}

int main()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;

	transform(v.begin(), v.end(), v.begin(), Func);

	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;

	return 0;
}

 

결과는 다음과 같다.

transform() 알고리즘의 사용자 정책 함수는 return값 을 사용하므로 for_each와는 다르게 return type을 갖고있다.

 

함수의 작동방식이 callback함수의 원리와 같다. 클라이언트 부분에서 tranform의 인자로 Func를 전달하였다.

이 Func의 주소가 서버의(STL내부) transform함수의 인자로 전달된다.

Iterator transform(Iterator first, Iterator last, iterator target, Function fun)
{
    for(Iterator p = first; p != last; p++)
        *target++ = fun(*p);
    return target;
}

 

서버 코드 구현부에서 fun(*p) 즉 Func(*p)가 실행되고, 이로인해 n에 5가 더해진후 반환값을 전달받는다.

 

정렬 알고리즘

heap 구조를 만든후 이를 이용한다. 만들어진 heap에 push_back()으로 원소를 추가한후, push_heap()으로 힙 연산을 수행하여 자신의 자리를 찾아가도록 한다. 다음 코드를 통해 확인해 보자.

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

using namespace std;

int main()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	v.push_back(60);

	make_heap(v.begin(), v.end());

	cout << "v[힙 생성] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;

	v.push_back(35);

	cout << "35 추가 : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;

	push_heap(v.begin(), v.end());

	cout << "v[힙 추가] 연산 수행 : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;

	return 0;
}

 

위의 코드를 도식으로 생각해보자.

            60                 
         /       \  
       50         30  
      /  \        /  \
    40    20    10   

 

맨 처음 heap을 생성하면 위와같은 구조의 heap이 생성된다. 여기에 push_back을 통하여 트리의 끝에 원소 35를 추가해보자.

            60                 
         /       \  
       50         30  
      /  \        /  \
    40    20    10    35

 

이제 push_heap을 통하여 힙 추가 연산을 수행하여 힙 구조를 유지해보자.

            60                 
         /       \  
       50         35  
      /  \        /  \
    40    20    10    30

 

35와 30의 노드가 교환된것을 알 수 있다.

 

이번 8장 알고리즘 단원은 페이지수로만 치면 150페이지 정도 되는 방대한 양이였다...

---

 

2) 나의 현황

하 공부 계획이 너무 머리안에서 복잡하다. 원래 자료구조를 C언어로 공부해봐서 건너뛰고 STL 사용법만 익힌후 바로 알고리즘으로 뛰어들려 했는데.... 뭐랄까 매우 거슬린달까.... C++로 자료구조를 공부를 한달간 해보고 알고리즘으로 뛰어들까?? 요즘 고민이 많다...

​

이글의 모든 사진과 내용의 출처는 공동환 님께 있습니다.