자료구조 / 추상자료형

 

1. 자료(Data)

 

자료란, 문자, 숫자, 소리, 그림, 영상 등 특정 형태로 된 의미를 지니는 단위를 말한다. 이러한 단위가 무작위로 나열되어 있다면 어떨까? 만약 책을 읽는데, 그 책의 원래 내용을 단어 단위로 뒤섞어서 책을 구성했다고 생각해보자. 이 책이 무엇을 전하고 있는지 판단할 수 있을까? 따라서 우리는 자료를 잘 가공하여 원하는 정보를 얻을 수 있도록 구조화할 필요가 있다.

컴퓨터도 이와 비슷하게 데이터를 가공하여 정보를 전달할 수 있어야 한다. 컴퓨터가 인간보다 잘하는 것이 딱 2가지 있는데, 이는 바로 계산 / 저장이다. 컴퓨터는 어마어마한 데이터를 저장하고 이에 대한 계산을 그 어떤 인간보다도 빠르게 수행하여 결과를 도출할 수 있다. 하지만 이러한 자료들이 적절한 방식으로 저장되어 있지 않다면 효율적인 가공이 어려울 것이다. 그래서 우리는 자료를 어떻게 컴퓨터에 구조화해서 저장할 지 고안해야 했다.

 

 

2. 자료구조(Data Structure)

 

자료구조는 자료의 집합을 의미한다. 각각의 단위 데이터가 논리적으로 일관된 규칙에 의해서 나열되어 연산 수행이 효율적으로 될 수 있도록 체계화한 것을 의미한다. 컴퓨터로 어떠한 결과를 도출하기 위해서 연산을 수행한다면, 그 데이터가 어디에 저장되어 있는지, 어떤 방식으로 저장되어 있는지를 쉽게 알 수 있어야 한다. 그런데 이러한 작업이 최대한 효율적으로 되려면 그 구조의 형태와 용도가 명확해야 할 것이다. 적절한 구조를 선택하지 못한다면 전혀 엉뚱한 결과를 낼 수도 있고, 제대로 결과를 내더라도 너무나 시간이 오래 걸려 컴퓨터를 쓰는 의미가 없어질지도 모른다.

자료구조의 선택기준은 아래와 같다.

① 자료의 처리 시간
② 자료의 크기
③ 자료의 활용 빈도
④ 자료의 갱신 정도
⑤ 프로그램 용이성

자료구조의 특징은 아래와 같다.

(1)효율성(Efficiency)

자료구조는 자료를 빠르게 접근하여 필요한 연산을 수행할 수 있도록 구조화되어야 한다. 수백만 개의 자료가 있다면, 자료 간의 연관성이 어떤가에 따라서 연관된 자료를 연결하여 저장할 수 있고, 혹은 순차적으로 저장할 수도 있다.. 만약 연관성이 있는 데이터의 경우 예를 들어 상 - 하 관계라고 보자. 전체 세계지도에서 특정 위치의 마을을 찾아야 한다고 할 때, 이 마을의 GPS 위치가 제공되고 대륙 - 국가 - 주 - 도시 - 마을의 단위별 하위 관계로 구성하였다고 생각해보자.

그러면, 이 데이터를 GPS 위치를 기반으로 대량의 단위별 데이터가 상단의 GPS 범위에 해당되는 경우 그 하위 자료로써 연결되어 구성된 경우, 이 특정 데이터의 위치를 찾는데 있어 대륙 부터 순서대로 몇 번의 연산만 수행하면 쉽게 그 결과를 도출할 수 있다. 그러나 (0, 0) 부터 진행하여 모든 마을을 순차적으로 숫자가 커짐에 따라 저장했다면 어떨까? 운이 나쁘면 전체 위치를 모두 비교해야 할수도 있다. 지구에 마을이 1천만개라면 1천만 번 수행해야 할 수 있다.. 이와 같이 연산의 횟수를 줄일 수 있을 수록 더욱 효율적인 자료구조가 된다.

(2) 추상화(Abstraction)

추상화는 복잡한 자료, 모듈, 시스템에 대해서 핵심적인 개념 및 기능만 추려내는 것이다. 프로그래밍을 하는데 우리는 자료구조를 활용을 하는 것에 방점이 있지, 자료구조를 어떻게 구현하는지가 더 중요한 것이 아니다. 어떠한 논리적인 규칙에 의해서 자료를 저장, 처리를 할 때, 내부적으로 그 구조가 어떻게 되어 있는지를 구체적으로 일일이 알 필요는 없다. 우리는 그 자료구조가 어떻게 동작하는 것인지 어떨 때 사용하는 것인지 그 개념과 기능만 알면 얼마든지 Logic을 수행할 수 있게 된다.

(3) 재사용성(Reusable)

자료구조를 설계한다면, 우리가 특정 프로그램에서만 종속적으로 동작하도록 설계해서는 안된다. 그러면 동일한 기능을 갖는 수많은 자료구조를 만들게 되는 비효율을 초래하게 될 것이다. 그래서 필요한 개념 / 기능만 모듈화하여 설계한다면 어떠한 프로그램에서든 범용적으로 활용할 수 있게 설계해야 한다.

 

 

3. 자료구조의 종류

 

기본적으로 자료를 저장한다면 어떻게 저장을 할 수 있을까? 우선 일렬로 데이터를 나열하는 방법이 있을 수 있다. 혹은, 관계가 있는 데이터를 서로 연관 지어서 특정 데이터를 찾으면 그와 연관된 데이터를 찾도록 할 수 있다.(상단의 예시와 같이)

전자는 선형 구조, 후자는 비선형 구조라고 볼 수 있겠다. 선형구조에는 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue), Deque(덱) 등이 있으며 비선형 구조에는 트리(Tree), 그래프(Graph) 가 있다고 볼 수 있다.

아래의 그림을 참고하면 더욱 이해가 쉬울 것으로 보인다. 아래의 내용 중 선형 리스트는 순서를 갖고 나열된 데이터를 의미하며 일반적으로 배열(Array)로 구현된다.

자료구조의 종류

 

 

4. 추상자료형(ADT, Abstract Data Type)

 

추상자료형은 자료구조의 '구체적 기능의 구현이 아닌, 순수하게 무슨 기능인지를 나열한 것'을 의미한다. 즉, 위에서 언급한 여러 자료구조가 있다면 그 자료구조들을 어떻게 사용할 수 있는지, A라는 자료구조가 가진 기능은 무엇인지를 정의한 것을 의미한다.

자바(Java)에서는 인터페이스(Interface)가 그러한 역할을 한다. 인터페이스(Interface)는 자바(Java)에서 필요한 기능들을 사전에 정의해놓고 그를 구현(Implements)하는 클래스(Class)에서 해당 기능의 세부 로직을 구현하도록 요구된다. 예를 들어, 위의 Linked List와 같은 자료구조의 경우, List라는 인터페이스(Interface)를 구현하여 클래스(Class)를 구성하고 있다. 또한 그 List는 Collection 이라는 인터페이스(Interface)를 구현하여 자바(Java)에서는 전체 자료구조를 하나의 프레임워크(Framework)로써 제공하고 있다.

사용자는 내부의 로직이 어떤 방식으로 구현되어 있는지 알 필요가 없다. 자료구조의 내부의 기능을 사용하여 문제를 해결하는 로직을 구성하면 된다.

 

오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.