자료구조(Data Structure) 기초 정리

전반적인 자료구조/알고리즘에 대한 기초 글을 작성하려 한다. 필요한 내용을 참고해서 확인해 보자. 

 

알고리즘 확인하기

 

 

 

Python으로 자료구조 조금 더 알아보기

[자료구조 기초] Data Structure 기초 시작하기

[선형 구조 - Python] 배열 

[선형 구조 - Python] 스택

[선형 구조 - Python]큐

[선형 구조 - Python] 연결 리스트

 

Python으로 알고리즘 조금 더 알아보기

[알고리즘 기초] Algorithm 기초 시작하기 - python

[검색 알고리즘] 선형 탐색과 이진탐색

[검색 알고리즘] 해시

[재귀 알고리즘] 재귀

[재귀 알고리즘] DFS

[재귀 알고리즘] BFS

[정렬 알고리즘] 버블 정렬

[정렬 알고리즘] 선택 정렬

[정렬 알고리즘] 삽입 정렬

[정렬 알고리즘] 퀵 정렬

[정렬 알고리즘] 병합 정렬

[정렬 알고리즘] 카운팅 정렬

 

---

 

 처음 시작하는 단계에서 직관적인 이해를 할 수 있도록 글을 적어보려한다. 따라서 가능한 어려운 용어를 제외하였고, 이 글을 통해 자료구조의 기초적인 이해도를 높일 수 있으면 좋겠다. 본 내용 뿐만 아니라 추가 공부를 통해 스스로 살을 붙여나가길 기대한다. 아래의 모든 예시는 Python과 JavaScript로 만들어 제공할 예정이다.

---

자료구조(Data Structure)

우리가 프로그래밍 언어를 배우는 이유는 무엇일까? 프로그래밍을 처음 배우면 보통 변수를 지정하고, 변수에 데이터를 넣는 것으로 시작을 한다. 그리고 변수를 이용해 데이터를 추가/수정/삭제/제거를 하면서 application을 만들기 시작한다. 즉, 이러한 관점에서 우리는 데이터를 다루기 위해 프로그래밍 언어를 배운다고 할 수 있다. 간단한 데이터가 아니라 수천/수만가지의 데이터를 다룬다면, 이러한 데이터를 다루는 방법에도 수만가지가 있을 것이다. 이러한 데이터를 좋은 구조로 조작하기 위해 알아야 하는것이 자료구조라고 할 수있겠다.

 

 

자료구조와 알고리즘

잘 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 프로그램 설계 시 가장 먼저 고려해야하는 것은 자료구조이다. 왜냐하면, 시스템의 기능에 따른 적절한 자료구조를 선택하는 것이 최종 성능을 크게 좌우한다. 그리고 자료구조에 따른 알고리즘에 대한 선택은 어느정도 공식화 되어있다고 할 수 있다. 물론 서비스에서 필수적으로 사용되어야할 알고리즘이 있다면, 그 알고리즘에 따른 자료구조의 선택은 필수적이라 할 수 있겠다. 

 

정리하면, 자료구조를 구현하기 위해서는 알고리즘이 필요하고, 반대로 알고리즘 문제를 풀기 위해 자료구조를 사용하기 때문에, 자료구조와 알고리즘은 밀접하다고 할 수 있다. 

 

 

자료구조의 성능 비교

자료구조의 필요성에 대해서는 위에서 알아보았다. 그러면 어떤 자료구조가 좋은지에 대한 기준도 알아보아야한다. 이는 성능 측정 방법이라고 할 수 있겠다. 당연한 이야기지만, 얼마나 빠르게 목표한 바를 빠르게 도출할 수 있는 프로그램을 만드는지도 중요하다. 추가적으로 좋은 컴퓨터를 이용하면, 계산하는 결과가 빠른 것 처럼 얼마나 돈이 많이 드는지(메모리)도 고려를 해야할 것이다. 물론 돈이 적게 들면서 목표한 결과를 빠르게 도출하는게 가장 좋지만, 이러한 경우도 분명한 trade-off가 있기 때문에 특정 상황에 따른 적절한 자료구조와 알고리즘을 선택하는 것이 개발자의 필수 역량이라고도 할 수 있겠다.

 

프로그램을 실행하고 완료하는데 필요로 하는 시간의 양을 시간 복잡도 (Time Complexity)라고 표현하고, 프로그램을 실행하고 완료하는데 필요한 메모리의 양을 공간 복잡도(Space Complexity)라고 한다. 사실 기초 단계에서는 알고리즘을 평가 시에 메모리 보다는 실행속도에 초점을 둔다. 이러한 성능을 수치로 나타낸 것이 빅-오 표기법(Big-Oh Notaion)이라고 한다.(기초단계에서는 사실상 시간복잡도라고 생각해도 무방하다) 빅-오 표기법의 대표적인 예는 아래와 같다.

 

---

 

Big-O 표기법 예시

우리의 목표는 정확한 자료구조를 인지하고 있고, 최적의 메모리와 계산을 도출해 내는 것을 목표로 한다. 아래의 표에서 N log N 까지는 괜찮을 알고리즘이라고 평가한ㄷ.

 

O(1)	N에 상관 없이 연산횟수가 한번으로 고정이다.
O(log N)	데이터 수에 비해 연산 횟수 증가률이 낮다.
O(N)	데이터 수에 비례해여 연산횟수가 증가.
O(N log N)	데이터 수가 2개로 늘면, 연산 횟수는 2배보다 조금 더 증가.
O(N ^ 2)	연산 횟수가 데이터 수의 제곱이다.
O(2 ^ N)	지수적 증가로 사용하기엔 비 요율적이다.

 

---

 

자료구조 종류

자료구조의 종류로는 형태에 따라 크게 선형 구조(Linear Data Structure)와 비선형 구조(Non-linear Data Structure)로 나뉜다. 초급자 기준으로 우리가 작성하고 있는 대부분의 구조는 선형 구조라고 할 수 있다. 쉽게 말하면, for문 하나를 사용하여 작성하는 대부분의 코드들은 선형구조로 연속적인 데이터의 구조라고 할 수 있다.  

 

선형 구조(Linear Data Structure)

선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조로, 데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다.  예시) 배열, 연결 리스트(linked list), 스택(stack), 큐, 덱(deque)

 

비선형 구조(Non-linear Data Structure)

비선형자료구조는 하나의 데이터 뒤에 다른 데이터가 여러개 올수있는 자료구조로 데이터가 일직선상으로 연결되어 있지 않아도 된다. 예시) 트리(tree), 그래프(graph)

 

---

 

정리

위의 두 가지 종류에 대한 가장 큰 차이는 각각의 자료구조에 대한 기초 블로그에서 찾아보자. 사실 우리는 하나의 데이터에 대해 핸들링 할 수 있는 방법은 다양한다. 하나의 데이터가 아닌 여러 데이터의 경우에 다루는 방법은 더욱 많다고 할 수 있다. 우리가 살고 있는 빅데이터 시대에 데이터를 잘 다루기 위해서는 자료구조에 대한 공부는 필수적이라고 할 수 있겠다.