[자료구조/알고리즘] 01. 추상 데이터 타입 ADT

CH 01 ADT(Abstract Data Type)

목표

본격적으로 자료구조를 알기 전에, Abstract Data Type(이하 ADT)를 알아봅시다.

목차

1. ADT란 무엇인가?
2. 지갑을 통한 ADT의 이해
3. ADT는 이렇게 씁시다
4. 결론

1. ADT란 무엇인가?

ADT를 번역하면 추상 자료형이라는 뜻입니다. 이는 구체적인 기능의 완성 과정은 서술하지 않고 오로지 순수하게 기능이 무엇인지만 나열하는 것을 말합니다. 추상 자료형에는 다음의 속성들을 가지고 있습니다.

1. Characters
2. Opertions

Characters는 추상 자료형의 내부 속성을 뜻합니다. 예를 들어서, 자동차라는 ADT가 존재한다면, 바퀴, 문, 핸들 등이 바로 이 ADT의 내부 속성입니다. 이들은 객체지향 프로그래밍(이하 OOP)에서 말하는 클래스의 내부 필드와 그 의미가 동일합니다. Operations는 추상 자료형의 연산을 뜻합니다. 마찬가지로 자동차라는 ADT에서 운전을 하다, 시동을 키다 등이 ADT의 연산이지요. 여기서 내부 중요한 것은 내부 구현을 정의하지 않는다는 것입니다. 그냥 운전을 하다라는 연산을 수행할 때 필요한 로직만 서술해도 좋습니다. 자 이제 다음 절을 통해서 ADT를 조금 더 깊게 이해해봅시다.

2. 지갑을 통한 ADT의 이해

위에서 자동차라는 예제를 간단하게 살펴보았지만, 아직 이해가 충분하지 않지요? 지금부터 지갑이라는 현실 세계의 물건을 가지고 Wallet 이라는 ADT를 만들어 보도록 하겠습니다. 먼저, 조금 더 쉽게 지갑을 정의하기 위해서 화폐는 만원과 오만원밖에 없다고 가정하도록 하겠습니다. 그럼 지갑은 무엇을 가질 수 있을까요? 맞습니다. 바로 10000원 짜리 지폐들과, 50000원 짜리 지폐들만 가질 수 있습니다. 이 때 지갑에 들어갈 10000원 짜리 지폐의 개수, 50000원 짜리 지폐의 개수가 바로 지갑의 내부 속성이 되겠지요. 정리하면 다음과 같습니다.

1. 10000원 짜리 지폐의 개수
2. 50000원 짜리 지폐의 개수

그럼 우리는 이 지갑을 가지고 무엇을 할 수 있을까요? 저는 다음의 일을 할 수 있을 것 같습니다.

1. 현재 지갑 속에 존재하는 지폐들의 총합을 구할 수 있습니다.
2. 비용에 대한 요금을 지불할 수 있습니다.
3. 돈을 지갑에 넣을 수 있습니다.

그리고 바로 이들이 지갑이라는 ADT의 연산이 되지요. 결국 자료구조는 현실 세계의 어떤 물건 혹은 개념에 대해서 내부 속성과, 연산을 정의하는 일입니다. OOP에 익숙하신 분들은 더 쉽게 ADT를 이해할 수 있을 겁니다. 자 이제 지갑이라는 ADT의 내부 속성과 연산에 대해 정의하였습니다. 우리가 할 일은 이제 ADT의 표준 양식을 작성하는 것이죠. 이것은 다음 절에서 알아봅시다.

3. ADT는 이렇게 씁시다

ADT의 표준이라고까지 할 것은 없지만, 대부분의 ADT는 속성/연산의 이름, 자료 형을 정의해주고 연산에 대해서는 내부 로직만 간단하게 서술해주면 됩니다. 구현은 ADT가 정의된 후에 하는 것이죠. 앞으로 자료구조 설명 이전에, ADT를 다음과 같이 먼저 정의하겠습니다. 다음은 우리가 분석한 지갑 Wallet의 ADT입니다.

ADT Wallet

• Characters:
  1. cntOf10000won: int
     • 지갑에 존재하는 10000원 지폐의 양
  2. cntOf50000won: int
     • 지갑에 존재하는 50000원 지폐의 양
• Operations
  1. GetCurrentTotalCash(wallet: Wallet *): int
     • wallet의 characters를 통해서 현재 지갑의 총 현금의 양을 반환합니다.
  2. PayMoney(wallet: Wallet *, cost: int): void
     • wallet의 characters를 통해서 cost에 해당하는 비용을 지불합니다.
     • 이 때 최대한 골고루 쓰는 것을 기본으로 하고, 거스름 돈을 포함해서 지폐의 개수를 갱신합니다.
  3. PutMoney(wallet: Wallet *, money: int): void
     • wallet의 characters를 통해서 money로 부터 지폐 개수를 갱신합니다.

4. 결론

자 이렇게 해서, ADT에 대한 설명을 마치도록 하겠습니다. 이해가 되셨나요? 처음에는 잘 이해하지 않으셔도 좋습니다. 앞으로 자료구조를 공부할 때 계속 ADT를 쓰니까 보다 보면 익숙해지실 겁니다. 본격적으로 자료구조에 대해 공부해봅시다.