시그마알파

안녕하세요 CODER_JH입니다.

제가 가장 좋아하는 알고리즘 파트네요 ㅎㅎ

알고리즘이 뭘까요?? 위키백과의 말을 빌리도록 하겠습니다.

알고리즘 : 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다. 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다.

이렇다고 하네요..

그렇다면 본격적으로 잘 알려진 알고리즘을 하나씩 알아보도록 하겠습니다. 

먼저 가장 기본적인 탐색 알고리즘의 순차탐색과 이진탐색에 대해 알아보겠습니다.

<순차탐색>

순차탐색이란 말그대로 앞에서 부터 순차적으로 하나하나 탐색해 나가는 것입니다.

찾고자 하는 값이 앞쪽에 있다면 짧은 시간에 찾아낼 수 있지만 뒤쪽에 있다면 오래 걸리겠죠?(비효율적이란 얘기입니다.)

그림으로 알아 보도록 하겠습니다.

참쉽죠? ㅎ

코드로 작성해 보겠습니다.

-> 매우 간단하내요 arr[0] ~ arr[9] 까지 for문을 돌려 만약 찾고자하는 값가 같으면 탐색을 멈추는 소스 입니다.

-> 순차탐색의 시간복잡도는 탐색리스트가 n개라면 O(n)이 되겠내요.

다음은 이진탐색에 대해 알아보도록 하겠습니다.

<이진탐색>

이진탐색이란 이름에서 뭔가 느껴지지 않나요? 탐색할 때 마다 탐색 범위가 반으로 줄어들기 때문입니다.

이진탐색을 하기위해선 탐색 리스트가 정렬되어 있다는 전제가 있어야 합니다.

10억개의 데이터 리스트를 순차탐색으로 탐색할 때 평군 5억번의 비교를 해야됩니다. 그러나 이진탐색으로 탐색할 경우 최대 33번의 비교로 값을 찾아낼수있습니다. 이 수치만 보더라도 이진탐색이 매우 효율적이라는 것을 알수있습니다.

그림으로 알아 보도록 하겠습니다.

-> 정렬된 데이터셋에서 중간값을 구합니다. 후에 찾고자 하는 값과 비교합니다. 찾고자 하는 값이 더 크므로 5보다 작은 값은 버리고 6~10을 보게됩니다.

->6~10사이의 중간값인 8과 찾고자 하는 값을 비교합니다. 찾고자하는 값보다 크므로 8이하는 버리고 9~10을 보게됩니다.

->이렇게 9와10이남아버리면 값을찾게 됩니다.

->3번의 탐색만에 값을 찾게됬내요~

코드로 작성해 보겠습니다.

->소스도 그렇게 어려운 부분은 없는 것같내요 ㅎㅎ

->이해안가는 부분있으면 댓글 달아주세요~

탐색의 2가지 알고리즘에 대해 알아봤습니다. 기본적인 것이므로 충분히 이해하고 가시기 바랍니다.

다음 시간에는 정렬 알고리즘에 대해 하니씩 파헤쳐 보도록 하겠습니다.

저번 시간에 이어 vector 컨테이너에 대해 알아 보도록 하겠습니다.

vector 컨테이너는 배열 기반 컨테이너 이므로 일반 배열처럼 임의 위치의 원소를 참조하는 두 인터페이스를 제공합니다.

바로 [ ] 연산자, at( ) 멤버함수입니다.

두 인터페이스의 기능은 같지만 [ ] 연사자는 범위 점검을 하지 않아 속도가 빠르며 at( ) 멤버 함수는 범위를 점검하므로 속도는 느리자만 안전합니다.

예제를 통해 이해해 보도록 하겠습니다.

<vector의 [ ]연산자와 at( ) 멤버 함수>

@ 

->[ ] 연산자는 범위 점검 없이 동작하며 at( ) 멤버 함수는 범위 점검을 하며 동작합니다. 만약 at( ) 멤버 함수 사용시 범위를 넘어가게 되면 범위 오류인 out_of_range 가 발생하게 됩니다.

이번엔 반복자에 대해 알아 보도록 하겠습니다.

컨테이너는 모든 원소의 시작과 끝을 가리키는 반복자 begin( )과 end( ) 멤버 함수로 제공합니다.

< vector의 begin( )과 end( )>

@

->iter는 반복자이며 ++연산자로 다음 원소로 이동하고 *연산자로 가리키는 원소를 참조합니다.

그림으로 보니 이해하기 더 쉽죠?ㅎㅎ

배열 기반 컨테이너인 vector와 deque는 임의 접근 반복자를 제공하며 임의 접근 반복자는 +, -, +=, -=, [ ]연산이 가능합니다.

<insert( ) 멤버 함수의 사용>

-> 반복자가 가리키는 바로앞에 값이 삽입되내요^^

삽입을 했다면 삭제도 있어야 겟죠?

<erase( ) 멤버 함수의 사용>

->v.erase(iter) : iter가 가리키는 위치의 원소(30)을 제거. 제거된 원소의 다음 원소를 가리키는 반복자를 반환

->v.erase(v.begin( )+1, v.end( )) : 구간 [v.begin( )+1, v.end( ))의 원소 (20,40,50)을 제거

vector 컨테이너의 몇가지 멤버함수를 알아 봤는데요. 이 외에도 더많은 함수를 제공한답니다.

오늘로서 표준 시퀀스 컨테이너이자 배열기반의 컨테이너인 vector의 포스팅을 마치고 다음시간에 deque에 대해 알아 보도록 하겠습니다.

글이 딱딱한 느낌인데 재밋게 써보도록 해보겠습니다^^

이번 장에서는 STL 컨테이너 중 시퀀스 컨테이너에 대하 알아보도록 하겠습니다.

STL 컨테이너는 시퀀스 컨테이너와 연관 컨테이너로 나눌 수 있습니다.

시퀀스 컨테이너 : 저장 원소가 삽입 순서에 따라 상대적인 위치를 갖는 컨테이너 (vector, list, deque)

연관 컨테이너 : 특정 정렬 규칙에 따라 상대적인 위치를 갖는 컨테이너(set, map, multiset, multimap)

먼저 시퀀스 컨테이너 중 하나인 vector컨테니어 에 대해 알아 보도록 하겠습니다.

vector 컨테이너는 배열과 비슷하여 사용이 쉽고 자주 사용되므로 잘 익혀 두시기 바랍니다.

<vector의 구조>

vector는 원소의 저장 위치가 정해지며 배열 기반 컨테이너이므로 원소가 하나의 메모리 블록에 할당된다.

시퀀스 컨테이너는 차례차례 원소를 추가하고 제거하는 push_back( )과 pop_back( )을 가지며, 첫 원소와 마지막 원소를 참조하는 front()와 back()을 가집니다. 또한 지정한 위치에 원소를 삽입할 수 있는 insert()를 가집니다. 반면 다른 시퀀스와 다르게 앞쪽에는 원소를 추가/제거할 수 없으며 뒤쪽에만 추가/제거할 수 있습니다.(다른 시퀀스 컨테이너는 앞쪽에도 추가/제거할 수 있습니다.)

그럼 예제를 통해 이해해 보도록 하겠습니다.

<vector의 push_back( )>

-> v라는 vector컨테이너를 만들고 끝부분에 10, 20, 30, 40, 50을 추가하고 출력해주는 예제입니다. 쉽죠? ㅎ

<vector의 size(), capacity(), max_size()

-> size() : 저장 원소의 개수

-> capacity() : 실제 할당된 메모리 공간

-> max_size() : 컨테이너에 담을 수 있는 최대 원소의 개수

그렇다면 결과는 어떻게 될까요??

@ 

 size()와 max_size()는 모든 컨테이너가 가지는 멤버 함수입니다. 하지만, capacity()는 유일하게 vector만이 가지는 멤버 함수입니다.

vector 컨테이너는 배열 기반 컨테이너이므로 연속한 메모리를 한 번에 할당하지만, 계속 원소가 추가될 수 있습니다. 원소가 추가될 때마다 메모리를 재할당하고 이전 원소를 모두 복사해야 한다면 너무나 비효율적일 것입니다. 따라서 재할당에 드는 성능 문제를 보완하고자 만들어지 개념이 capacity입니다. capacity()를 예제를 통해 좀 더 쉽게 이해해 보도록 하겠습니다.

<vector의 capacity()>

@ 

->결과를 보면 미리 저장할 메모리의 크기를 크게 하면 원소가 추가돼도 메모리의 크기가 변하지 않게 됩니다.

->또한 미리 메모리를 예약할 수 있는 reserve()를 제공합니다. ex) v.reserve(8) // 8만큰의 메모리 할당

<vector 생성자의 초기값 지정>

1. vector<int> v(5)  : 기본값 0으로 초기화된 size가 5인 컨테이너

2. vector<int> v(5,1) : 기본값 1로 초기화된 size가 5인 컨테이너

3. vector<int> v(v1) : v는 v2컨테이너의 복사본 컨테이너

<vector의 clear( )와 empty( )>

->v.clear() : v를 비운다.

->v.empty() : v가 비었는지 검사한다.

@

->결과를 보시면 size는 0이 되어도 메모리는 제거되지 않고 남아 있게 됩니다.

->swap방법을 이용하여 capacity를 0으로 만들수 있습니다.

<swap을 이용한 할당 메모리 제거>

@

-> 이렇게 swap을 이용하니 할당 메모리를 제거할 수 있내요~

vector 컨테이너의 남은 내용은 다음시간에 이어서 하도록 하겠습니다. ^^

<작성자 - CODER_CJH>

<참고자료 - 뇌를 자극하는 C++STL>