개발일지

컨테이너 어댑터(Container Adapter)개요　앞서 살펴본 컨테이너들은 완전 바닥부터 직접 만들었다. 하지만 이미 존재하는 컨테이너를 기반으로 새로운 컨테이너를 만드는 작업, 즉, 래핑(wrapping)하여 새로운 인터페이스를 만드는 것이 더욱 효율적일 때가 있다. 이것이 바로 컨테이너 어댑터다. C++ 표준 라이브러리에서 제공하는 대표적인 컨테이너 어댑터를 간략하게 설명하고 구현하는 시간을 가져보자.std::stack 　스택(stack)은 데이터의 처리와 저장을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용하는 컨테이너다. 기능적인 측면에서 스택은 한쪽 끝에서만 데이터를 삽입하거나 삭제하는데, 이를 활용해 괄호를 검사하거나, 뒤로 가기 버튼, 컴파일러를 구현할 때 사용된..

std::deque개요　앞서 살펴본 자료구조들은 연속된 자료구조 거나, 연결된 자료구조였다. 하지만 std::deque(Double-ended queue)는 두 가지 방식이 섞여있는 형태며, 양방향 삽입/삭제가 모두 가능한 자료구조다. 따라서 deque는 배열과 리스트의 장점을 모두 가지고 있어, 둘의 단점을 보완할 수 있는 자료구조다. 여기서 queue는 추후에 다룰 자료구조이니, 이런 것이 있구나 정도만 짚고 넘어가자.구조　앞서 부분에서 deque의 구조가 조금 특이하다는 것을 알았다. 이를 가시적으로 확인하기 위해 다음 그림을 보자.  　위 그림은 deqeue의 전체 덱 자료구조를 나타내고 있다. Chunk는 여러 개의 메모리 청크 중 하나를 나타낸다. 각각의 청크는 연속된 메모리 블록으로 구성되..

std::forward_list개요　앞선 자료구조 포스트의 std::forward_list는 아주 기본적인 형태로 구현된 연결리스트다. 따라서 리스트 끝에 원소를 추가하거나, 역방향으로 이동하는 기초 기능 외에는 지원하지 않는다. 따라서 C++에서는 이러한 단점을 보완하기 위해 양방향 연결 리스트(doubly-linked list) std::list를 제공한다. 이를 사용하기 위해선 헤더파일을 임포트 해야 한다.구조　연속된 자료 구조와 연결된 자료구조 (2) with C++에서 그림을 하나 가져와보자.  　보면 알겠지만, 노드끼리 서로 연결되어 있기 때문에 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터, 해당 노드에 있는 데이터를 갖고 있다. 간략하게 형태를 코드로 파악하자면 다음과 같다...

자료구조를 공부하다 보면 메모리 청크라는 단어를 자주 듣게 된다. 본 카테고리의 두 글을 보더라도, 청크라는 용어가 나온다. 단순히 메모리 덩어리라고 생각하기엔 추상적인 느낌이 강해 본 포스팅을 통해 구체화해 보도록 하자. 먼저 메모리 청크는 동적으로 메모리를 할당할 때 사용되는 일정한 크기의 메모리 블록을 의미한다. 이때 청크는 요소들 간 포인터를 사용하지 않는다. 각 청크는 배열 형태로 데이터를 저장하는 포인터와 청크의 크기, 다음 청크를 가리키는 포인터를 갖고 있다. 여기서 포인터를 사용하지 않는다는 것은 메모리 청크는 일반적인 포인터를 사용하지 않고, 인덱스 또는 오프셋을 사용하여 요소들을 참조한다는 의미다. 예를 들어, int 형 배열 arr 에서 arr[0] 에 접근하려면, arr의 시작 주소..

std::forward_list개요　앞서 포스팅한 std::vector, std::array같은 연속된 자료 구조에서는 데이터를 임의로 추가하거나 삭제하는 작업이 매우 비효율적이다. vector 자료 구조에서 insert() 함수와 erase() 함수를 예로 들어보자. insert() 함수를 통해 데이터를 삽입하려 하면 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요하고, erase() 함수도 특정 위치의 원소를 삭제한 후, 뒤쪽의 원소들을 모두 앞으로 이동해야 한다. 따라서 연결 리스트와 같은 연결된 자료 구조가 필요한 것이다.　　기본적인 연결 리스트를 구성하기 위해서는 포인터가 필요하고, new와 delete 연산자를 이용하여 메모리를 할당하고 해제할 수 있어야 한다. C++에서는 기본..

std::vector 구현 　이제부터 vector를 간단하게 구현해 보겠다. 우리의 목적은 크기가 유동적으로 조절되는 배열을 만드는 것이고, 용량은 1.5배씩 늘리도록 하겠다. #include using namespace std;templateclass vector{ T* _data = nullptr; // 데이터의 주소값 int _size = 0; // 크기 int _capacity = 0; // 용량　먼저 벡터에 담을 데이터의 주솟값과, 크기, 용량 변수를 초기화해준다. public: vector() { } // 기본 생성자 ~vector() // 소멸자 { if (_data) // 소멸자가 실행될 때 벡터 내에 데이터가 존재하면 delete[] _data; // 할당 해제 }　기본 생성자를 만..

std::vector　지난 시간에 크기가 고정되는 배열 std::array에 대해 살펴보았다. 예고한 것처럼 C 스타일의 배열의 한계를 극복한 가변 크기 배열 std::vector에 대해 알아보자. 벡터는 Cpp reference에 다음과 같이 정의되어 있다.  　직역하자면 연속적으로 저장되는 가변 배열이라는 의미다. 즉, 연속된 자료구조이며 크기를 늘리거나 줄여 원소를 변경할 수 있는 배열이라고 생각하면 되겠다. 이러한 벡터를 사용하기 위해서는 vector 라이브러리를 받아와서 다음과 같은 형태로 사용하면 된다. #include #include using namespace std;int main(){ vector v = { 1,2,3,4,5 }; // 크기가 5인 int형 가변 배열 vect..

array ary2"

연결된 자료 구조　앞선 시간에서 선형 자료 구조 중 연속된 자료 구조를 알아보았다. 이번 시간에는 여러 개의 메모리 청크인 노드(Node)에 데이터를 저장하는 연결된(Linked) 자료 구조를 연결된 자료 구조의 대표격인 연결 리스트를 통해 알아보자. 노드(Node): 연결 지점 　연결 리스트(Linked list)란 각각의 노드가 저장할 데이터와 다음 노드를 가리키는 포인터를 갖고 있는 자료 구조를 의미한다. 이때 노드가 한 쪽 방향으로만 탐색이 가능한 것을 단일(Singly) 연결 리스트라고 하고, 앞 뒤 방향 모두 탐색이 가능한 것을 양방향(Doubly) 연결 리스트라고 한다. 이러한 연결 리스트를 그림으로 표현하면 다음과 같다. 　이러한 개념에 착안하여 한 번 코드로 연결 리스트를 구현해보겠다. ..

시간 복잡도　데이터를 처리하기에 앞서 데이터를 어떻게, 어떤 형식으로 저장할 건지에 대한 자료 구조를 선택하는 것은 중요한 일이다. 이러한 선택을 하는데 있어 적합한 지표로는 알고리즘 복잡도인  시간 복잡도(Time complexity)가 있다. 이때 시간 복잡도란 특정 작업를 수행하는 데 걸리는 시간을 데이터 크기에 대한 수식으로 표현하는 방식이다.  　시간 복잡도는 데이터 크기가 변경되면 연산 시간이 어떻게 변하는지 시각적으로 파악할 수 있게 한다. 이때 표기식은 일반적으로 점근 표기법(asymptotic notation) 중 BIG-O 표기법(BIG-O notation)을 사용하는데, 이는 함수의 증감 추세를 비교하여 알고리즘의 효율성을 파악하는 표기법이다. 이 표기법의 큰 특징은 최악의 경우까지 ..