들어가며

프로그래밍의 본질은 문제를 해결하는 것이며, 그 문제를 해결하는 수단으로 알고리즘적 사고와 프로그래밍 언어의 문법을 사용합니다. (코드없는 데이터구조와 알고리즘 p.26)

이 문장을 읽고 '나는 그동안 문제 해결 방법으로 프로그래밍 언어의 문법만 간신히 사용하고 있었구나...'라고 생각 했습니다. 그럼 알고리즘적 사고는 무엇일까, 궁금한 마음이 들었고 이에 대해 조금씩 알아보려고 합니다.

알고리즘이 무엇인지에 이해하기 위해서는 알고리즘과 상호 보완적 개념인 데이터 구조에 대해서 알아둘 필요가 있습니다. 오늘은 데이터 구조란 무엇인지 그리고 데이터 구조에는 어떤것들이 있는지 넓고 얕게 알아보겠습니다.

데이터 구조

데이터 구조란, 데이터를 구성하고 저장하는 방법을 설명하며, 데이터를 식별하는 방법을 제공하고, 데이터의 관계를 보여주는 개념입니다.

데이터 구조의 4가지 유형인 선형 데이터, 트리 데이터, 해시 데이터, 그래프에 대해서 알아보겠습니다.

1. 선형 데이터 구조

선형 데이터 구조는 데이터 구조를 구성하는 요소들이 서로 인접해 순차적인 방식으로 정렬되어있는 데이터 구조를 뜻합니다.

선형 데이터 구조를 갖는 배열, 리스트, 스택, 큐에 대해 알아봅시다.

1-1. 배열

배열은 데이터를 저장하고 구성하는 가장 기본적인 데이터 구조 중 하나입니다.
배열에 저장된 각각의 데이터를 요소(element)라고 하며, 0부터 번호(인덱스)를 매깁니다.
배열 내의 요소들은 순차적 또는 연속적으로 정렬되어있어 배열의 요소들을 임의의 순서로 읽을 수 있습니다.

1-2. 리스트

리스트는 배열의 유형 중 하나입니다.
배열은 데이터 요소를 메모리에 순차적으로 저장하지만, 리스트는 데이터 요소를 흩어진 상태로 메모리에 저장한다는 특징을 가지고 있습니다.
따라서, 메모리를 더 효과적으로 사용할 수 있습니다.
리스트의 연결 방향에 따라 단방향 연결 리스트, 양방향 연결 리스트, 순환형 연결 리스트로 구분할 수 있습니다.

(1) 단방향 연결 리스트

(2) 양방향 연결 리스트

(3) 순환 연결 리스트

1-3. 스택 (Stack)

스택은 추가된 요소를 사용 가능한 메모리의 가장 앞 주소에 배치하는 데이터 구조입니다.
스택에 요소를 추가하는 동작을 푸시(push)라고하며, 요소를 삭제하는 동작을 팝(pop)이라고 합니다.

1-4. 큐 (Queue)

큐는 각 요소에 우선순위를 부여하는 데이터 구조입니다.
큐에 요소를 추가하는 동작을 인큐(enqueue)라고하며, 요소를 삭제하는 동작을 데큐(dequeue)라고 합니다.

1-5. 우선순위 큐 (Priority Queue)

우선순위 큐는 큐의 개념을 확장한 것으로, 키와 값을 사용해 큐의 요소를 정렬하는 데이터 구조입니다.
우선순위가 높은 요소가 큐에서 먼저 제거됩니다. 만약, 우선순위가 같다면 큐에 먼저 추가된 요소부터 삭제됩니다.

2. 트리 데이터 구조

트리 데이터 구조는 데이터를 계층으로 정렬하는 데이터 구조입니다. 트리 데이터 구조는 루트 노드를 기준으로 구성되며 하위에 부모 노드와 자식 노드를 갖으며, 노드를 연결하는 선을 에지(edge)라고 합니다.

트리 데이터 구조를 갖는 이진 트리, AVL트리, RB트리, B트리, 힙에 대해서 알아봅시다.

2-1. 이진 트리

각 부모가 항상 2개의 자식 노드와 연결되어 있는 트리 구조를 갖습니다.
모든 노드는 키-값 구조로 이루어져 있고, 모든 노드의 키는 오른쪽 서브트리가 더 큽니다.

2-2. AVL(Adelson-Velsky and Landis)트리

불균형 이진 트리가 생길 수 있는데 이 문제를 해결하기 위해서는 트리의 균형을 조정하는 과정을 거쳐야 합니다.
AVL트리는 서브트리 2개 사이에서 높이 차이를 감지하면 트리회전이라는 균형 조정 과정을 수행하는 이진 트리입니다.
AVL트리의 시간 복잡도는 O(logn)입니다.
ex) 일부 데이터베이스 검색 시스템

2-3. RB트리

RB트리는 자체적으로 균형을 조정하다는 점에서 AVL트리와 비슷하지만, 트리회전수가 AVL보다 적어 효율적입니다.
RB트리의 시간 복잡도는 O(logn)입니다.
RB트리는 노드마다 빨강 또는 검정으로 해석되는 비트를 포함하는 특징을 가지고 습니다. 일반적으로 루트 노드는 검정이고, 빨강노드는 검정 노드를 자식 노드로 갖습니다.

2-4. B트리

B트리는 자체적으로 균형을 조정하다는 점에서 AVL트리와 비슷하지만, 부모 노드가 3개이상의 자식 노드를 가질 수 있다는 특징을 가지고 있습니다.
ex) 데이터 베이스 시스템 설계

2-5. 힙

값이 최대 혹은 최소인 노드에 빠르게 접근해야하는 응용프로그램에 적합한 트리기반 데이터 구조 입니다.
앞서 배운 우선순위 큐는 힙을 통해 구현할 수 있습니다.
최대힙은 루트 노드가 힙에서 가장 큰 값을 갖으며 부모노드는 자식노드와 같거나 큰 값을 갖습니다.
최소힙은 루트 노드가 힙에서 가장 작은 값을 갖으며, 부모노드가 자식노드와 같거나 작은 값을 갖습니다.

3. 해시 데이터 구조

해시 데이터 구조를 이해하기 위해서는 해시와 해시 함수에 대해서 알아야 합니다. 해시는 어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것을 뜻하며, 해시함수는 해시를 실행하려고 하나의 값을 다른 값으로 변환하는 상자를 뜻합니다.

해시 데이터 구조인 해시 테이블과 해시 테이블의 해시 충돌 문제를 해결하기 위한 체이닝방식에 대해 알아봅시다.

3-1. 해시 테이블

해시 테이블은 키와 값으로 구성된 검색 시스템입니다.
해시 테이블의 모든 키는 그에 대응하는 값을 가지고 있습니다. 그러므로 키를 알면 연결된 값을 즉시 찾을 수 있습니다.
해시 테이블의 시간 복잡도는 O(1)입니다.

그러나, 해시값과 배열의 크기로 인해 해시 충돌이 발생 할 수 있습니다. 이를 해결하기 위해 체이닝이라는 방식으로 해시 테이블을 구현할 수 있습니다.

3-2. 체이닝

체이닝은 요소를 단순 배열이 아닌 연결 리스트인 배열에 저장하는 방식으로 구현됩니다.
해시 함수가 여러 요소에 대해 똑같은 인덱스를 반환하면, 해시값과 해당 요소들을 함께 '연결'하여 해시 테이블의 같은 인덱스에 저장하므로 해시 충돌을 막을 수 있습니다.

4. 그래프

그래프는 노드 사이의 연결을 보여주는 데이터 구조입니다. 그래프는 루트 노드가 없는 트리같이 생겼으며, 부모 노드 또는 자식 노드로 식별 할 수 있는 노드를 찾을 수 없습니다. 그래프의 노드는 객체 혹은 정점이라고 하며 이를 연결하는 선을 에지(Edge)라고 합니다.

4-1. 유향 그래프 (directed graph)

방향성이 있는 에지를 가진 그래프를 뜻합니다.

4-2. 무향 그래프 (undirected graph)

방향성이 없는 에지를 가진 그래프를 뜻합니다.
무향 그래프는 에지에 방향성이 없으므로, 노드 양쪽으로 에지를 타고 이동할 수 있습니다.

4-3. 가중치 그래프 (weighted graph)

가중치를 갖는 에지를 가진 그래프를 뜻합니다.
에지가 방향성을 가지는지 여부에 따라 무향 가중치 그래프, 유향 가중치 그래프로 나눌 수 있습니다.
ex) 소셜 네트워크 서비스

참고) 관계형 데이터베이스 관리 시스템(RDBMS)와 그래프 데이터베이스 비교

관계형 데이터베이스는 행과 열로 구성된 테이블에 데이터를 저장하는 데이터베이스 입니다.

관계형 데이터베이스를 이용해 데이터를 검색하기 위해서는 여러 데이터베이스를 연결해서 검색하는 조인(join)을 사용하는데 테이블 사이의 조인이 너무 많으면 검색 속도가 느려집니다. 그래프 데이터베이스는 테이블이 아닌 데이터 중심으로 데이터가 직접 연결되므로 관계형 데이터베이스에 비해 검색 속도가 상대적으로 빠릅니다.

아래는 SNS의 친구 관계를 관계형 데이터베이스와 그래프 데이터베이스로 나타내 비교한 것입니다.

참고) 트리 데이터 구조와 그래프는 무엇이 다른가요?

트리 데이터는 루트 노드로 시작해 부모 노드와 자식 노드로 이루어져 있습니다. 그래프는 루트 노드가 없는 트리처럼 생겼으며, 부모 노드 혹은 자식 노드로 식별할 수 있는 노드가 없습니다.

마치며

데이터 구조를 한번 훑어보니 머릿속에 흝어져 있던 지식들이 조금은 명확해진것 같습니다. 다음 글에서는 오늘 배운 데이터 구조에 대한 지식을 기반으로 알고리즘에 대해 얉고 넓게 알아보도록 하겠습니다 :-)

참고

코드 없는 알고리즘과 데이터 구조(암스트롱 수베로 지음/류태호 옮김/동양북스) 책을 읽고 일부 내용을 보강하여 작성한 글입니다.
데이터 구조와 알고리즘에 대해 가볍게 맛보고자 하신다면 위 책을 추천합니다!
본문에 있는 그림은 모두 책을 보고 제가 직접 그린것이라 노드나 데이터를 표현한 그림의 크기가 일정치 않을 수 있으나, 이것이 데이터 메모리의 크기라던지의 특정한 의미를 갖는것은 아닙니다.

데이터 구조 훑어보기