/* 본 게시물은 ' ' 의 내용을 토대로 작성되었습니다. */
참고 자료
#자료구조
1. 자료 구조란?
자료 구조의 정의는 다음과 같다.
자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.
[출처] : 위키백과 - 자료구조
그렇다면 자료구조를 왜 배워야할까?
이에 대한 답은 자료 구조에 따라 알고리즘의 성능에 영향을 결정하기 때문이다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 우리는 프로그램을 설계할 때, 어떠한 자료구조를 선택할지는 가장 우선적으로 고려해야 한다. 또한, 특정한 알고리즘을 반드시 필요로 할 때, 해당 알고리즘이 어떤 자료구조에서 가장 나은 성능을 발휘할 때 인지 알아야한다.
즉, 자료구조는 알고리즘을 익히는 데 필요한 기초 지식이다. 이를 배우면 데이터를 효율적으로 관리하는 기법을 배우는 것과 마찬가지이다.
2. 자료 구조의 종류
자료 구조는 구현, 형태에 따라 분류 할 수 있다.
구현에 따른 자료구조 종류
- 배열: 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
- 튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조이다.
- 연결 리스트 - 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
- 원형 연결 리스트 - 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.
- 이중 연결 리스트 - 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
- 환형 이중 연결 리스트 - 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.
- 해시 테이블 - 개체가 해시값에 따라 인덱싱된다.
형태에 따라 자료구조를 분리했을 때 크게 선형 구조와 비선형 구조로 나눌 수 있다.
선형 구조 : 구조와 자료 간 관계가 1대 1인 선형구조
- 스택 - 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.
- 큐 - 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
- 환형 큐 - 한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐이다.
- 덱 - 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.
비 선형 구조: 1대 다 혹은 다 대 다 구조
- 그래프 - 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.
- 유향 그래프, 무향 그래프 - 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다. 유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.
- 트리 - 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현된다.
- 힙 - 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다. (이진 트리- 자식이 최대 두 개인 트리.)
자료 구조 공부 시작!
반응형
