[Data Structure] 자료구조란?

자료구조란? (Data Structure)

사전적인 의미는 자료(Data)의 집합의 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이라고 한다.

• 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아, 자료구조라는 이름을 붙였다.

 

자료구조를 쓰는 목적

이러한 자료구조를 사용하는 목적은 명확하다. 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있다.

 

자료구조의 선택 기준

적은 양의 데이터를 처리할 때는 어떤 자료구조를 사용하든 큰 차이가 없다. 그러나 대량의 데이터를 한 번에 처리함에 있어서 어떤 자료구조를 사용하는 가에 따라서 효율성에 있어 굉장한 차이가 있다.

예를 들어 스택과 연결 리스트가 있다고 했을 때, 원소 삽입에 대한 시간복잡도는 각각 O(1)과 O(n) 이다. 데이터가 100만 개가 존재한다고 했을 때, 한 번의 연산을 거치는 것과 100만번의 연산을 거치는 것은 효율성 면에서 큰 차이가 있다.

• 자료의 처리 기간
• 자료의 크기
• 자료의 활용 빈도
• 자료의 갱신 정도
• 프로그램의 용이성

자료의 처리를 보다 효율적으로 하기 위해서 위와 같은 사항을 고려하여 선택, 사용해야 한다.

 

자료구조의 특징

1. 효율성

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

한가지 예를 들어보자면 검색에 대한 알고리즘을 구현할때, 데이터의 양이 많다면 순차 검색(Linear Search)를 사용하는 것 보다 이분 검색(Binary Search)를 활용하는것이 더 효율적일 것이다. 왜냐하면 학생이라는 테이블에 학생에 대한 데이터가 100만개 있다고 할때, 순차 검색으로 데이터를 검색하게 되면 운이 좋을때는 1번의 연산으로 찾을 수 있겠지만, 운이 없을경우에는 100만번의연산을 거쳐야 할 것이다.

이에 반해 이분 검색은 연산의 횟수가 훨씬 줄어든다. 이와같이 목적에 맞는 자료구조를 사용하는것이 효율적이다.

2. 추상화

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

마찬가지로 자료구조 내부의 구현은 중요하지 않다. 어떻게 구현했는지 보다 어떻게 사용해야 하는지를 알고 있어야 한다.

예를들어 스택(Stack)의 경우, 먼저 들어간것이 나중에 나오는 FILO(First In Last Out)의 형태를 가지고 있다. 그리고 push() 함수를 이용해서 데이터를 삽입할 수 있고, pop() 함수를 이용해서 데이터를 추출할 수 있다. 그 함수 내부 구현이 어떻게 되었는지는 중요하지 않다.

사람마다 다른 코드를 작성할 것이고, 사용 언어, 개발 툴등 환경적인 변수에 의해서 다른 코드가 나올 것이기 때문에 추상적인 개념에 대해서만 이해하고 있다면 사용할 수 있다.

3. 재사용성

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

 

자료구조 분류와 종류

자료구조는 크게 선형 자료구조와 비선형 자료구조로 나뉜다.

선형 자료구조의 경우 데이터가 일렬로 나열되어 있는 것을 뜻하고, 비선형 자료구조는 특정한 형태를 띄고 있는 것을 뜻하는데, 각각에 해당하는 자료구조는 아래와 같다.

단순구조

자료 값을 사용하기 위해서 True/False, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본적으로 제공하는 자료형이다.

• 2진수, 정수, 실수, 문자, 문자열

선형구조

자료를 구성하는 데이터를 순차적으로 나열 시킨 형태다. 자료들 간의 관계가 1:1인 자료다.

• 배열 : 가장 일반적인 구조입니다. 메모리 상에 같은 타입의 자료가 연속적으로 저장되고 자료 값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
• 연결 리스트 : 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조 값으로 구성되어있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
• 덱 : 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조다.
• 스택 : 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다.
• 큐 : 스택과 반대로 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 쓸 때는 가장 나중에 나온다.

비선형구조

하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 것을 의미한다. 계층 구조나 망 구조를 갖는 자료구조로서 트리와 그래프가 있다.

• 그래프 : 꼭짓점과 꼭짓점을 잇는 변으로 구성되어있다.
• 트리 : 뿌리와 뿌리, 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조다.

파일구조

서로 관련 있는 필드로 구성된 레코드 집합인 파일에 대한 자료구조로 보조 기억 장치에 데이터가 실제로 기록되는 형태다. 메모리에 한번에 올릴 수 없는 대용량을 다룬다.

• 순차 파일, 색인 파일, 직접 파일

 

자료 구조와 알고리즘의 관계

Algorithm(알고리즘 또는 알고리듬)은 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것. 문제풀이에 필요한 계산절차 또는 처리과정의 순서다. 알고리즘의 중요한 특징은 같은 지식수준을 가진 사람이라면 그 알고리즘을 보고 누구나 같은 결과를 낼 수 있어야 한다. 요리의 레시피(recipe)에 비유해 볼 수 있다.

보통 자료 구조가 선택되면 그에 적용할 알고리즘은 거의 명확해진다. 즉, 자료 구조가 효율적인 알고리즘을 사용할 수 있게 함으로 자료 구조와 알고리즘은 매우 밀접한 관계를 가질 수밖에 없다.

만약, 장에 진열된 책들속에 하나의 책을 찾는다고 치면 어떤 순서나 규칙을 가지고 찾을 지에 대한 방법이라고 생각하면 된다. 왼쪽부터 순서대로 찾을 수도 있고, 역순으로 찾을 수도 있고, 중간부터 찾을 수도 있다. 클린 코드라는 책을 찾아야 한다면, 책장에 진열되어 있는 구조에 따라 효율적으로 책을 찾는 방법이 달라지게 된다. 제목 순으로 진열되어 있다면 역순으로 찾는 방법을 선택하게 되고, 분야 별로 진열되어 있다면 IT 서적 쪽을 먼저 찾게 될 것이다.

즉, 위와 같이 보통은 자료 구조의 선택 → 효율적인 알고리즘의 선택이 된다. 또한 알고리즘을 프로그램 명령어들의 집합이라고도 한다. 프로그램은 특정 문제를 해결하기 위한 처리 방법과 순서를 기록한 명령어들의 모음이다. 이 프로그램이 실행되기 위해서는 메모리에 올릴 데이터가 필요하며, 이 데이터들을 담아내는 방식은 자료구조다.

즉, 넓은 의미에서 자료구조 + 알고리즘(+a) = 프로그램이라고 할 수 있다.

위의 정의만 보면 프로그램 = 알고리즘 같아 보이지만, 디테일을 따지면 엄연히 다르다.
가장 간단한 예로 알고리즘은 항상 같은 결과를 보장하지만 프로그램은 그렇지 않을 수 있다.