[알고리즘] 자료구조 란?

자료구조란?

자료구조(data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 집합을 의미하며 각 원소들 사이의 관계가 논리적으로 정의된 일정한 규칙에 의하여 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분하여 표현한 것을 말한다.

자료구조가 필요한 이유?

데이터를 효율적으로 저장, 관리하여 메모리를 효율적으로 사용하기 위함이다. 적절한 자료구조의 사용은 메모리의 용량을 절약해주고, 실행시간을 단축시켜줄 수 있다.

자료구조의 선택기준

작업의 효율성, 추상화, 재사용성을 증가시키기 위하여 상황에 따른 적절한 자료구조 사용이 필요하다.

따라서, 아래의 사항을 고려하여 자료를 좀 더 효율적으로 처리할 수 있도록한다.

자료의 처리시간

자료의 크기

자료의 활용빈도

자료의 갱신정도

프로그램의 용이성

자료구조의 특징

1. 효율성

앞서 설명 했듯이 자료구조를 사용하는 목적은 효율적인 데이터의 관리 및 사용이다. 따라서 적절한 자료구조를 선택하여 사용한다면 업무의 효율이 올라갈 것이다. 

2. 추상화

추상화란 복잡한 자료, 모듈, 시스템 등으로 부터 핵심적인 개념만 간추려 내는 것이다. 자료구조를 구현할 때 중요한 것은 어느 시점에 데이터를 삽입할 것이며, 어느 시점에 이러한 데이터를 어떻게 사용할것인지에 대해서 초점을 맞출수 있기 때문에 구현 외적인 부분에 더 시간을 쏟을 수 있다.

예를들어 스택(Stack)의 경우 먼저 들어간것이 나중에 나오는 FILO(First In Last Out)의 형태를 가지고 있다. 그리고 push() 함수를 이용해서 데이터를 삽입할 수 있고, pop() 함수를 이용해서 데이터를 추출할 수 있다. 그 함수 내부 구현이 어떻게 되었는지는 중요하지 않다. 사람마다 다른 코드를 작성할 것이고, 사용 언어, 개발 툴등 환경적인 변수에 의해서 다른 코드가 나올 것이기 때문에 추상적인 개념에 대해서만 이해하고 있다면 사용할 수 있다.

3. 재사용성

자료구조를 설계할때 특정 프로그램에서만 동작하게 설계하지는 않는다. 다양한 프로그램에서 동작할 수 있도록 범용성 있게 설계하기 때문에 해당 프로젝트가 아닌 다른 프로젝트에서도 사용할 수 있다.

자료구조의 분류

자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간 크기에 따라 여러 가지 종류의 자료구조 중 하나를 선택할 수 있다. 자료구조의 종류로는 자료형의 따라 분류하는 단순 구조와 자료 간 관계가 1 대 1인 선형 구조, 1 대 다 혹은 다 대 다 구조인 비선형 구조, 마지막으로 파일 구조가 있다.

단순구조

프로그래밍에서 사용되는 기본 데이터 타입

선형 구조

선형구조란 자료를 구성하는 데이터를 순차적으로 나열시킨 형태를 의미

저장되는 자료의 전후관계가 1:1

배열(Array) : 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.

연결 리스트(Linked List) : 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.

원형 연결 리스트 : 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.

이중 연결 리스트 : 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.

원형 이중 연결 리스트 : 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.

스택(Stack) : 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.

큐(Queue) : 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.

덱(Deque) : 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.

비선형 구조

비선형구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것을 의미

데이터 항목 사이의 관계가 1:n 또는 n:m

그래프(Graph) : 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.

유향 그래프, 무향 그래프 - 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다. 유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.

트리(Tree) : 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현된다.

파일구조

서로 관련된 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조이다.