본 글의 저작권과 원문은 https://blog.naver.com/sweetie_rex 에 있습니다.
현재의 글은 업데이트가 되지 않음을 유의해서 읽어주세요.
최신 업데이트 된 글을 읽으시려면 아래의 링크를 확인해주세요.
자료구조 (Data Structure) 란?
'자료구조' 를 조금 이해하기 쉽게 써보면 '데이터의 구조' 가 돼.
즉, 데이터를 구조적으로 다루는 방법들 을 말하지.
분명히 이야기하지만, 자료구조는 프로그래밍의 핵심이나 본질은 아니야. 하지만 프로그래밍을 작성할 때, 자료구조에 대한 개념이 있는 상태로 작성하는 것과, 개념이 없는 상태로 작성하는 것은 큰 차이가 있어.
그렇기 때문에 이 장에서는 자료구조에 대해서 깊게 살펴보지는 않을 예정이고, 간단하게 자료구조가 어떤 것들이 있는지, 그리고 일상에서 어떻게 활용되는지 개괄적인 이야기만 해보려고 해. 코드 한 줄 없이, 개념만 이해하고 넘어가면 되니까 어렵진 않을거야.
자료구조는 앞으로 참된 소프트웨어 개발자가 되고 싶다면 반드시 거쳐야 하는 내용이야. 개발을 공부하다보면 향후 자료구조를 제대로 공부하는 날이 올텐데, 그 전에 간단히 맛보기만 해보자!
자료구조를 알아야 하는 이유?
자료구조를 공부하면 얻을 수 있는 몇가지 장점이 있어.
- 복잡한 문제를 보다 쉽게 해결할 수 있음
- 데이터를 체계적으로 다룰 수 있음
- 코드를 효율적으로 작성할 수 있음
- 성능을 높일 수 있음
자료구조를 공부함으로서 어떻게 이런 장점을 얻을 수 있는지는 하나씩 살펴보면서 알아가보자.
자주 이용되는 자료구조 형태들
- 선형 자료구조 (Linear Data Structure)
- Array (배열)
- List (리스트)
- Array List (배열 리스트)
- Linked List (연결 리스트)
- Stack (스택)
- Queue (큐)
- Deque (덱, 데크, 데큐, 디큐 등으로 발음)
- 비선형 자료구조 (Non-Linear Data Structure)
- Map (맵)
- Tree (트리)
- Binary tree (이진트리, 완전이진트리)
- Graph (그래프)
우리는 프로그래밍에서 대표적으로 사용되는 위 6가지 자료구조 형태에 대해서 알아보려고 해.
자료의 구조를 크게 분류해보면 선형(Linear) 과 비선형(Non-Linear) 으로 나뉘어.
그리고 선형(Linear) 자료구조에는 대표적으로 List, Stack, Queue 가 있고, 비선형(Non-Linear) 자료구조에는 대표적으로 Map, Tree, Graph 가 있어.
갑자기 일상적이지 않은 단어들을 써서 "무슨 소리야?" 했을 텐데, 이제부터 설명해볼게. 차근차근 이해해보자!
선형 자료구조 (Linear Data Structure)
선형 자료구조(Linear Data Structure) 라는 것은 데이터가 순차적으로 하나의 선(line) 처럼 나열된 형태의 자료 구조야.
1. Array (배열)
이전에 자료형 & 변수 영역에서 이야기 했던 그 배열이야. Array 는 프로그래밍 자료구조의 기본중에 기본이지! 데이터가 연속적으로 구성된 형태를 말한다고 했었어.
사실 Python 과 JavaScript 에서의 기본으로 제공해주는 Array 는 아래의 ArrayList 와 LinkedList 의 기능을 모두 갖추고 있어. 파이썬과 자바스크립트가 배우기 쉬운 언어라는 것에 이런 이유도 있어.
Java 에서는 Array 를 만들때부터 length 를 정확하게 지정해줘야 하지만, Python 과 JavaScript 는 아무렇게나 쓰고싶은대로 막 늘렸다가 줄였다가 하면서 사용할 수 있지.
장점: 순차적인 반복작업에 매우 빠름
단점: 배열의 크기(길이)가 고정되어 있음(Python 과 JavaScript 는 해당 없음), 배열의 중간에 데이터를 추가하거나, 삭제하는 경우 나머지 모든 배열의 원소(element)들이 자리(index)를 바꿔야하기 때문에, 중간에 데이터가 자주 변경될 수 있는 경우 비효율적임
2. List 자료구조
- Array List (배열 리스트)
데이터들이 배열처럼 순서대로 쭉 늘어선 형태의 자료구조야.
사실 배열과 매우 비슷하지만, 데이터의 길이(크기)가 정해져 있지 않아서 동적으로 늘렸다가 줄였다가 할 수 있다는 장점이 있어. 그냥 단순하게 말해서 "사이즈 변화가 자유로운 배열" 이야.
위에서 말한 것 처럼 Python 과 JavaScript 의 배열은 기본적으로 크기를 자유자재로 늘렸다, 줄였다 할 수 있기 때문에 ArrayList 라고도 볼 수 있어.
장점: 배열의 길이변화에 자유롭기 때문에 데이터의 추가/삭제가 용이함
단점: 데이터에 대한 접근속도가 배열보다는 느린 편
- Linked List (연결 리스트)
LinkedList 는 자료구조의 씨앗과도 같은 존재지. 왜냐하면 이 녀석은 향후 존재하는 모든 자료구조의 기초가 되는 녀석이거든. LinkedList 는 데이터들이 주소값(address) 으로 서로 연결되어 있는 형태야. 자료구조에서는 이러한 각각의 데이터를 Node(노드) 라고 표현하기도 하는데, 각 Node 들은 주소값 이라는 값으로 연결되어 있어. 이런 주소값을 가지는 변수를 Pointer(포인터) 라고도 해.
혹시 나중에 C 계열의 언어(C, C++ 등)를 배우게 된다면 이 내용에 대해 자세히 알 수 있을거야. 하지만 지금 단계에서는 너무 깊이 알려고 하지 않아도 돼. 왜냐면 우리는 지금 프로그래밍의 본질에 대해서만 알아가기에도 벅차기 때문이야!
여하튼 Linked List 는 다음 노드의 주소값을 참조하는 형태이기 때문에 Array List 와 비교했을 때, 어느 위치에든 새로운 데이터를 삽입/삭제하는 속도가 매우 빨라.
장점: ArrayList 에 비해 Node(데이터)의 삽입/삭제가 매우 빠름
단점: ArrayList 에 비해 데이터 검색 속도가 느린 편
3. Stack 자료구조
Stack 이라는 단어는 '쌓아 올린 형태' 를 뜻해. Stack 은 접시를 예로 들면 아주 쉬운데, 설거지가 끝난 접시를 바닥부터 차곡차곡 쌓고, 음식을 담을때 다시 꺼낸다고 생각해보자.
가장 첫번째로 놓은 접시가 가장 마지막에 꺼내지지?
가장 마지막에 놓은 접시가 가장 첫번째로 꺼내진다고도 말할 수 있지.
이것을 FILO(First in - Last out) 또는 LIFO(Last in - First out) 라고 해. 이게 바로 스택 자료구조의 특징이야. 후입선출(後入先出) 이라고도 해.
Stack 은 매우 자주 사용되는 구조인데, 우리가 쓰는 웹 브라우저의 history 를 볼 때도 Stack 자료구조가 사용 돼.
우리가 어떤 페이지든 접속할 때 마다 브라우저 history 에 페이지의 내용이 쌓이게되고, 뒤로가기 버튼을 클릭하면 마지막으로 본 페이지가 노출되지.
그리고 우리가 이전에 배웠던 재귀함수(Recursive Function) 또한 Stack 의 형태로 사용 되고, 프로그래밍의 Error 메시지를 유심히 봤다면 눈치 챘을수도 있는데, Error 메시지도 Stack 구조로 출력되고 있어. 그래서 이것을 'Stack trace' 라고 하지.
아래의 그림을 보면 이해가 될거야.
Stack 에는 Array 의 length 처럼 해당 스택을 담을 수 있는 최대 깊이(depth)가 있어. 해당 깊이를 초과해서 Stack 을 쌓아버리면 Stack Overflow 라는 문제가 발생해.
여담이지만, 위 그림은 전세계 개발자들의 지식의 보고, 지구상의 개발자라면 모르는 이가 없을 정도로 유명한 Stack Overflow 라는 커뮤니티의 로고인데, 앞으로 개발을 전문적으로 하다보면 하루에도 10번, 20번씩 들락날락 거리게 될거야.
개인적으로 저 로고를 너무너무 잘 만들었다고 생각하는데, 그 이유는 스택오버플로우를 찾을때면 내 머리의 생각이 한계에 도달해서 머리가 터질 지경의 상태이기 때문이지...
난 항상 Stack overflow 형/누나들에게 감사와 존경하는 마음을 가지며 살고 있어.
또 다른 여담으로, 개발자들은 보통 자신이 보유한 기술들을 '기술 스택(Tech Stack)' 이라고 표현 해.
예시)
"너의 기술 스택은 어떻게 되니?"
"난 Python, JavaScript, Java 를 주로 다루는 편이야."
"우리랑 기술 스택이 잘 맞는 것 같은데, 같이 개발해볼래?"
4. Queue 자료구조
Queue 는 한쪽에서는 삽입만, 다른 한쪽에서는 삭제만 이루어지는 자료구조야.
새치기가 불가능한 줄서기를 떠올리면 쉬워. 가장 먼저 진입한 데이터가 가장 먼저 나오는 구조야. (나중에 자료구조를 제대로 공부하면 알게되겠지만, 우선순위에 따라 새치기가 가능한 '우선순위 큐(힙, heap)' 라는 개념도 존재하긴 해)
이런 구조를 FIFO(First in - First out) 라고 하고, 선입선출(先入先出) 이라고도 해.
데이터를 입력된 순서대로 처리 해야 하는 경우, 또는 어떤 처리에 대해서 대기열이 필요한 경우 에 사용 돼.
비선형 자료구조 (Non-Linear Data Structure)
비선형 자료구조(Non-Linear Data Structure) 라는 것은 선형자료구조가 아닌 나머지 자료구조들을 말해. 하나의 데이터 뒤에 여러개의 데이터가 존재하거나, 데이터가 순차적으로 나열되지 않은 다양한 형태들이야.
1. Map 자료구조
이전에 이야기 했던 Map 과 동일한 내용이지. key-value pair(키-값 쌍) 으로 구성되어 있는 자료구조야. 우리가 파이썬에서 코딩했던 그 dictionary 가 바로 Map 자료구조를 가진 녀석이야.
Map 자료구조는 이전에 이야기했던 것 처럼, 프로그래밍의 모든 영역에서 거의 항상 사용 돼.
2. Tree 자료구조
Tree 자료구조에서 사용되는 용어
- Node
- 부모노드, 자식노드
- Root Node
- Sub tree
- Leaf Node
- Level
- 높이
- 차수
LinkedList 가 자료구조의 씨앗이라면, Tree 는 자료구조의 꽃이야. 모든 자료구조들 중에서 가장 흔하게 가장 자주 사용되는 자료구조가 아닐까 싶어. 우리의 일상에도 많이 녹아져있지.
사실 Tree 는 뒤에서 설명할 Graph 의 한 종류인데, 생긴게 나무의 모양처럼 생겨서 Tree 라는 이름이 붙었어.
하나의 뿌리(root node)에서 시작해서 점점 가지(branch) 와 잎(leaf)들이 붙으면서 넓어지는 형태지.
우리가 일상생활에서 평범하게 사용하고 있는 마인드맵, 또는 책의 목차(index)도 트리구조야.
Tree 자료구조는 데이터들을 동일한 특성으로 묶어서 분류하거나, 데이터들이 계층을 가지고 있을 때 사용되는 편이라, 검색이 상당히 빠르다는 특징을 가지고 있고, 아주 다양한 곳에 자주 사용되는 편이야.
주로 목차(index), 검색시스템, 파일시스템(폴더 구조), 데이터베이스, 의사결정 등 다양한 영역에서 사용되고 있어.
- Binary tree (이진 트리)
이진 트리(Binary tree)란, 트리구조 중에서도 하나의 node 가 가지고 있는 자식 node 의 갯수가 최대 2개인 트리구조를 말해. 2개로 뻗어나간다고 해서 '이진' 트리야.
이진트리의 종류는 여러가지가 있지만 가장 대표적인 이진트리는 포화이진트리(Perfect binary tree) 일거야.
포화이진트리는 child node 가 정확히 2개씩 존재하기 때문에 특정한 규칙성을 가져. 예를들면 트리의 각 레벨마다 child node 의 갯수가 2의 제곱 형태로 늘어나는 등이 있지. 수학적으로 풀어나가기에도 너무 좋은 구조라서 많이 사용 돼.
아래 그림이 포화이진트리의 형태야.
지금까지 설명한 Tree 외에도 엄청나게 다양한 Tree 들이 있어.
위의 모든 것들을 다 알 필요는 없으니 걱정하지 마. 여기에서는 그냥 'Tree 구조란 무엇을 말하는가?' 만 이해하고 넘어가면 돼!
3. Graph 자료구조
Graph 란, 우리들이 흔히 보는 막대그래프, 선그래프 등을 이야기하는게 아니라, 점(vertex)과 선(edge)으로 이루어진 도형 을 말해.
Map 이 지도를 말하는게 아니라 맵핑하는 형태를 말하는 것 처럼, Graph 는 도표가 아니라 도형의 형태 를 이야기하는거니 헷갈리지 말자.
Graph 는 쾨니히스베르크 다리 건너기 문제에서 유래했어. 쾨니히스베르크는 과거 독일의 도시였다가 2차세계대전 이후 러시아의 영토가 된 곳인데, 이 도시에는 유명한 2개의 섬과 7개의 다리가 있어.
문제는 이 7개의 다리를 딱 1번씩만 건너는 방법을 찾기(일명 한붓그리기) 였는데, 많은 수학자들이 이 문제에 도전했지만 불가능하다는 결론을 얻었어.
이때(1735년) '레온하르트 오일러(Leonhard Euler)' 라는 수학자가 이 문제를 추상화(Abstract) 하여 만든 것이 바로 Graph 야. 아래 그림을 보면 4개의 점(vertex)과 7개의 선(edge)으로 표시되어있지.
위 그림이 그래프 구조의 원형이라고 할 수 있어.
우리 실생활에서 가장 많이 쓰이는 그래프는 지하철/버스 노선도야.
이전에 '추상화(Abstract)' 를 설명할 때 나왔던 그림이지.
Graph 자료구조는 2가지로 나뉘는데, 방향그래프(Directed Graph) 와 무방향그래프(Undirected Graph) 로 나뉘어. (유향그래프/무향그래프 라고도 함)
Graph 의 점(vertex)을 노드(Node) 라고 하는데, 각 Node 들의 관계(선)가 방향이 있다면 방향그래프가 되고, 관계의 방향이 없다면 무방향그래프가 돼.
위의 Tree 자료구조는 사실 Graph 의 한 종류라고 했던 것 기억해줘.
그래프 자료구조는 보통 탐색 알고리즘이나 길찾기 알고리즘, 추천 알고리즘 등에 자주 사용되는 편이야.
탐색 알고리즘에는 대표적으로 DFS(Depth-First Search, 깊이우선탐색) 와 BFS(Breadth-First Search, 너비우선탐색) 라는 알고리즘이 존재하고, 길찾기 알고리즘에는 Dijkstra(다익스트라), A*(에이스타), D*(Dynamic A*) 알고리즘 등이 사용 돼. 이들은 우리가 사용하는 네이버지도, 카카오맵 등의 길찾기 기능이나 네비게이션에서 사용되는 알고리즘들이야.
이런 알고리즘의 영역은 자세히 들어가면 정말 매우 어렵기 때문에, 프로그래밍을 어느정도 익숙하게 다룬 다음에 따로 공부해보길 권장할게!
개발자로 취업하기를 희망한다면 알고리즘 공부를 일찍 하는게 좋을거야. 취업할 때 코딩테스트에 많이 등장하거든.
이상으로 프로그래밍 영역에서 가장 많이 사용되는 6가지 자료구조(Data Structure) 를 아주 간단히 알아봤어. 사실 자료구조는 제대로 이해하려면 그것만 따로 책 한권 분량이 나오는 아주 중요한 영역이야. 제대로 알기 위해서는 이 자료구조 각각의 구현방식과 주요 함수들까지 같이 설명해야하고 직접 구현을 해봐야겠지만, 일단은 이렇게 자료구조가 뭔지 대충만 알고있어도 초보 단계에서는 큰 도움이 될거야.
기회가 된다면 꼭 자료구조를 정식으로 공부해보길 바라. :-)
