자료구조란?

자료구조, 왜 배워야할까? 

나는 비전공자로서 정보처리기사를 취득한 후, C언어와 파이썬을 공부하며 프로그래머스 배지를 따기 위해 문제를 풀어나갔다. 문제 합격률 ~70%까지는 어떻게든 노가다(반복적인 작업)로 문제를 풀 수 있었지만, 난이도 있는 문제를 풀어보니 어느 순간 한계에 부딪히기 시작했다. 도저히 문제를 풀 수가 없게 된 것이다. 그때 나는 자료구조와 알고리즘을 왜 공부해야 하는지 깨달았다.

 

개발자가 자료구조를 모른다는 것은 마치 공사장에서 삽을 들고 땅을 파고 있는데, 설계도 없이 무작정 땅을 파고 철근을 아무렇게나 심고 있는 것과 같다는 것을 알게 되었다.특히 개발자는 한정된 메모리 자원 내에서 메모리를 효율적으로 사용해야 하는 숙명이 있다. 자료구조를 모른 채 코딩을 먼저 시작하면 프로그램을 장기적인 관점에서 제대로 설계하지 못해 기술 부채(Tech-debt)를 지게 되거나, 매우 비효율적인 방식으로 개발하게 될 수 있다. 

 

이 글을 읽는 독자분들도 자료구조를 왜 공부해야하는지에 대한 개인적인 답을 내고 출발한다면, 좀 더 목표하는 지점까지 덜 괴롭게 공부하고 이해할 수 있을거라고 생각한다! 

그렇다면, 자료구조가 뭘까? 

생각해보면 컴퓨터가 하는 일은 두 가지로 아주 단순하다, 바로 데이터를 저장하고 연산하는 일이다 

자료구조란 이 데이터를 최소한의 메모리를 가지고 효율적으로 저장할 수있고 관리할 수 있는 방법이라고 할 수 있다. 

자료구조 분류 

자료구조는 선형 자료구조와 비선형 구조로 나눌 수가 있다.

 

선형은 일직선으로 나아가는 것을 의미하는데, 무언가를 할 때 한 번에 하나씩, 차례대로 진행되는 것을 생각하면 된다. 선형 자료구조라는 것은 데이터들이 한 줄로 차례대로 연결되어 있고, 데이터를 한 번에 하나씩 처리할 수 있다. 마치 카페에서 바리스타가 손님의 주문을 받고 차례대로 주문을 처리하는 것 처럼 한 번에 하나씩 처리하는 순서가 정해져 있다.

반면 비선형은 나무에서 나무 가지 줄기가 쭉 올라가다가 가지가 여러 개로 나뉘 듯이, 일직선이 아닌, 여러 갈래로 나눠질 수 있는 구조를 말한다. 비선형 자료구조는 데이터들이 여러 갈래로 퍼지거나 복잡하게 연결된 구조를 말하는데, 마치 네비게이션처럼 데이터를 찾을 때 한 줄로만 가는 게 아니라, 여러 갈림길로 나뉠 수 있는 자료구조이다. 

 

이제 각 자료구조에 대해 간단히 알아보도록 하자. 

배열(Array) 

배열은 청크(chunk) 형태로 연속적인 메모리가 할당되는 자료구조이다. 쉽게 말해, 덩어리로 메모리가 할당되는 구조라고 생각할 수 있다. 배열은 연속적인 메모리 공간을 차지하므로, a[0], a[1], a[2]처럼 각 요소의 첨자(index) 값이 1씩 증가한다. 이때 배열의 가장 큰 장점은 값을 수정하는 등 랜덤 접근(Random Access)이 가능하다는 점이다. 

랜덤 액세스 예시:

• 예를 들어, a[2] 에 3이라는 값이 있을 때, 5로 바꾸고 싶으면 자유롭게 값을 변경할 수 있다.
• 또한, a[2]로 이동하기 위해 굳이 a[0]부터 차례대로 갈 필요 없이, 바로 a[2]로 빠르게 접근할 수 있다.

랜덤 액세스가 가능하다는 큰 장점 뒤에는 단점도 있다. 배열에서는 요소의 값을 삭제할 때 불편한 일이 발생한다. 

만약 a[2] 의 값을 삭제하고 싶다고 하자. 배열에서는 어떤 요소의 값을 0으로 만들 수는 있을지언정 걍 삭제 ㄱㄱ 할 수가 없다. 그래서 a[2] 의 값을 삭제하고 싶으면 그 다음에 있는 원소들이 모두 한 킨씩 앞으로 이동해야 삭제가 완료된다. 이는 마치 식당에서 사람들이 대기 의자에 앉아있는데 대기 인원이 빠지면 대기자들이 의자를 한 칸씩 앞으로 땡겨서 앉는 것과 비슷하다. 

<요약>

• 장점: 빠른 랜덤 접근(Random Access)이 가능하다.
• 단점: 원소 하나를 삭제하려면 나머지 데이터를 이동시켜야 하므로 오버헤드가 증가한다.

연결리스트 (단일, 이중, 원형) 

배열은 덩어리 형태로 메모리가 연속적으로 할당되는 반면, 리스트는 각각의 원소가 랜덤한 메모리 주소에 따로따로 저장된다. 따라서 배열과 달리, 리스트에서는 처음부터 각 원소가 서로 연결되어 있지 않다.

 

연결 리스트에서는 각 원소를 노드(Node)라고 부르는데, 노드라는 단어는 여러 개의 밧줄을 매듭으로 묶어 하나의 줄로 길게 연결하는 것과 같은 뜻을 가지고 있다. tmi로 이 단어는 '매듭'을 의미하는 라틴어 'nodus'에서 유래했다고 한다.

 

컴퓨터 과학에서 노드(Node)는 각각의 데이터나 연결 지점을 의미하며, 각 노드는 다음 노드와 연결되어 데이터를 저장하거나 이동할 수 있게 된다. 그래서 노드가 있다면 디폴드 값이 각 원소를 매듭지어지기 전의 밧줄들처럼 서로 떨어져있다고 생각하면 나중에 자료구조의 형태를 기억하기가 수월할 것이다. 

 

배열에서 첫 번째 원소는 무조건 0번째인데 리스트는 어디가 첫 번째 원소인지 알 수가 없다.

그래서 리스트에서 첫 번째 원소에는 무조건 시작 값이라고 깃발을 달아주는 head가 필요하고 이 head에 첫번째 노드의 주소값이 저장된다. 이제 첫 번째 원소는 head가 있으니 구분할 수 있는데 그 다음 원소들은 구분할 수 없다. 

 

이 문제를 해결하기 위해 첫 번째 이후  원소들의 순서를 만들어주고 구분할 수 있도록, 각 노드에 이름표와 같은 포인터를 붙여서 각 노드가 다음 노드를 포인터로 가리킬 수 있게 하면 원소들을 서로 구분할 수 있게 된다. 여기서 데이터는 64bit 시스템에서 8byte를 차지하는데 거기에 포인터 8byte 가 더 얹어지니 각 노드당 16byte를 차지하게 된다. 

 

여기서 64bit 시스템에서 int형 데이터는 4byte인데 왜 12byte가 아니냐고 반문할 수도 있을 것이다. 

 

<반문하는 사람의 주장>

• 데이터(int): 4바이트
• 포인터(다음 노드의 주소): 8바이트

그런데 여기에 메모리 정렬(Padding)이라는 개념이 추가된다. 대부분의 컴퓨터 시스템에서는 효율적인 메모리 접근을 위해 데이터를 8바이트 단위로 정렬한다. 그래서 데이터의 크기가 8바이트보다 작아도, 추가적인 빈 공간(패딩)이 생겨서, 전체 크기가 16바이트가 되는 경우가 많다. 

 

<실제 메모리 할당>

• 데이터(int): 4바이트
• 포인터: 8바이트
• 패딩: 4바이트 (메모리 정렬 때문에 추가되는 공간)

여튼 메모리 공간이 산발적으로 위치해있는 특징으로 인해 연결 리스트는 랜덤 액세스가 불가능하다. 예를 들어 만약 4번째 노드를 접근하고 싶다면 첫 번째 원소부터 차례대로 포인터를 따라서 찾아가야 하기 때문이다.

 

이러한 단점도 있는 반면, 연결리스트는 데이터의 삭제와 삽입이 배열보다 용이하다. 노드가 서로 연결되어 있지 않기 때문에 3번쨰 노드를 삭제하고 싶으면 삭제해버리고 화살표 방향만 바꿔서 이어주듯이 이전 노드의 포인터를 삭제한 노드 다음 노드를  포인터로 가리키면 간단하게 원하는 노드를 삭제할 수 있다. 

<요약>

• 단점: 랜덤 액세스가 불가능하다. 
• 장점: 데이터 추가와 삭제가 간편하다.  

이제 연결 리스트의 세부 항목인 단일,이중,원형 리스트에 대해 간단히 알아보자. 

단일 연결 리스트는 앞으로 전진하는 리스트이다. 

단일 연결 리스트는 한 방향으로 이동하는 기차처럼 앞으로만 전진하니까 다음 값이 NULL이면 그 다음이 없다.

 

 

 

이중연결 리스트는 앞으로도 갈 수 있고, 뒤로도 갈 수 있다.

이중 연결 리스트는 각 노드가 다음 노드뿐만 아니라 이전 노드도 가리키기 때문에, 앞으로도 뒤로도 자유롭게 이동할 수 있다.

 

원형 리스트는 NULL이 없어서 빙글빙글 돈다. 

원형 리스트는 NULL이 존재하지 않는 형태이다. 맨 앞에 있는 연결 리스트와 맨 뒤에 있는 연결 리스트가 그림과 같이 연결이 되면 NULL을 만나지 않고 빙글빙글 돌기 때문이다. 

<사용 예시>

음악 플레이리스트 반복 기능: 

음악 재생 프로그램에서 노래가 끝나면 자동으로 다음 노래로 넘어가고, 마지막 노래가 끝나면 다시 첫 번째 노래로 돌아가는 기능을 구현할 수 있다. 

1. 각 노래를 원형 리스트의 노드에 넣는다. 
2. 현재 재생 중인 노래가 끝나면, 다음 노드(다음 노래)로 이동해 재생을 시작한다.
3. 마지막 노래가 끝나면, 다시 첫 번째 노드로 돌아가서 노래를 재생한다. 

스택 

스택은 마치 프링글스통에 감자가 차곡차곡 쌓여있고 맨 위에 있는 감자칩을 꺼내서 먹는것 처럼, 한쪽 방향에서 삽입과 삭제가 이루어지는 자료구조이다. 그래서 데이터가 접시를 쌓듯이 차곡차곡 쌓이게 되고 입구와 출구가 같으니까 데이터를 뺄 때는 가장 마지막에 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 형태를 가지고 있다.

 

<사용 예시>

웹 브라우저의 방문 기록 (뒤로 가기 기능): 

사용자가 새로운 웹 페이지를 방문할 때마다, 해당 페이지의 정보를 스택의 맨 앞에 새로운 노드로 추가한다. 각 노드에는 방문 기록이 순서대로 저장되고, 사용자는 방문 기록 뒤로 가기도 했다가, 앞으로 가기도 할 수 있다. 예를 들어 인터넷 접속해서 구글 -> 네이버-> 야후 순으로 접속했는데 뒤로가기를 눌렀을 때 야후->네이버->구글 순으로 돌아가기 기능을 구현할 수 있다. 

큐 

큐는 버스 정류장에서 버스를 타고 내리는 사람들을 상상하면 된다. 줄의 앞에 있는 사람이 먼저 버스에 타고, 새로운 사람이 줄의 뒤에 계속해서 서게 되는 것처럼,  긴 파이프 통 양 옆에 입구와 출구가 각각 있고 각 요소들이 먼저 온 순서대로 한줄서기를 하는 것과 같다. 큐에서는 데이터 삽입을 enque 라고 하고 데이터 삭제를 deque 라고 한다. 삽입은 뒤에서 이루어지고 삭제는 앞에서 이루어지는거니까 가장 먼저 들어온 데이터가 가장 먼저 삭제 되는 LIFO(Last In First Out) 구조가 된다. 

 

<사용 예시>

프린터에서 용지를 차례대로 출력 : 

• 문서가 대기열에 추가될 때마다, 그 문서를 리스트의 끝에 추가한다.
• 프린트 작업이 시작되면, 첫 번째 노드(문서)를 출력하고, 출력이 끝나면 그 노드를 제거한다.
• 다음 문서로 이동해 같은 작업을 반복한다. 

데크

데크는 스택과 큐가 합쳐진 형태이다. 양쪽 방향에서 삽입과 삭제가 모두 이루어진다.

<사용 예시>

웹 브라우저의 방문 기록 (앞으로 & 뒤로 가기 기능): 

스택에서는 뒤로 가기 기능만 가능했다면, 데크를 사용하면 앞으로 가기, 뒤로가기 모두 유연하게 구현할 수 있다. 예를 들어 인터넷 접속해서 구글 -> 네이버-> 야후 순으로 접속했는데 뒤로가기를 눌렀을 때 야후->네이버->구글 순으로 돌아갔다가 다시 구글 -> 네이버-> 야후 순으로 앞으로 갈 수 있다. 

 

단일 연결 리스트 vs 큐, 둘의 차이점이 뭐야? 

단일 연결 리스트와 큐는 모두 출구와 입구가 한 개인 상태에서 데이터의 순차적 처리에 중점을 둔다는 공통점이 있다. 

 이 둘의 차이점은 결정적으로 중간 노드의 처리 가능 유무에 있다.

 

이 둘의 차이점을 비유로 설명하자면, 단일 연결 리스트는 기차와 같다. 마치 기차처럼 한 방향으로만 연결되어 있으며, 각 칸(노드)을 자유롭게 추가하거나 제거할 수 있는 구조이다. 기차의 중간에서도 새로운 칸을 추가하거나 제거할 수 있다. 반면 큐는 줄 서기처럼 동작한다.줄을 서는 사람은 뒤에서만 추가되고, 앞에서만 빠져나갈 수 있다. 중간에서 끼어들거나 중간의 사람을 먼저 처리할 수는 없다.

 

차이점을 좀 더 쉽게 이해할 수 있도록 예를 들어 프린터 대기열을 각각 단일 연결 리스트와 큐로 구현하다고 해보자.

단일 연결 리스트는 각 노드가 다음 노드를 가리키는 포인터만을 가지고 있는 일방적인 구조이고 어느 위치에서든 데이터 삽입과 삭제가 가능하기 때문에 대기열의 중간에 있는 문서 출력을 취소하는 것이 가능할 것이다. 하지만 문서의 처음부터 끝까지 순차적으로 탐색해야 하므로, 대기열의 끝에 있는 문서에 접근하려면 전체 리스트를 탐색해야 하고, 큐처럼 구조적으로 끝에서 삽입하고 앞에서 삭제하는 것이 명확하지 않기 때문에, 데이터 접근 및 처리에 있어서 큐보다 비효율적일 수 있다.

 

큐는 포인터로 이루어진 구조가 아니고 문서가 추가되는 순서대로 출력되며, 삽입과 삭제가 고정된 위치에서 일어나므로 구조가 단순하다. 하지만 큐는 항상 앞에서 삭제하고 뒤에서 삽입해야 하므로, 대기열의 중간에 있는 문서를 우선 처리하거나 삭제할 수 없다. 

이중 연결 리스트 vs 덱 , 둘의 차이점이 뭐야 ? 

이중 연결 리스트와 덱은 출구와 입구가 양쪽에 있기 때문에 양방향 탐색이나 양쪽 끝에서 데이터 삽입/삭제가 필요한 상황에서 유용하게 사용된다. 이 둘의 차이점 역시 중간 노드의 처리 가능 유무에 있다. 

 

이중 연결 리스트는 마치 양방향 열차처럼, 앞뒤로 자유롭게 움직이며 중간의 승객도 쉽게 탑승/하차할 수 있는 열차라고 생각할 수 있다. 필요하면 어느 자리에서나 승객이 탑승하거나 하차할 수 있다. 반면, 덱은 양쪽에 문이 있는 대기열처럼, 앞쪽과 뒤쪽에서만 사람이 들어오거나 나갈 수 있다. 중간에 있는 사람을 끼워 넣거나 빼는 것이 불가능하며, 대기열의 양 끝에서만 조작이 가능하다.

 

예를 들어 게임에서의 턴 관리를 각각 이중 연결 리스트와 덱으로 구현하다고 가정해보자.

 

덱은 양쪽 끝에서 빠르게 작업을 처리해야 하는 상황에서 적합하다. 게임의 턴 진행이 주로 차례대로 이루어지고, 가끔 긴급 상황이 발생해 특정 플레이어를 앞쪽에 추가해야 한다면 덱이 더 효율적일 수 있지만 중간에 있는 특정 플레이어의 순서를 변경하려면, 앞쪽이나 뒤쪽에서 데이터를 꺼내고 삽입하는 방식으로 해결해야 한다. 

 

이중 연결 리스트는 게임에서 중간에 있는 플레이어의 순서를 자주 조정해야 하거나, 양방향으로 탐색해야 할 필요가 있는 상황에서 적합하다. 하지만 양쪽 끝에서 빠르게 플레이어의 순서를 바꿔줘야 하는 경우, 덱보다 처리 속도가 느리다. 또한 양쪽 포인터를 관리해야 하고, 삽입/삭제 과정에서 양방향 포인터를 수정해야 하므로 구현이 상대적으로 복잡하여 유지보수가 어려울 수 있다. 

 

따라서, 게임에서의 턴 관리에서 중간 조작과 유연한 탐색이 필요하다면 이중 연결 리스트, 순차적인 처리와 긴급한 상황에 대비한 구조가 필요하다면 덱을 사용하는 것이 적합하다.

트리

트리는 계층구조로 부모와 자식 관계로 이루어진다.

트리구조에서 1번 노드에서 6번으로 이동하고 싶다고 하면, 어떻게 이동할 수 있을까? 이동 경로는 보시다시피 한 곳 밖에 없다. 트리에서는 최상의 노드를 root 라고 부르게 되는데이 루트부터 시작해서 3번으로 갔다가 6번으로 올 수 있는이 길 말고는 다른 길은 절대로 존재하지 않게된다. 

 

<사용 예시>

 

컴퓨터의 디렉토리: 

컴퓨터의 파일 시스템은 트리 구조로 이루어져 있다. 최상위 폴더(디렉토리)가 루트 노드가 되고, 그 아래에 여러 하위 폴더와 파일들이 자식 노드로 연결된다. 폴더 안에 폴더가 있을 수 있고, 각 파일이나 폴더는 고유한 경로로 탐색된다. 

그래프

트리는 노드 경로 이동의 범위가 제한적인 반면, 그래프는 계층구조가 아니기 때문에 경로가 다양하고 유연하다. 그래프는 최상위계층이라는 개념이 없기 때문에 가능하다. 그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조인데 여기서 정점은 노드라고도 불리며, 그래프에서 데이터를 저장하는 점을 의미한다. 간선은 정점 사이를 연결하는 선이라고 생각할 수 있는데 간선은 거리나, 비용과 같은 값을 나타내는 가중치(weight) 값이 있을 수 있다. 

 

<사용 예시>

네비게이션:  그래프 구조를 활용하여 최단 경로를 찾거나, 네트워크 탐색을 하는 알고리즘으로 구현할 수 있다. 

 

1. 운전 목적지 

• 도시 A에서 도시 F까지 운전해 가려 한다. 이 도시들은 여러 도로로 연결되어 있으며, 각 도로에는 거리(가중치)가 있다. 우리의 목표는 A에서 F로 가는 최단 경로를 찾는 것이다. 

2. 그래프 구성

• 각 도시는 그래프의 정점(Vertex)이 된다. 
• 각 도로는 그래프의 간선(Edge)이 되며, 각 도로에는 거리라는 가중치가 존재한다. 

  A --- 5 --- B --- 3 --- E --- 4 --- F
   \         /  \        /
    2       6    7      8
     \     /      \    /
      C --- 2 --- D

 

• A, B, C, D, E, F는 도시를 나타내는 정점이다. 
• 간선은 도시 간 연결된 도로를 나타내며, 각 간선에는 거리를 나타내는 가중치가 있다.

3. 다익스트라 알고리즘 실행 과정

1. 시작:
   • 시작점 A에서 각 도시에 대한 거리 초기화:
     • A = 0, B = ∞, C = ∞, D = ∞, E = ∞, F = ∞
2. A에서 연결된 도시 탐색:
   • A에서 B까지는 5, A에서 C까지는 2이므로:
     • B = 5, C = 2
3. C에서 연결된 도시 탐색 (C는 현재 가장 가까운 도시):
   • C에서 D까지는 2, A에서 C까지는 이미 2이므로:
     • D = 2 + 2 = 4
4. D에서 연결된 도시 탐색 (D가 가장 가까움):
   • D에서 B까지는 6, D에서 E까지는 7:
     • B = min(5, 4 + 6) = 5, E = 4 + 7 = 11
5. B에서 연결된 도시 탐색:
   • B에서 E까지는 3:
     • E = min(11, 5 + 3) = 8
6. E에서 연결된 도시 탐색:
   • E에서 F까지는 4:
     • F = 8 + 4 = 12

7. 최단 경로

• A에서 F까지의 최단 경로는 A -> B -> E -> F이고, 총 거리는 12이다.