개발일지

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

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

array ary2"

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

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