[Data Structure] C++로 구현해보는 자료구조 - 들어가며

C++로 구현해보는 자료구조 - 들어가며

자료구조를 정리하는 마음으로 본 글을 포스팅하려고 한다.
순서는 다음과 같이 이뤄진다.

- 선형 자료구조

• 배열(Array)

• 정렬 정적 배열(Sorted Static Array)
• 비정렬 동적 배열(Unsorted Dynamic Array)
• 정렬 동적 배열(Sorted Dynamic Array)

• 연결구조(Linked List)

• 단일 연결구조(Single Linked List)
• 이중 연결구조(Double Linked List)
• 선형 연결구조(Circular Linked List)

• 스택(Stack)

• 배열 버전
• 연결구조 버전

• 큐(Queue)

• 배열 버전 / 환형 큐(Circular Queue)
• 연결 구조 버전

• 데크(Deque)

- 비선형 자료구조

• 트리(Tree)

• 이진 탐색 트리(Binary Search Tree)

• 그래프(Graph)

• 유향 그래프(Directed Graph)
• 무향 그래프(Undirected Graph)

순서는 후에 달라질 수 있다.
중간중간 더 많은 지식들을 접하면 추가가 될 수도 있다.
일단 기본적으로는 이 순서를 따른다.
C++98과 C++14로 각각 구현할 예정이다.
C언어도 고려해보았으나, 귀찮을 것 같아 포기.

본격적으로 시작 전, 기본적으로 알아야할 사항들을 짚고 넘어가고자 한다.

자료구조와 알고리즘

우리는 어떤 복잡하고 어려운 계산들을 빠르고 정확하게 알아내기 위해 컴퓨터를 사용한다. 즉, 일정한 순서가 있는 프로그램을 작성한 후, 거기에 데이터를 입력하여 기대한 결과들을 얻게 된다. 문제는 현실에 있는 데이터를 각 언어에 있는 타입으로 표현되기엔 너무 복잡하다는 사실이었다. 그래서 컴퓨터에 데이터를 보다 효율적으로, 쉽게 다룰 수 있는 '저장하는 방법'을 고안했는데, 이것이 자료구조(data structure)이다. 그리고 '어떤 문제를 해결 하는 과정'을 알고리즘(algorithm)이라고 한다. 정리하면, 프로그램은 크게 자료구조와 알고리즘으로 나눌 수 있다. 자료구조와 알고리즘은 긴밀한 관계가 있는데 자료구조가 선택되면 적용할 알고리즘이 정해지거나, 혹은 반대로 알고리즘을 위해 자료구조가 고안되기도 한다. 자료구조의 종류는 상술된 것 말고도 여러가지이며,(표준 라이브러리에 있는 클래스 혹은 여러분들이 만든 클래스도 모두 자료구조이다.)위의 것들은 기본적인 것들만 나열한 것이다.

추상 자료형

추상 자료형(ADT: abstract data type)이란, 자료구조의 구체적인 구현은 숨기고, 자료구조의 자료와 연산만 나열한 것을 얘기한다. 즉, 인터페이스만 얘기하는 것이다. 예를 들어보자. 모니터를 구매했다고 가정했을 때, 동봉된 설명서에는 모니터에 달려있는 버튼들을 사용하는 방법들이 있을 것이다. 전원, 메뉴, 밝기 조절 버튼 등. 우리는 이러한 버튼들이 있고, 각 버튼들이 어떤 동작을 하는 데에만 관심이 있지, 각 버튼들을 눌렀을 때 모니터 내부에 어떤 전기적 신호가 흐르고, 제어되고 하는 구현되는 방법에는 관심이 없다. 여기에서 나온 설명서 역할이 추상 자료형이다.

성능 측정

자료구조를 어떻게 구현했느냐에 따라 자료구조의 성능이 좌지우지되곤 한다. 여기서 성능이란, 공간(메모리)은 어느정도 차지하고, 시간은 얼마나 걸리는지를 얘기한다. 전문 용어로 정리하면 공간 복잡도(space complexity), 시간 복잡도(time complexity)라고 한다. 이 성능을 측정하는 방법을 정확히 숙지하고 있어야 효율적인 자료구조를 구성할 수 있을 것이다. 현대에는 다룰 수 있는 메모리 용량이 매우 커졌기 때문에, 시간 복잡도를 많이 신경쓴다. 실제 시간을 측정하는 것은 하드웨어 사양에 따라 많이 달라지므로, 연산의 빈도 수를 이용해 대략적으로 추정하게 된다. 여기엔 복잡도를 표기하는 방법중 빅오 표기법(big O notation)를 이용하게 된다. 빅오 표기법에 대한 내용은 링크로 대신한다. 시간에 대한 분류는 다음과 같다.

실행 빈도 수	표기
1	$O(1)$ : 상수형
$logn$	$O(logn)$ : 로그형
$n$	$O(n)$ : 선형
$nlogn$	$O(nlogn)$ : 선형 로그형
$n^2$	$O(n^2)$ : 2차형
$n^3$	$O(n^3)$ : 3차형
$2^n$	$O(2^n)$ : 지수형
$n!$	$O(n!)$ : 팩토리얼형

아래로 갈수록 시간이 오래 걸린다는 뜻이다. 선형만 되더라도 시간이 많이 느려진다. 예시를 보자.

int main()
{
    int count = 0;                  // 1
    for (int i = 0; i < 100; ++i)   // n + 1
    {
        ++count;                    // n
    }

    return 0;                       // 1
}

한 단계로 표시되는 구문은 기본적으로 같은 단위 시간이 걸린다고 가정한다. 다 더하면 $2n + 3$이지만 표기는 상위 차수만 기입하므로 이 알고리즘의 시간 복잡도는 $O(n)$이다.

다음 포스트에서는 배열에 대해서 알아보도록 하겠다.