맨위로가기

추상 자료형

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

추상 자료형(ADT)은 데이터와 해당 데이터를 조작하는 연산들을 묶어 놓은 개념으로, 프로그래밍 언어에서 자료 구조를 추상화하는 데 사용된다. 1974년 바바라 리스코프와 스티븐 N. 질레스가 CLU 언어 개발의 일환으로 처음 제안했으며, 1980년대에는 대수적 명세와 거의 동의어로 사용되었다. ADT는 도메인, 연산 집합, 제약 조건의 집합으로 구성되며, 인터페이스와 구현을 분리하여 구현 세부 사항을 숨기고 사용자가 인터페이스에만 집중하도록 한다. 추상 변수, 스택, 큐, 리스트, 집합 등 다양한 예시가 있으며, C++, 자바 등의 객체 지향 언어에서 클래스를 통해 구현된다.

2. 역사

추상 자료형은 1974년 바바라 리스코프와 스티븐 N. 질레스가 CLU 언어 개발의 일환으로 처음 제안하였다.[2] 1980년경 대수적 명세는 컴퓨터 과학 분야의 중요한 연구 주제였으며, 당시에는 추상 자료형과 거의 동의어로 사용되었다. 이는 보편 대수학을 기반으로 한다.[3]

1960년대 구조적 프로그래밍 시점부터 단계적 세분화와 같은 기법과 제어 구조의 활용 장려 외에도, 데이터 구조와 코드를 연계하여 데이터 구조의 변경이 소스 코드 내에 흩어져 버리는 이전 프로그래밍의 문제점에 대처하는 데이터 추상에 관한 논의가 나타났다. 추상 자료형은 이러한 데이터 추상화의 구체적인 방법으로 1974년 바바라 리스코프가 제안한 언어 CLU에서 제안되었다.

3. 정의

형식적으로, 추상 자료형(ADT)은 대수 구조와 유사하며,[4] 도메인, 연산 집합, 그리고 연산들이 만족해야 하는 제약 조건들의 집합으로 구성된다. 도메인은 종종 암묵적으로 정의되는데, 예를 들어 ADT 연산 집합에 대한 자유 대상이 있다. ADT의 인터페이스는 일반적으로 도메인과 연산만을 지칭하며, 사전 조건 및 사후 조건과 같은 연산에 대한 일부 제약 조건을 포함할 수 있지만, 동작으로 간주되는 연산 간의 관계와 같은 다른 제약 조건은 포함하지 않는다. 동작에 대한 형식적 명세에는 공리적 의미론과 연산적 의미론의 두 가지 주요 스타일이 있다.[4]

제약 조건은 인터페이스의 일부는 아니지만, ADT의 정의에 여전히 중요하다. 예를 들어, 스택과 큐는 유사한 요소 추가/제거 인터페이스를 가지지만, 마지막으로 입력된 것이 먼저 출력되는(LIFO) 동작과 먼저 입력된 것이 먼저 출력되는(FIFO) 동작을 구분하는 것은 제약 조건이다. 제약 조건은 방정식뿐만 아니라 논리식으로도 구성된다.

3. 1. 보조 연산

추상 자료형(ADT)의 표현은 핵심 연산 외에도 다음과 같은 보조 연산을 포함할 수 있다.

  • `create()`: ADT의 새로운 인스턴스를 생성한다.
  • `compare`(''s'', ''t''): 두 인스턴스의 상태가 어떤 면에서 동일한지 검사한다.
  • `hash`(''s''): 인스턴스 상태로부터 표준 해시 함수를 계산한다.
  • `print`(''s'') 또는 `show`(''s''): 인스턴스 상태를 사람이 읽을 수 있는 형태로 표현한다.


이러한 이름은 예시이며 저자에 따라 다를 수 있다. 명령형 스타일의 ADT 정의에서는 다음과 같은 연산도 자주 발견된다.

  • `initialize`(''s''): 새로 생성된 인스턴스 ''s''를 추가 연산을 위해 준비하거나, 어떤 "초기 상태"로 재설정한다.
  • `copy`(''s'', ''t''): 인스턴스 ''s''를 ''t''와 동일한 상태로 만든다.
  • `clone`(''t''): ''s'' ← `create()`, `copy`(''s'', ''t'')를 수행하고 ''s''를 반환한다.
  • `free`(''s'') 또는 `destroy`(''s''): ''s''가 사용한 메모리 및 기타 자원을 회수한다.


`free` 연산은 ADT가 "메모리를 사용"하지 않는 이론적인 개체이므로 일반적으로 관련이 없거나 의미가 없다. 그러나 ADT를 사용하는 알고리즘에서 사용되는 저장 공간을 분석해야 할 때는 필요할 수 있다. 이 경우, 각 ADT 인스턴스가 상태에 따라 얼마나 많은 메모리를 사용하는지, 그리고 `free`에 의해 얼마나 많은 메모리가 풀로 반환되는지를 지정하는 추가적인 공리가 필요하다.

3. 2. 제한된 유형

추상 자료형(ADT)의 정의는 종종 인스턴스에 저장된 값을 해당 변수의 "범위"라고 하는 특정 집합 ''X''의 멤버로 제한한다. 예를 들어, 추상 변수는 정수만 저장하도록 제한될 수 있다. 프로그래밍 언어와 마찬가지로, 이러한 제한은 설명과 알고리즘 분석을 단순화하고 가독성을 향상시킬 수 있다.

3. 3. 앨리어싱

운영 스타일에서는 여러 인스턴스가 어떻게 처리되는지, 그리고 하나의 인스턴스를 수정하는 것이 다른 인스턴스에 영향을 미칠 수 있는지 여부가 불분명한 경우가 많다. 추상 자료형(ADT)을 정의하는 일반적인 스타일은 알고리즘 실행 중에 하나의 인스턴스만 존재하는 것처럼 연산을 작성하고 모든 연산을 해당 인스턴스에 적용하는 것이다. 예를 들어, 스택은 `push`(''x'') 및 `pop`() 연산을 가질 수 있으며, 이는 유일하게 존재하는 스택에서 작동한다.

여러 인스턴스 스타일은 때때로 별칭 공리와 결합된다. 즉, `create`()의 결과는 알고리즘에서 이미 사용 중인 인스턴스와 다르다는 것이다. 추상 자료형의 구현은 여전히 메모리를 재사용하고 `create`()의 구현이 이전에 생성된 인스턴스를 생성하도록 허용할 수 있다. 그러나 그러한 인스턴스가 "재사용"되기까지 정의하는 것은 추상 자료형 형식에서 어렵다.

보다 일반적으로, 이 공리는 다른 인스턴스와의 부분적 별칭도 제외하도록 강화될 수 있으므로, 트리 또는 레코드와 같은 복합 추상 자료형과 포인터와 같은 참조 스타일 추상 자료형이 완전히 분리된 것으로 간주될 수 있다. 예를 들어, 추상 변수의 정의를 추상 레코드를 포함하도록 확장할 때, 레코드 변수 ''R''의 필드 ''F''에 대한 연산은 분명히 ''F''를 포함하며, 이는 ''R''의 일부이지만 ''R''과 구별된다. 부분적 별칭 공리는 하나의 레코드 변수의 필드를 변경하는 것이 다른 레코드에 영향을 미치지 않는다고 명시한다.

3. 4. 복잡도 분석

일부 저자는 각 연산의 계산 복잡도를 시간(연산 계산)과 공간(값 표현) 측면에서 모두 포함하여 알고리즘 분석을 돕기도 한다. 예를 들어, 각 연산이 추상 자료형(ADT)의 상태에 관계없이 동일한 시간을 소요하고 각 값이 동일한 공간을 차지하거나, ADT의 "크기"가 있고 연산이 ADT 크기에 대해 선형, 2차 등이라고 지정할 수 있다. C++ 표준 템플릿 라이브러리의 설계자인 알렉산더 스테파노프는 복잡성 어서션이 인터페이스의 일부여야 한다고 주장했다.[5]

다른 저자들은 스택 ADT가 연결 목록 또는 배열로 구현되는지에 관계없이 동일하며 연산 비용의 차이에도 불구하고 ADT 명세가 구현과 독립적이어야 한다고 주장하며 이에 반대한다.

4. 인터페이스와 구현의 분리

형식적으로 추상 자료형(ADT)은 수학의 대수 구조와 유사하며,[4] 도메인, 연산 집합, 그리고 연산들이 만족해야 하는 제약 조건 집합으로 구성된다. 추상 자료형의 인터페이스는 일반적으로 도메인과 연산만을 지칭하며, 사전 조건 및 사후 조건과 같은 연산에 대한 일부 제약 조건을 포함할 수 있다.

프로그램이 구현될 때, 추상 자료형은 구현을 숨기는 인터페이스를 나타낸다. 추상 자료형의 사용자는 구현이 아닌 인터페이스에 관심을 가진다.

추상 자료형의 강점은 사용자로부터 구현이 숨겨져 있다는 것이다. 인터페이스만 공개된다. 이것은 추상 자료형이 여러 가지 방법으로 구현될 수 있음을 의미하지만, 인터페이스에 충실한 한 사용자 프로그램은 영향을 받지 않는다.

예를 들어, 이진 탐색 트리 추상 자료형은 이진 트리, AVL 트리, 레드-블랙 트리, 배열 등 여러 가지 방법으로 구현할 수 있다. 그러나 구현에 관계없이 이진 탐색 트리는 "삽입", "삭제", "검색"과 같은 동일한 연산을 수행할 수 있다.

5. 구현

추상 자료형(ADT)은 다양한 방식으로 구현될 수 있으며, 여러 구체적인 자료 구조를 사용할 수 있다.[9] 예를 들어, 추상 스택은 연결 리스트나 배열로 구현할 수 있다. ADT의 서로 다른 구현은 의미상 동일하며, ADT를 사용하는 코드에서 상호 교환적으로 사용될 수 있다. 이는 추상화 또는 캡슐화의 한 형태를 제공하여, 서로 다른 상황에서 ADT 객체를 사용할 때 유연성을 높인다.[9]

ADT는 종종 불투명한 자료형 또는 핸들로 포장되어 모듈에 포함되며, 인터페이스는 연산의 시그니처만 포함한다.[9] 이를 통해 클라이언트에 영향을 주지 않고 구현을 변경할 수 있다. C++와 자바 같은 객체 지향 언어는 클래스를 통해 추상 자료형을 지원하며, ADT의 각 인스턴스는 일반적으로 해당 클래스의 객체이다.[9]

일부 프로그래밍 언어는 특정 내장 자료형의 표현을 모호하게 정의하고, 수행 가능한 연산만 정의하여 '내장 ADT'로 간주하기도 한다. 예를 들어, Awk, Lua, Perl의 배열은 추상 리스트의 구현으로 볼 수 있다.

형식적 명세 언어에서 ADT는 공리적으로 정의될 수 있으며, 해당 언어는 이러한 ADT의 값을 조작하여 직접적이고 즉각적인 구현을 제공한다. 예를 들어, OBJ는 방정식을 정의하고 재작성하여 실행할 수 있다.

6. 추상적 자료 구조

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

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

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

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

7. 추상 자료형의 예

잘 알려진 추상 자료형에는 복소수, 리스트, 스택, 큐, 맵, 우선순위 큐, 집합 등이 있다.[8]

널리 사용되는 ADT는 다음과 같다.



이러한 ADT는 다양한 방식으로 정의될 수 있으며, 반드시 동일하지는 않다. 예를 들어, 추상 스택은 푸시되었지만 아직 팝되지 않은 항목의 수를 알려주는 `count` 연산을 가질 수도 있고 그렇지 않을 수도 있다.

7. 1. 내장형 추상 자료형

일부 프로그래밍 언어 사양에서는 내장된 추상 자료형(ADT)을 지원한다. Awk, 루아, 펄과 같은 수많은 스크립트 언어가 그 예시이며, 추상 리스트의 구현체로 간주된다.

7. 2. 추상 변수

추상 변수는 명령형 변수의 의미를 가진 가장 단순한 비자명 추상 자료형(ADT)으로 간주될 수 있다. 이 변수는 `fetch`와 `store`의 두 가지 연산을 허용한다. 연산적 정의는 종종 추상 변수를 사용하여 작성된다. 공리적 의미론에서, V를 추상 변수의 유형으로, X를 내용의 유형으로 설정하면, `fetch`는 V \to X의 함수이고, `store`는 V \to X \to V의 유형을 가진다. 주요 제약 조건은 `fetch`가 항상 동일한 변수 ''V''에 대한 가장 최근의 `store` 연산에서 사용된 값 ''x''를 반환한다는 것이다. 즉, `fetch(store(V,x)) = x`이다. 또한 `store`가 값을 완전히 덮어쓰도록 요구할 수 있다. `store(store(V,x1),x2) = store(V,x2)`.

연산적 의미론에서, `fetch`(''V'')는 위치 ''V''의 현재 값을 반환하는 프로시저이고, `store`(''V'', ''x'')는 값 ''x''를 위치 ''V''에 저장하는 `void` 반환 유형의 프로시저이다. 제약 조건은 읽기가 쓰기와 일관된다는 형태로 비공식적으로 설명된다. 많은 프로그래밍 언어에서와 마찬가지로, 연산 `store`(''V'', ''x'')는 종종 ''V'' ← ''x'' (또는 유사한 표기법)로 작성되며, 변수 ''V''가 값이 필요한 컨텍스트에서 사용될 때마다 `fetch`(''V'')가 암시된다. 따라서, 예를 들어 ''V'' ← ''V'' + 1은 일반적으로 `store`(''V'',`fetch`(''V'') + 1)의 약어로 이해된다.

이 정의에서는 이름이 항상 다르다고 암시적으로 가정한다. 즉, 변수 ''U''에 값을 저장하는 것은 다른 변수 ''V''의 상태에 영향을 미치지 않는다. 이 가정을 명시적으로 만들기 위해 다음 제약 조건을 추가할 수 있다.

  • 만약 ''U''와 ''V''가 다른 변수라면, 시퀀스 { `store`(''U'', ''x''); `store`(''V'', ''y'') }는 { `store`(''V'', ''y''); `store`(''U'', ''x'') }와 동일하다.


이 정의는 ''V''에 대한 어떤 `store` 연산을 수행하기 전에, 즉 ''초기화되지 않은'' ''V''를 `fetch`(''V'')의 평가 결과에 대해 아무런 언급을 하지 않는다. 저장 전에 가져오는 것은 허용되지 않거나, 특정 결과를 갖도록 정의되거나, 지정되지 않은 상태로 남겨둘 수 있다. 이러한 `fetch`가 합법적이며 변수의 범위 내에서 임의의 값을 반환한다는 가정에 효율성이 의존하는 일부 알고리즘이 있다.

7. 3. 추상 스택

추상 스택은 후입선출(Last-In-First-Out, LIFO) 구조를 가지는 자료형이다. 일반적으로 다음 세 가지 주요 연산으로 정의된다.

  • `push`: 스택에 데이터를 삽입한다.
  • `pop`: 스택에서 데이터를 제거한다.
  • `peek` 또는 `top`: 스택의 맨 위 데이터 항목을 제거하지 않고 접근한다. [6]


완전한 추상 스택 정의에는 불리언 값을 반환하는 `empty` (''S'') 함수와 초기 스택 인스턴스를 반환하는 `create` () 연산도 포함된다.

7. 4. Boom 계층 구조

이진 트리, 리스트, 가방(bag), 집합 추상 자료형의 Boom 계층 구조는 복잡한 예시에 해당한다.[7] 이 자료형들은 모두 세 가지 연산으로 선언할 수 있다. 연산의 종류는 다음과 같다.

  • `null`: 비어있는 컨테이너를 생성한다.
  • `single`: 단일 요소에서 컨테이너를 생성한다.
  • `append`: 동일한 유형의 두 컨테이너를 결합한다.


네 가지 자료형에 대한 완전한 명세는 이러한 연산에 대해 다음 규칙을 추가하여 제공할 수 있다.

자료형규칙
트리`null`은 트리에 대한 왼쪽과 오른쪽 중립 요소이다: `append(null,A) = A`, `append(A,null) = A`.
리스트`append`는 결합적이다: `append(append(A,B),C) = append(A,append(B,C))`.
가방(bag)교환성을 갖는다: `append(B,A) = append(A,B)`.
집합멱등성을 갖는다: `append(A,A) = A`.



데이터 접근은 세 가지 연산에 대한 패턴 매칭으로 지정할 수 있다. 예를 들어, 이러한 컨테이너에 대한 `member` 함수는 다음과 같다.

`member(X,single(Y)) = eq(X,Y)`
`member(X,null) = false`
`member(X,append(A,B)) = or(member(X,A), member(X,B))`



함수는 자료형에 대한 관련 규칙 하에서 불변해야 한다. 선택된 방정식의 하위 집합에 의해 암시된 각 동치 클래스 내에서, 모든 구성원에 대해 동일한 결과를 생성해야 한다.

7. 5. 추상 자료형으로서의 유리수 (일본어 문서)

유리수는 컴퓨터에서 그대로 다룰 수 없다. 유리수의 추상 자료형은 다음과 같이 정의할 수 있다.

'''생성자''': 두 정수 a, b를 사용하여 유리수의 추상 자료형 인스턴스를 생성한다. 여기서 a는 분자이고 b는 분모이다.

'''함수''': 덧셈, 뺄셈, 곱셈, 나눗셈, 지수 계산, 비교, 약분, 실수로의 변환

완전한 설명을 위해서는 각 함수는 데이터에 대해 기술되어야 한다. 예를 들어, 유리수 a/b와 c/d를 곱할 때 결과는 ac/bd로 정의된다. 일반적으로 입력, 출력, 실행 전 조건, 실행 후 조건, 추상 자료형에 대한 가정도 기술된다.

참조

[1] 웹사이트 Reading 10: Abstract Data Types https://web.mit.edu/[...] MIT
[2] 서적 Fundamentals of Algebraic Specification 1 - Equations and Initial Semantics Springer-Verlag
[3] 서적 Universal Algebra for Computer Scientists Springer-Verlag
[4] 서적 Abstract Algebra Springer
[5] 간행물 Al Stevens Interviews Alex Stepanov http://www.sgi.com/t[...] 2015-01-31
[6] 웹사이트 axiomatic semantics https://xlinux.nist.[...] 2023-11-25
[7] 간행물 The Boom Hierarchy 1994
[8] conference Design and Implementation of Abstract Graphical Data Types 1979
[9] 서적 Algorithms in C https://archive.org/[...] Addison/Wesley
[10] 문서 データ抽象
[11] 문서 言語に応じて名称が異なり、C++であればメンバ関数（member function）、Javaであればメソッド（method）と呼ばれる
[12] 문서 データ型の値に相当するこのまとまりのことを抽象データ型の実体（インスタンス , instance）と呼ぶ。


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com