자료구조(Data Structure) 입문을 위한 개요 정리

Data Structure

새로운 개념이나 분야를 공부해 나갈 때 처음으로 해야 할 일은 ‘무엇을 모르는지 아는 것’이다. 요즘같은 영상 시대에서 주로 사용하는 방법은 유튜브에 잘 정리된 개요 강의가 있는지 확인하는 것이다. 10분이라는 짧은 시간동안 자료구조가 무엇인지 ~ 어떤 자료구조들이 있고 왜 있는지를 알려주는 좋은 개요 강의를 찾아서 요약해 보려 한다.아래의 80%는 해당 유튜브 영상을 참조하여 정리한 것이다.

 

‘자료구조’란?

상황에 맞게 데이터를 읽고 불러오기 쉽게 정리할 수 있는 데이터의 구조

 

1. 배열 (Array)

다른 말로는 리스트나 벡터로 불린다. 메모리에 저장된 연속된 값. 배열에 저장되어 있는 값을 찾기 위해 우리는 “INDEX”를 알아야 한다.

배열이 메모리에 저장되는 방식

 

 

 

2. 문자열(STRING)

문자나 숫자, 특수문자 등으로 만들어진 배열.

문자열이 메모리에 저장되는 방식, 마지막 (zero)가 NULL을 뜻한다.

STRING의 메모리 저장 방식은 기본적으로 배열과 동일하지만 마지막 문자 뒤에 Null Caracter인 Binary 0를 넣는다. (-어디서 끝나는지 알기 위함.)

 

3. MATRIX

배열의 배열, 스프레드 시트의 표나 화면의 픽셀 처럼 2차원적으로 확장된 자료를 다루고 싶을 때 사용. 

 

[ARRAY, STRING, MATRIX]는 각각 하나의 숫자나 문자를 저장하는 구조.

하지만 연관있는 데이터를 연결시켜 저장하고 싶을 때가 있다. 예를들면 아이디와 비밀번호처럼 이때 활용할 수 있는 자료구조들이 아래와 같은 것들이다.

 

4. 구조체 Struct

단일 숫자가 아닌 여러 데이터를 한 번에 저장 가능한 복합 데이터로 된 변수

구조체는 이처럼 서로 연관있는 변수를 함께 저장할 때 쓰인다.

STRUCT로 된 배열을 만들 수 있다. 구조체 배열은 크기가 고정되고 확장이 불가능 하다. 이 특성 때문에 새로운 값을 중간에 넣기가 힘들다. (꽉 찼을 경우) 하지만 이런 STRUCT 구조를 활용해서 더 유연한 데이터 구조를 만들 수 있다. (=> NODE)

 

5. 노드(NODE)

NODE는 변수임과 동시에 포인터(메모리 주소를 가리키는 변수)이다.

많은 자료 구조의 기본인 노드는 변수하나와 포인터(들)을 가지고 있다.

이 NODE를 여러개 저장 할 수 있는 유연한 구조체가 바로 LINKED LIST이다.

 

6. LINKED LIST

여러개의 NODE를 저장하는 데이터 구조. 크기를 미리 지정해야 하는 Array와 달리 링크드리스트는 단순히 포인터를 이동시키는 것 만으로 상황에 따라서 크기를 늘리고 줄일 수 있다.

링크드리스트를 추상화해 보여주는 사진, 위는 연결되어 Circular한 Linked List이다.

위처럼 포인터의 재 연결만으로 링크드 리스트는 쉽게 데이터를 추가, 삭제 할 수 있다.

여러개의 NODE를 저장하는 데이터 구조. 크기를 미리 지정해야 하는 Array와 달리 링크드리스트는 단순히 포인터를 이동시키는 것 만으로 상황에 따라서 크기를 늘리고 줄일 수 있다.

LINKED LIST가 저장되는 방식

위의 메모리 구조는 LINKED LIST의 유연함을 나타냈는데, 포인터의 이동을 보면 1008- 1002 - 1000으로 이동하며 “CIRCULAR” LINKED LIST임을 알 수 있다.

다음 포인터의 값을 0(NULL)으로 해주면 연결 리스트를 끝낼 수 있다.

 유연성(단순히 포인터의 이동으로 추가, 삭제가 쉬운)을 가졌기 때문에 순서를 바꾸거나, Trim(쪼개기), Reverse(뒤집기)를 쉽게 할 수 있고 이로인해 더 복잡한 자료 구조들이 이 LINKED LIST를 활용해서 구축되었다. 가장 보편적인 것이 "Queue와 Stack"이다.

 

7. 큐(Queue) : First In First Out

 먼저 온 사람이 먼저 나간다. FIFO 구조를 가진 Queue는 링크드리스트로 만들어진다. 나가는 것을 어떻게 구현할까? 단순히 앞의 제일 앞의 포인터를 한칸 뒤로 이동 시키면 된다.  

Queue를 추상화 해서 설명하는 그림

위의 그림에서 Dequeue(먼저 온 사람인 HANK를 뺀다면)하기 위해서는 아래처럼 포인터를 하나 옮겨주면 된다.

Dequeue 후의 모습

위의 그림에서 새로운 사람이 추가된다면? INQUEUE

Inqueue후의 모습

 

8. 스택 : Last In First Out (LIFO)

마지막으로 들어온 사람이 먼저 나가려면 어떤 구조를 만들어야 할까? 이 자료구조가 LIFO, STACK이다.

Stack에서 나가는 것은 POP , 들어오는 것은 PUSH로 부른다.

 

9. 트리(Tree)

Node에서 포인터를 두개 갖기만 한다면 Tree 구조를 만들 수 있다.

트리 노드의 구조체

값이 저장되어 있는 트리를 추상화한 그림

 트리 구조에서 제일 위의 Node는 루트(Root)라고 하며, 제일 아래 Node는 리프(Leaf)라 하며, 한 노드(A)의 밑의 노드들은(A밑) 자식 노드(Children Node)라고 한다. 반대의 경우는 부모 노드(Parent Node)라고 한다.

한 노드의 자식 노드의 개수는 제한이 없지만, 위의 그림 예시처럼 한 노드의 자식이 두개까지인 것을 Binary Tree라고 한다.

트리의 하나의 특징은 뿌리에서 잎까지 한가지 경로만 존재 한다는 것이다.

 

 그럼 (규칙적인 트리와 달리)서로 제멋대로 연결되어 있는 자료들은 어떻게 표현할까? 그걸 표현하기 위한 구조가 아래의 “그래프(Graph)”구조이다.

 

10. 그래프(Graph)

 

그래프를 추상화한 모습

 위에서 설명한 것 처럼 제멋대로 연결되어 있는(리프, 루트, 부모, 자식의 개념이 없는) 자료 구조를 그래프로 표현 할 수 있다.

  이는 단순히 하나의 노드에서 여러개의 포인터를 포함시킴으로써 만들 수 있다. 

 

 

위의 구조 뿐 아니라 다양한 변형된 구조(Heap, Red Black Tree등)이 있으나 영상에선 다루지 않았다. 하지만 Heap은 기본 구조중 하나이니 같이 정리한다.

 

11. Heap (힙) : 우선순위 큐 Queue

Max Heap예시 위로갈수록 커진다.

 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리(Complete Binary Tree)를 기본으로 한 자료 구조(Tree Based-Structure)

 Max Heap과 Min Heap이 있는데, 말 그대로 Max Heap은 부모 노드가 항상 자식 노드의 값보다 큰 특징을 같고 있으며  Min Heap은 반대의 특성을 갖는다.

 Insert와 Delete 는 Upheap, Downheap으로 부르며 다음에 구체적으로 정리하겠다.

 

 위의 내용으로 어느정도 전체적인 개요를 머릿속에 넣을 수 있었다. 자료 구조들을 직접 코딩해서 만들어야 할까? 아니다 이미 각 언어들에서 만들어놓은 구조들이 있는데 이게 그 유명한 C++의 STL(Standard Template Library) / Java의 Java Class Library등이다. 앞으로는 각각의 자료구조에 대해 구체적으로 공부하면서 내용을 정리 해야겠다.