유튜브의 신창수 교수님의 자료구조와 알고리즘을 듣고, 주요 내용을 정리해 놓는 것을 목적으로 이 글을 작성한다.
자료구조?
-
자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다 (https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
-
자료구조는 데이터에 편리하게 접근, 변경하기 위해 데이터를 저장하거나 조직하는 방법이다.
-
자료구조의 목적은 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며 잘 선택된 자료구조는 실행시간을 단축시키고, 메모리 용량의 절약을 이끌어낼 수 있다.
자료구조의 선택 기준
- 자료의 처리 시간
- 자료의 크기
- 자료의 활용 빈도
- 자료의 갱신 정도
- 프로그램의 용이성
자료구조의 특징
-
효율성 (Efficeincy)
자료구조를 사용하는 목적은 효율적인 데이터의 관리 및 사용이다. 따라서 상황에 맞는 적절한 자료구조의 사용이 필수적이라 할 수 있다. 예를 들어보면, 데이터의 양이 많은 상황에서는 순차 검색 (Linear Search)보다 이분 검색(Binary Search)를 활용하는 것이 더 효율적이다. -
추상화 (Abstraction)
추상화는 복잡한 자료, 모듈, 시스템 등으로부터 핵심적 개념만 간추려 내는 것이다. 특정 자료구조 자체의 내부 구현은 그리 중요하지 않기 때문에 실제 구현한 언어가 무엇인지에 따라서 코드는 다르지만, 추상적 개념만 알고 있으면 된다. 따라서 언어에 종속적이지 않다. -
재사용성 (Reusability)
자료구조를 설계 할 때, 특정 프로그램에 맞추어 설계하지 않고, 다양한 프로그램에서 사용될 수 있도록 범용화한다. 따라서 해당 자료구조의 인터페이스만 사용해 데이터를 처리하도록 하여 모듈화(재사용)가 가능하다.
자료구조의 분류
- 자료구조는 크게 선형 자료구조/비선형 자료구조로 나뉜다.
- 선형 자료구조는 데이터가 일렬로 나열돼 있는 것을 뜻한다.
- 비 선형 자료구조는 특정한 형태를 띄고 있는 것이다
- 선형구조의 자료구조는 배열, 리스트, 스택, 큐, 데큐(Dequeue)가 있고 비선형 구조의 자료구조는 트리, 그래프가 있다.
<선형 구조>
자료들이 1 : 1의 관계(일렬로 연결되는)로 처리되는 자료구조이다.
- 배열(Array)
가장 일반적인 구조로서 인덱스와 인덱스에 대응하는 데이터들로 이루어진 자료 구조 - 연결 리스트(Linked List)
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조 - 스택(Stack)
후입선출(後入先出, Last In First Out)의 자료구조 - 큐(Queue)
선입선출(先入先出, First In First Out)의 자료구조 - 데큐(Dequeue)
양쪽에서 모두 삽입/인출이 가능한 자료구조
<비선형 구조>
자료들의 구성이 1 : 1이 아닌 1 : n, n : m 간의 관계를 가지고 처리 되는 복잡한 자료 구조
- 트리(Tree)
부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드가 부모가 되어 다시 각각의 자식 노드가 연결되는 재귀적 형태의 자료구조 - 그래프(Graph)
정점(Vertex)과 정점들을 연결하는 변(Edge)으로 구성된 자료구조
알고리즘?
- 알고리즘은 자료구조 등으료 표현 및 저장된 데이터를 대상으로 하는 문제 해결 방법이다. 알고리즘은 자료구조에 의존적이다.
Reference
https://mandy8303.tistory.com/62
https://andrew0409.tistory.com/148
http://www.incodom.kr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0
