알고리즘 코딩기법 - 5. STL

안녕하세요 조일룡입니다.

오늘은 C++에서 표준 라이브러리로 채택된 STL에 대해 간략하게 알아보겠습니다.

STL은 Standard Template Library의 약자로 템플릿을 이용한 표준 라이브러리.. 뭐 이정도의 의미를 가지고 있습니다.

아래의 주소에서 STL에 대한 모든것을 알 수 있습니다.

http://www.cplusplus.com/reference/stl/


이번 포스팅에서는 템플릿에대해 잠깐 짚어보고, STL에서 제공하는 컨테이너 중 가장 흔히 사용하는 'vector'에 대해  알아보겠습니다.


Template

템플릿을 건너뛰고 싶었지만 역시 언급을 해야할 것 같습니다.

템플릿은 컴파일타임에 자료형을 확정하여 그 자료형에 맞는 코드를 생성하는 C++에서 제공하는 기능입니다.

두개의 정수형 변수를 받아 값을 맞바꾸는 아래의 함수를 봅시다.

void swap(int & a, int & b)
{

if (a != b) a ^= b ^= a ^= b;

}

만약 실수형 변수를 받아 똑같은 일을 하는 함수가 필요하다면 우리는 아래와 같은 함수를 재정의 해야합니다.

void swap(double & a, double & b)
{

if (a != b) a ^= b ^= a ^= b;

}

단지 자료형만 다를 뿐 함수의 몸체는 동일한 구조를 가진 함수를 따로 구현하려니 여간 귀찮은 일이 아닙니다. 그래도 함수를 구현하는 일이니 좀 참아줄만 하네요.. 근데 클레스에서 이 짓을 해야한다면 참을 수 있을까요?

한 프로그램에서 int 형의 자료를 저장하는 스택과 double 형의 자료를 저장하는 스택이 필요한 경우를 가정해봅시다. 이 때 두 가지 형태의 스택을 각각 구현하려 생각하는 짜증이 밀려 오는군요... 하지만 어쩔수 없이 노가다 근성으로 코딩을 하겠지요.
일단 int형 스택을 구현하고 control+C -> contro+V 콤보를 작렬한 후 replace all(int->double)을 감행합니다.

휴.. 그나마 붙여넣기, 모두바꾸기 신공으로 그렇게 큰 노력을 들이지 않고 각각의 클레스를 만들긴 했습니다. ^^;

그런데 프로그램을 실행하다 보니 이상하게 프로그램이 죽는군요.. 어디가 잘못됐는지 찾아보니 스택이 문제입니다..
열심히 디버깅을 해서 오류가 난 지점을 찾아 제대로 작동하게 고쳤습니다.
이제 다시 프로그램을 실행하는데.. 또 죽는군요.. 이건 또 뭘까요.. 디버그를 해서 찾아보니...
아.. 아까전에 int형 스택만 고치고 double형 스택은 안고쳤네요 ㅠㅠ


템플릿을 사용하여 swap을 구현해봅시다.

template<class ItemType>
void swap(ItemType & a, ItemType & b)
{

ItemType temp = a;
a = b;
b = temp;

}

위의 swap과 모양이 약간 다른데요.. 위의 swap에서는 비트연산을 통해 두 변수의 값을 맞바꾸었지만 아래에서는 temp변수를 사용해서 바꿨습니다.
template을 통해 넘어오는 변수의 자료형이 비트연산으로 값을 맞바꿀수 없는 경우가 있을 수 있기 때문인데요.. 예를 들어 string같은 자료형은 비트연산으로 그 값을 맞바꿀 수 없지요.. 대신 저렇게 해야합니다. 물론 대입연산자 재정의는 필수입니다.


Template의 원리

제 경험상 많은 친구들이 template의 사용은 잘 하지만 이게 어떻게 동작하는지는 잘 모릅니다. 어떤 친구는 런타임시에 어떤 메커니즘이 작동하는거 아니냐고 하더군요 그렇기 때문에 template을 쓰면 속도가 느려진다고 하면서...

그 친구에게 유감스럽지만 template은 런타임시에 자료형을 보고 적절한 처리를 하는 것이 아닙니다. C++ 컴파일러가 그렇게까지 똑똑하진 않나봅니다. 사실은 그렇게까지 똑똑해질 필요는 없습니다.

C++은 단지 컴파일시간에 template으로 작성된 함수나 클래스를 사용하는 클라이언트를 보고 필요한 자료형으로 확장된 함수나 클레스를 각각 만들어 줍니다. 그러니깐 붙여넣기 + 모두바꾸기 신공을 컴파일러가 해주는 샘이지요 ㅎㅎ.. 컴파일이 약간 느려질수는 있겠습니다만 템플릿 때문에 실행속도가 느려졌다는 말은 어불성설이겠네요..




vector

vector는 STL에서 제공하는 컨테이너중 하나로 제 생각엔 가장많이 사용되는 컨테이너가 아닐까 생각됩니다.

vector는 배열과 같은 일을 합니다. 연속적인 공간에 템플릿으로 정의된 자료형의 배열을 할당하여 그 후에는 배열처럼 사용할 수 있습니다. 그리고 여러 STL에서 제공되는 algorithm 함수와 함께 강력한 기능을 제공합니다.


vector vs array

c++에선 이미 배열을 기본 데이터타입으로 제공을 합니다. 그런데 vector를 쓰는 이유는 무엇일까요?
가장 큰 이유는 동적할당 때문일 겁니다.

c++에서 배열을 잡을 때 컴파일시간에 배열의 크기를 모르면 배열을 잡을 수 없습니다. 즉 배열의 크기는 변수가 될 수 없고 오로지 상수만이 가능합니다. 이를 극복하기 위해 동적할당이 제공됩니다. c에서는 malloc 함수를 쓰고 c++에서는 new 객체를 사용합니다.
위의 기능을 활용하여 런타임에 적절한 배열의 크기를 알아내서 적절하게 배열을 할당할 수 있습니다.

그럼 왜 vector일까요?

런타임시에도 배열을 얼마나 크게 잡아야 할지 모르는 경우를 생각해봅시다. 예를 들어 장기게임을 하는데 한 수 한 수를 배열에 저장하고 싶습니다. 그런데 장기게임이 몇 수 만에 끝날지는 아무도 모르기 때문에 배열을 잡기가 쉽지 않습니다.
방법중 하나로 배열을 그냥 대충 엄하게 크게 할당하고 시작할 수는 있습니다. 왠만하면 그 배열크기를 초과할 만큼 게임이 진행되지는 않게 크게 잡습니다. 대부분의 게임은 배열을 오버플로우를 발생시키지 않고 종료됩니다. 하지만 여기에는 두가지의 문제점이 있습니다.

첫번재 문제점은 메모리의 낭비입니다. 대부분의 경우 잡아놓은 배열을 다 쓰지 않고 버려진채 게임이 끝납니다.
두번째 문제점은 메모리 오버플로우의 가능성이 있다는 것입니다. 두 기사가 너무 방어적이라 좀처럼 게임이 끝나지 않고 계속 진행되다 보면 잡아놓은 배열을 모두 쓰고도 모자란 상황이 발생할 수 있습니다. 이때 게임은 외마디 오류박스를 띄우고 사라지겠지요.

위의 문제를 해결하기 위해서 일단 배열을 적당히 작게 잡고 필요할때마다 더 큰 배열을 할당하는 방법이 있습니다. 장기를 예로 보면 대부분 장기를 하면 50수까지는 둔다는 정보가 있다고 가정합시다. 그럼 첫 번째 배열은 크기를 50으로 잡습니다. 게임이 진행되다가 50수가 넘으면 100개짜리 배열을 새로 잡고 50수까지의 기록을 100개 짜리 배열에 복사를 합니다. 그후 50개짜리 배열은 메모리에서 해제를 하고 이제부턴 100개짜리 배열을 씁니다. 이런식으로 배열의 크기가 더 커질 필요가 있을 때 마다 새로 메모리를 할당하는 방법이 있습니다만. 귀차니즘이 텍사스 소때처럼 몰려옵니다.

만약 한 프로그램내에서 저런 배열이 여러개 있어야 한다면 각각 구현해야 하는데 정말 귀찮아 죽겠습니다. 그렇다면 객체지향프로그래밍 페러다임을 도입해 클래스로 저런 배열을 구현해 놓고 가져다 쓰는게 그나마 좀 영리한 선택이 되겠지요? 거기에다가 템플릿의 편리함 까지 추가해서 언제어디서나 쓸 수 있게 만들어 놓읍시다.. ㅋㅋㅋ 클래스를 구현할땐 좀 귀찮지만 나중을 생각하면 기분좋은 일이내요

그런데 C++을 사용하는 프로그래머들에게 사막 한 가운데의 오아시스 같은 존재가 있었으니 그것이 바로 STL입니다.

STL에선 바로 저런 배열 클레스를 vector라는 이름으로 제공을 하고 있습니다. 저 같은 귀차니즘에 감염된 종자들에게 구원의 손길과 같게 느껴지네요.


vector를 사용해보자

우선 vector의 멤버함수를 살펴봅시다.

Member functions

(constructor)

Construct vector (public member function)

(destructor)

Vector destructor (public member function)

operator=

Copy vector content (public member function)

Iterators:

begin

Return iterator to beginning (public member type)

end	Return iterator to end (public member function)

rbegin

Return reverse iterator to reverse beginning (public member function)

rend	Return reverse iterator to reverse end (public member function)

Capacity:

size	Return size (public member function)

max_size

Return maximum size (public member function)

resize

Change size (public member function)

capacity

Return size of allocated storage capacity (public member function)

empty

Test whether vector is empty (public member function)

reserve

Request a change in capacity (public member function)

Element access:

operator[]

Access element (public member function)

at	Access element (public member function)

front

Access first element (public member function)

back	Access last element (public member function)

Modifiers:

assign

Assign vector content (public member function)

push_back

Add element at the end (public member function)

pop_back

Delete last element (public member function)

insert

Insert elements (public member function)

erase

Erase elements (public member function)

swap	Swap content (public member function)

clear

Clear content (public member function)

Allocator:

get_allocator

Get allocator (public member function)

http://www.cplusplus.com/reference/stl/vector/

100개의 숫자를 임의로 생성하고 비내림차순으로 소팅하여 출력하는 아래의 프로그램을 봅시다.

#include <cstdlib> #include <ctime> #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int i; srand(time(NULL)); // 벡터를 선언합니다 vector<int> nums; // 100개의 난수를 생성하여 벡터에 추가합니다 for (i = 0; i < 100; i++) nums.push_back(rand()); // 비내림차순으로 정렬 sort(nums.begin(), nums.end()); // 화면에 출력 for (i = 0; i < 100; i++) cout << nums[i] << endl; return 0; }

위의 프로그램에서는 push_back() 함수를 사용하였습니다만 vector에 추가될 원소의 갯수를 미리 알고 있다면 생성자에서 미리 배열의 크기를 지정하여 시간과 메모리를 아낄 수 있습니다.
int main() { int i; srand(time(NULL)); int N = 100; vector<int> nums(N, 0); for (i = 0; i < N; i++) nums[i] = rand(); sort(nums.begin(), nums.end()); for (i = 0; i < N; i++) cout << nums[i] << endl; return 0; }


마지막으로 vector<int> 형 배열을 전달받아 합과 평균을 리턴하는 함수를 작성해보겠습니다. 평균은 반올림합니다.
vector<int> SumAvg(vector<int> array) { vector<int> ans; int sum = 0; for (int i = 0; i < array.size(); i++) { sum += array[i]; } ans.push_back(sum); ans.push_back((double)ans / array.size() + 0.5); return ans; }


이것으로 이번 포스팅은 마치겠습니다. 힘드네요 ^^;

다음 포스팅은 비트연산(bit operation)을 이용한 Brute Force Search 방법에 대해서 쓸까합니다. 간략히 설명하자면 Brute Force는 해의 후보가 될 수 있는 모든 문제 공간을 탑색하여 최적을 찾는 방법입니다. 문제를 해결하는 가장 확실하면서도 쉬운 방법인 반면에 수행 시간이 긴 단점이 있죠.. 주로 모든 문제 공간을 탐색해야 하는 경우에 사용됩니다.