Data Structure : Introduction
자료구조(Data Structure)란?
자료구조(Data Structure)의 정의
사진출처: 인프런 Inflearn
“컴퓨터과학에서
데이터를 구조적으로 표현하는 방식과이를 구현하는 데 필요한 알고리즘“
- 컴퓨터의 메모리는 1차원 구조[1] 이기 때문에 현실 세계의 다차원 데이터를 다루기 위해서는 이것을 1차원인 선 형태로 바꾸는 것이 필요하다.
- 위와 같은 기초 알고리즘에는 2차원 배열 및 이진 트리, 그래프 등의 자료구조가 있다.
List, Stack, Queue, Circular Queues, Heap tree, Graph정도의
대표적인 7가지 개념을 주축으로 포스팅 해보겠다.
자료형(Data Type)이란?
자료형(Data Type)이란?
용어 그대로
"자료(Data)의 종류"이다. 한번쯤 코딩을 해보았다면 알 수 있을 것이다.
바로int(정수), double(실수), char(문자), str(문자열)등등 프로그래밍 언어별로 많은 종류가 있다.
- 자료형을 사용할 때에는 실행 가능한 (executable) 연산인지 확인해야한다.
자료형(Data Type) 이 결정되면 그에 따라 해당 Data와 관련된 연산이 달라질 수 있기 때문이다.- 복잡한 자료형을 구현할 때에는
데이터간의 연산이 함수(Function)로 작성된다.
(ex. Stack 자료형에서 새로운 값을 추가하는 연산은 add()라는 Function으로 정의된다.)
추상적자료형(Abstract Data Type)이란?
추상적자료형(ADT: Abstract Data Type)이란?
자료 자체의 형태와 그 자료에 관계된 연산들을 추상적, 수학적으로만 정의한 것.
추상적자료형(ADT)은 데이터나 연산이무엇(what)인지는 정의되지만,
어떻게(how)컴퓨터 상에서 구현할 것인지는 정의되지 않는다.- EX. 자연수를 나타내는 추상적 자료형 중 Nat_Number 이 있다. Nat_Number의 연산 중 하나인 add() 는
Nat_Number add(x,y)의 형태로 사용할 수 있다.여기서 추상화(Abstraction)란?
- 어떤 시스템의 간략화 된 기술 또는 명세로서,
System의 가장 핵심적인 구조나 동작에만 집중하는 것.- 객체 지향 언어의 대표격인 Java를 학습해본 개발자라면 무슨 느낌인지 알 것이다.
Java의 class 개념과 일맥상통이라 볼 수 있다고 한다.
Nat_Number add(x,y)
- 연산의 이름 : add
- 매개변수 : x, y
- 반환형 : Nat_Number
와 같이 연산이 무엇인지(what) 정의할 수 있다.
하지만 어떻게(how) + 연산을 구현하는지에 대한 구체적인 코드는 주어지지 않는다.
이것이 추상적자료형(ADT)이다.
Data Structure Categories
1. 혼합 자료구조 (Composite Data Structure) - 배열 (Array)2. 선형 자료구조 (Linear Data Structure) - - 배열 (Array) ---> 가변 길이 배열 (STL의 Vector) - 리스트 ---> 연결 리스트 (Linked List)3. 추상적 자료구조 (Abstract Data Structure) - - 리스트 ---> 연결 리스트 (Linked List) - 스택 (Stack) - 큐 (Queue) ---> 환형 큐 (Circular Queues) - 트리 (Tree) ---> 트라이 (Trie) - 그래프 (Graph)4. 딕셔너리 자료구조 (Dictionaries) - - 연관 배열 - Map (Associative array) - 연관 리스트 - 해시 테이블
참고: 나무위키 Data_Structure
참고: C언어로 쉽게 풀어쓴 자료구조 <개정 3판> 천인국, 공용해, 하상국 지음
Task Lists
[1] 하드웨어의 구조는 2차원 이지만, CPU가 인지하는 것에 있어 논리적 메모리 공간은 1차원임.
- 자료구조(Data Structure)란?
- 자료형(Data Type)이란?
- 추상적자료형(Abstract Data Type)이란?
Comments