꿈 꾸는 누렁이

벡터

벡터가 무엇인지 한번 찾아보았다. 간단하게 정의하자면 순차 컨테이너에 속하는 동적 배열이다. C의 배열과 똑같이 행동한다.

그렇다면 C의 배열과 벡터의 차이점은 무엇일까? 

1. 타입에 상관없이 모든 타입에 대해서 일반적인 배열을 만들 수 있다.
=> int, double, char, int *, 객체 가릴 것 없이 모든 타입에 대해서 배열을 만들 수 있다는 이야기이다.
2. 배열의 크기 조절이 자동으로 이루어지며, 추가 및 삭제에 대한 인터페이스를 제공한다
=> 배열에 값을 추가하기 위해 새롭게 더 큰 메모리를 할당하고, 값을 복사하고 기존 메모리를 해체하고... 이러한 과정들을 알아서 해준다는 것이다! 개꿀!!!!ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그러나 2번과 같은 장점에 따른 단점 또한 존재한다.

C++의 벡터는 무조건 데이터를 선형적으로 만들려고 한다.( 그렇기에 이름도 순차 컨테이너. ) 중간에 끊긴다거나 하면 안된다는 소리이다. 

왼쪽과 같은 형태는 가능하지만, 오른쪽과 같은 형태는 안된다는 소리이다. 이러한 선형을 유지해야하는 특징 때문에 값을 추가할 때 단점이 발생한다.

메모리 공간이 충분하여 기존에 이어서 확장한 후 값을 그냥 더 추가할 경우에는 문제가 안된다.
아래의 그림처럼 말이야.

그런데 다음 그림과 같이 기존의 6개 메모리 뒤에 다른 관련없는 값이 이미 할당되어 기존의 6개 메모리 뒤에 연이어 추가 확장이 불가능한 경우는 문제가 발생한다.

이러한 경우에는 

이렇게 복사, 확장, 추가, 소멸 등의 여러 작업들이 필요하니 속도가 느려지는 단점이 있다.

설명은 이 정도로 정리하도록 하고, 매우 간단한 코드를 기록해보자.

7번 라인에서 볼 수 있듯이 템플릿 문법을 활용하여 사용한다. 반복자를 활용하지 않은 가장 기본 기본 기본적인 벡터 예제이다. 실행 결과는 매우 뻔하기 때문에 생략~

9번 라인에서 처럼 .size() 함수를 통해 벡터가 정의된 길이를 확인할 수 있다.

다음 vector 에서 제공하는 push_back 함수를 사용한 예이다. push_back 함수를 사용하면 벡터 열에 손쉽게 데이터를 추가할 수 있다.

오늘은 컨테이너, 이터레이터, 알고리즘이란 무엇이며, 무엇이 있는지 학습한 결과를 기록한다.

Container

컨테이너는 뜻 그대로 그릇, 무언가 담을 수 있는 역할을 한다. 즉, 자료 및 값을 저장하는 역할을 한다. 이 그릇의 모양이나 크기에 따라 담기를 권장되는 내용물이 다르고 취급 방법이 다르다.(컵이라는 그릇에 라면을 담을 수는 있지만 효율적이지 못한 것처럼.)

먼저, 컨테이너에는 순차 컨테이너, 연관 컨테이너, 컨테이너 어댑터 등이 있다. 

이게 무슨 소리인가? 

순차 컨테이너 : 뭔가 자료들이 순차적으로 들어가는거..?
연관 컨테이너 : 연관되어서 들어가는거..? 쌍으로 연관되어서 들어가는 것인가?
컨테이너 어댑터 : 어댑터란 다른 전기나 기계 장치를 서로 연결해서 작동할 수 있도록 만들어 주는 결합 도구 라는 정의가 있는 것으로 보아, 컨테이너와 컨테이너를 변환할 수 있는 그런게 아닐까?

나는 리얼로 위와 같이 생각했다. 내가 조사해 본 컨테이너들은 다음과 같다.

순차 컨테이너 

말 그대로 순차적으로 자료를 저장한다. 내 예측이 맞았다! 순차 컨테이너에서는 자료의 추가가 빠르지만 탐색할 때에는 시간이 많이 걸린다. 왜냐하면 순차적으로 접근하기 때문에!

이러한 순차 컨테이너에는 vector, deque, list 가 있다. 그렇게 벡터, 벡터했던게 바로 여기서 나오는 개념이었구나~

1. Vector : 동적 배열 처럼 동작하며, 자료는 뒤 쪽에서 추가된다.
2. Deque : 벡터와 유사하지만 앞에서도 자료들이 추가될 수 있다.
3. List : 벡터와 유사하지만 중간에서 자료를 추가하는 연산이 효율적이다.

연관 컨테이너

다음은 연관 컨테이너이다. 연관 컨테이너는 조사해 본 결과 사전과 같은 구조로 자료를 저장한다고 한다. 즉, 키와 값의 형태로 데이터가 저장되고, 자료들은 정렬되어 있으며 이러한 정렬 때문에 자료 추가에는 시간이 걸리지만 탐색은 키를 통하여 한 번에 뽑아내니 빠르다. 

이러한 연관 컨테이너에는 Set, Map, MultiSet, MultiMap 등이 있다

1. set : 집합이라고 하며, 중복이 없는 자료들이 정렬되어 저장된다.
2. map : 맵이라고 하며, key - value 형태로 저장된다.
3. multiset : 다중 집합이라고 하며, 집합과 유사하지만 자료의 중복을 허용한다.
4. multimap : 다중 맵이라고 하며, 맵과 유사하지만 키가 중복될 수 있다.

컨테이너 어댑터

드디어 컨테이너 어댑터이다!

컨테이너 어댑터는 기존 컨테이너의 인터페이시를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미한다고 한다. 이게 무슨 말일까 싶어서 좀 더 확인해보았는데

컨테이너 어댑터에는 Stack이 있다. 이를 예로 들자면, 기본 컨테이너인 벡터는 vector 클래스를 사용하는데 이 클래스의 인터페이스를 제한하고(벡터의 여러 기능들을 제한하고) 특정 형태(스택에 관련된 연산)의 동작 만을 수행하도록 한다.

그러니까 한 마디로 내가 어떤 자료구조를 구현할 것 인데 그냥 밑 바닥부터 구현하기 힘들고 귀찮은데 마침 기가 막히고 검증된 기존의 컨테이너가 있으니 이를 활용하여 확장 및 축소 등의 적용(Adapt)을 하는 것이라고 보면 될 것 같다. 그런데 뭔가 계속 제한한다고 하는데 이는 기존의 컨테이너에서 필요없는 부분은 사용하지 못하도록 하는 의미의 제한인 것 같다.

아무튼, 이러한 컨테이너 어댑터에는 Stack, Queue, Priority queue이 제공된다.

Iterator

이제는 반복자(Iterator)의 개념이다.

이 반복자는 각 컨테이너의 자료구조에 맞는 액세스를 할 수 있도록 도와준다. 예를 들어 순회를 한다거나, 원하는 값이 있는 메모리에 접근 가능하도록. 검증되었기 때문에 안심하고 사용해도 된다.

일종의 포인터와 비슷한 객체이다. 기존의 자료구조에서 보면 링크드 리스트에서만 보더라도 노드를 순회하기 위해서는 포인터의 값을 증가 혹은 감소시키고 여러 검사를 하는 등 작업을 했는데 반복자가 이를 대신해준다고 보면 된다. 

알고리즘마다 각기 다른 방식으로 컨테이너 요소들에 접근하기 때문에 반복자에도 여러 종류들이 존재한다. 그렇기 때문에 컨테이너를 사용한다면 꼭 반복자를 사용해야 한다.

반복자에는 몇 가지 예를 들자면 input iterator, output iterator, forward iterator, bidirectional iterator, random access iterator 등이 있다.

Algorithm

알고리즘은 문제 해결하기 위해서 그 절차나 방법의 공식화를 의미한다.

탐색, 정렬, 반전, 삭제, 변환 등이 있다.

위와 같이 3가지 요소로 구성된 것이 C++ STL이라는 것을 학습했고, 대충 개념을 잡게 되었다.

지난 포스팅 때, 재귀는 믿음이 졸라 중요하다고 했다. 이번에도 마찬가지다.

그 전에 재귀를 공부할 때, 써야하는 경우에 대한 추가적인 기록이 필요할 것 같아서 먼저 기록한다.

재귀가 필요한 경우

재귀가 필요한 경우는 다음과 같다.

탈출 조건이 명확하고, 같은 작업이 계속해서 반복되는 경우.

피보나찌 수열에서는 n-2항과 n-1 항이 더해지는 부분이 반복된다.

Fibonacci(5) 이면 Fibonacci(4) + Fibonacci(3) 인데 Fibonacci(4)에도 Fibonacci(3)에도 n-2항과 n-1항이 더해지는 부분이 필요하기 때문에 반복이 되고, 이를 재귀로 구현했던 것이다.

이번 포스팅에서 구현해 볼 이진 탐색에서 또한 마찬가지다. 

가운데 값을 구한 후 비교 -> 범위 재설정 

이 작업이 반복되기 때문이다. 탈출 조건의 명확성은 말할 것도 없고 말이다.

이진 탐색에서도 믿음이 필요한가?

물론이다. 필요하다. 위에서 제시한 재귀가 필요한 경우와 믿음이 존재한다면 재귀 함수를 마음 놓고 신경도 안 쓰고 사용해도 된다.

재귀란 무엇인가?

피보나찌 수열 구하기이다. 재귀로 구해볼 것이다. 재귀는 매우 특이한 방법이 아닐 수 없다.

A라는 함수가 있을 때, A를 열심히 실행하는 도중에! 그것도 A가 미처 다 끝나지도 않은 채로 다시 A를 실행한다. 

이렇게 되면 와 진짜 너무 복잡한데, 또 두 번째 실행된 A안에서 또 A가 호출하면 와 진짜 머리 터진다.

윤성우 선생님? 강사님? 교수님? 의 자료 구조에서 공부한 파트를 정리하게 되었다.

그냥 재귀를 하면 심심하니까 피보나찌 수열을 통해서 재귀 함수를 작성해보았다. 복잡할 수 있으므로 시간의 흐름에 따라 스텝을 밟을 것이다.

피보나찌 수열의 재귀적 구현

먼저, 다음은 피보나찌 수열이다.

0,   1,   1,   2,   3,   5,   8,   13,   ...

0번째 항과 1번째 항은 무조건, 지구가 멸망하지 않는 이상 0과 1로 각각 주어진다.(멸망하면 수학을 풀 필요가 없다) 그렇다면 2번째 항부터는 어떻구 구하는가?

• 2번째 항을 구하는 방법 : 0번째 항의 값과 1번째 항의 값을 더한다.
• 3번째 항을 구하는 방법 : 1번째 항의 값과 2번째 항의 값을 더한다.
• 4번째 항을 구하는 방법 : 2번째 항의 값과 3번째 항의 값을 더한다. (ㄱ)
• n번째 항을 구하는 방법 : n-2 번째 항의 값과 n-1 번째 항의 값을 더한다. ( 일반화 ) (ㄴ)

일단, (ㄱ) 까지의 상황을 코드로 정리해보겠다.

그렇다. 무식하다. 근데 이게 좀 쩌는 것이 무어냐면 ㅋㅋ,

• Fibonacci(4); 의 결과 : 3
• Fibonacci(3); 의 결과 : 2 
• Fibonacci(2); 의 결과 : 1

함수의 결과가 중요하지 않다. Fibonacci 함수의 본질을 알려준다. Fibonacci 함수의 본질은 다음과 같다.

Fibonacci 함수에 원하는 항의 인덱스 값을 넣으면 해당 인덱스 항의 값을 구해줘요!

이게 진짜 개중요하다. 우리는 앞으로 만들 우리의 Fibonacci 함수를 믿어야 한다. 우리는 Fibonacci 함수의 인자로 원하는 항의 인덱스 값을 넣으면 해당 인덱스 항의 값을 내어준다는 사실을 믿어야한다. 믿음이다. 재귀 함수 루틴이 들어간다고 해서 이러한 사실이 부정인가? 아니다. 

위의 믿음을 가지고 특정 항을 생각해보자. 특정 항은 예를 들어 5번째 항의 값을 구한다고 생각하자.

Fibonacci(5) = Fibonacci(4) + Fibonacci(3);

재귀를 생각하지 말라. 믿음이 있어야한다.
Fibonacci(4)는 4번째 항의 값을 리턴할 것이라는 믿음.
Fibonacci(3)은 3번째 항의 값을 리턴할 것이라는 믿음.

이런 믿음을 바탕으로 (ㄴ)까지의 상황으로 아래와 같이 구현해보았다.

그렇다면, 실제로 어떻게 동작을 해보는지 재귀의 경우를 그려볼까?

피보나치 수열의 재귀적 구현의 동작 원리

그만 알아보자

이진 탐색을 구현해보았다.

이진 탐색에 대해 간단하게 기록하기 전에 이진 탐색의 전제 조건에 대해서 기록을 먼저 해보겠다.

이진 탐색의 전제 조건

• 이진 탐색은 오름차순이든 내림차순이든 관계없이 '정렬'이 되어있는 연속된 배열 자료구조에서 적용된다.

이러한 전제를 갖는 자료구조를 대상으로 탐색을 진행하는 것이 이진 탐색이다. 그렇다면 왜 이진 탐색은 저런 전제를 갖나?
그 해답은 이진 탐색의 정의에 있다.

이진 탐색이란?

타겟을 탐색할 때, 전체 자료구조의 (1)최대한 가운데 위치하는 값과 타겟을 (2)비교하여 탐색의 범위를 비교한 가운데 값을 기준으로 왼쪽과 오른쪽 중 하나로 탐색의 (3)범위를 좁히고 다시 좁혀진 범위에서 최대한 가운데 값을 다시 비교하고 탐색의 범위 결정을 반복하여 타겟을 탐색하는 알고리즘이다.

이진 탐색은 반복이 들어간다. (4)반복이 들어간다는 의미는 탈출 조건이 필요하다는 뜻이다.

이 탈출 조건은 매우 당연하고 자연스럽다.

허나, 이 이유를 알기 전에 범위를 잡는다는 개념을 알아야 한다. 범위를 잡는 것은 여러 케이스들이 있을테지만 선형(배열) 자료 구조에서의 범위를 잡는다는 행위에 대해서 적어보겠다.

탐색할 범위를 잡는다는 것은 시작 인덱스와 끝 인덱스를 잡는 것이다. 쉽게 말해서 시작과 끝을 잡아야한다. 배열에서 시작과 끝을 잡는다는 의미는 시작 인덱스 값과 끝 인덱스 값을 잡는다는 것이다.

자, 그러면 세 가지의 경우가 있다.

• 시작 인덱스 < 끝 인덱스
  : 정말 당연한 것이다. 탐색할 범위의 양 시작과 끝을 잡고 있다고 보면 된다.
• 시작 인덱스 == 끝 인덱스
  : 이런 경우가 나올 수 있을까? 나올 수 있다. 시작 인덱스이자 끝 인덱스에 위치한 값이 타겟인 경우다. 운이 안 좋은 가장 최악의 경우인 것이다. 어떻게 이렇게 제일 끝에 나올 수 있어? 재수 없단 말이지! 이런 뉘앙스의 최악의 경우를 뜻하고, 이런 경우까지 고려하여 알고리즘의 성능 평가를 시행한다 실제로.
• 시작 인덱스 > 끝 인덱스
  : 이런 경우가 가능할까? 알고리즘이고 말고를 떠나서 글자 자체만 보더라도 불가능하다. 고로, 탈출 조건이 된다. 이 경우는 해당 배열 자료구조에 타겟에 해당하는 값이 없기 때문에 발생하는 경우이다. 시작 인덱스와 끝 인덱스가 같은 바로 위의 경우에도 타겟이 검출되지 않으면 발생하는 경우이고, 이 경우에는 조건 제어를 통해 반복을 탈출해야한다. 왜냐고? 배열에 타겟이 없으니까!

자 그렇다면 구현하는데에 생각하는 순서를 좀 정리해본 것이 위 본문에서의 괄호 안의 숫자들이다.

• (1)최대한 가운데 위치하는 값(을 구한다)
• (2)비교
• (3)범위를 좁힌다(결정한다)
• (4) 탈출 조건

위 순서에 해당하는 부분들을 주석으로 표시해봤다.

C++ 문법을 공부하다보니, 매우 편리한 STL을 제공하길래 너무나도 유익해 보여서 공부해본다.

먼저, STL은 Standard Template Library의 약자이다. 해석하자면 템플릿을 기반으로 작성된 라이브러리의 모음인데 이것이 표준화 되어있다는 소리이다. 즉, 만국 공통이라는 것이다. 어느 곳에서든 공통으로 사용할 수 있다.

그렇다면 템플릿을 기반으로 작성된 라이브러리는 무슨 말일까?

C++나 JAVA 등의 다른 객체지향 언어들을 살펴보면 템플릿이라는 것이 존재한다. 뜻만 보면 모형자라는 뜻인데 이 모형자의 특징은 다음과 같다.

• 모형이 정해져있다.
• 여러 색을 채워넣을 수 있다.

모형이 정해져있는데 색은 내 마음대로 시시각각, 상황에 맞게 칠할 수 있는 것이다. 이를 프로그래밍 언어에 적용하여 템플릿의 특징을 생각해보았다.

• 수행될 기능이 정해져있다.
• 여러 자료형으로 채워넣을 수 있다.

덧셈이면 덧셈, 곱셈이면 곱셈 수행해야 할 기능은 딱! 정해져있는데 자료형은 내 마음대로 시시각각, 상황에 맞게 지정하여 사용할 수 있는 것이다.

아래의 예는 함수 템플릿을 이용하여 템플릿 함수를 실행하기 까지의 코드이다.

아래와 같이 클래스에 대해서도 적용을 해볼 수 있다.

바로 위의 코드에서 보듯 클래스가 정해져 있고(모형들이 정해져 있음), 자료형을 입맛대로 넣고 사용할 수 있다(색을 마음대로 넣을 수 있다) 이러한 C++의 문법을 활용하여 만들어진 검증된 라이브러리가 STL 이다.

STL에는 무엇이 있을까?

STL의 구성은 다음과 같다.

Container(컨테이너) + Iterator(반복자) + Algorithm(알고리즘)

먼저, 컨테이너는 자료를 저장하는 구조이다. 자료 구조라는 소리이다. vector, list, map, set queue, stack 등이 그 예이다.

다음으로, 반복자는 컨테이너에 저장된 요소들을 순차적으로 처리하기 위한 컴포넌트이다. 자료 구조 내에 접근할 수 있는 방법을 제시해주는 컴포넌트라고 보면 될 것 같다.

마지막으로, 알고리즘은 정렬, 탐색 등의 부 프로그램 모음이라고 보면 될 것 같다. 흔히 알고 있는 그 알고리즘 맞다.

이러한 구성의 STL을 왜 사용하는가?

STL의 장점

STL의 장점은 이미 나와있다. 두 말하면 잔소리이다.

편리하고, 범용적이고, 검증된 라이브러리이다. 특히 C++ 전용으로 만들어진 C++ Template Library 인데 표준이기까지 하다.
공부를 하지 않을 수가 없어서 공부한다.