추상적 자료형

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

추상적 자료형(Abstract Data Type, 줄여서 ADT)은 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명기한 것이다. 추상적 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르다. 비슷한 개념의 추상적 자료 구조는 각 연산의 시간 복잡도를 명기하고 있지만 추상적 자료형에서는 이것조차 명기하지 않는다.

추상적 자료형은 인터페이스구현을 분리하여 추상화 계층을 둔 것이다. 예를 들어, 전기 밥솥을 추상적 자료형에 비유한다면, 그 속에 들어가는 밥은 자료가 되고, 밥솥에 있는 취사, 예약취사 버튼들과 남은 시간을 표시하는 디스플레이에 어떤 내용들이 표시되어야 하는지를 명기한 것이다. 추상적 자료형에서는 이것들이 어떻게 구성되는지 관심이 없고, 몇 와트전기를 소모하는지에 대해서도 관심이 없다.

자료에 대한 연산은 자료에 대하여 질의를 던지는 것과 자료를 변경하기 위한 연산으로 나뉜다. 유명한 자료구조인 스택에서 자료를 변경하기 위한 연산은 기본적으로 push와 pop이 있다. 여기에 자료에 대하여 질의를 던지는 연산으로 스택의 크기를 알 수 있는 size 연산, 스택이 가득차거나 비었는지를 알 수 있는 full, empty 연산이 있고, 추가적으로 pop을 하면 제거될 자료를 볼 수 있는 peek 연산 등을 정의할 수 있다. 만약 여기에 각 연산들은 모두 상수 시간 복잡도(즉, O(1))에 일어나야 한다고 명기한다면 이것은 '추상적 자료 구조'가 된다.

추상적 자료 구조[편집]

추상적 자료 구조는 이론 컴퓨터 과학 분야에서 자료에 대한 일련의 연산이 정의되며, 각각의 연산에 대한 연산 복잡도가 정의된 가상의 자료 저장 공간이다. 이는 자료 구조의 구체적인 구현 방식과는 관련이 없다.

추상적 자료 구조를 올바르게 선택하는 것은 효율적 알고리즘을 설계하고, 연산 복잡도를 추정함에 있어서 필수적이다. 반면, 구체적인 자료구조를 올바르게 선택하는 것은 알고리즘의 효과적인 구현에 중요하다.

이러한 추상화 개념은 프로그래밍 언어 이론에서의 추상적 자료형(Abstract data type, ADT)과 매우 유사하다. 데이터 모델이라는 또 다른 유사한 추상화 개념은 데이터 요소 간의 상호 연관 패턴(이상하게 들리겠지만, 자료 구조의 구조 자체)을 나타낸다.

많은 추상적 자료 구조(그리고 추상적 자료형)의 이름은 구체적 자료 구조의 이름과 동일하다.

추상적 자료형의 예[편집]

유명한 추상적 자료형에는 복소수, 리스트, 스택, , , 우선순위 큐, 집합 등이 있다.

같이 보기[편집]