추상적 자료형
Python-기본 과정에서 파이썬에서 지원하는 내장 데이터 타입(data type, 자료형)에 대해서 다뤘습니다. 자료형이란 여러 종류의 데이터를 식별하는 분류로 생각할 수 있으며 더 나아가
1. 해당 자료형에 가능한 값
2. 해당 자료형에서 수행이 가능한 명령들
3. 해당 자료형을 저장하는 방식
을 의미합니다.
데이터란 어떠한 형태를 가지며 비슷한(혹은 공통된) 특징을 갖는 데이터를 하나로 묶어서 개념적으로 생각할 수 있습니다. 우리가 '정수'의 정확한 정의를 모르더라도 -1, 3, 12, -145, 5930, ... 등의 값을 보면 정수라는 것을 알 수 있습니다. 또한 개념적으로 정수 사이에 어떠한 연산이 수행 가능한지도 알고 있습니다. 이렇듯 무수히 많은 데이터 사이에는 분류가 가능한 논리적/개념적 기준이 있으며 같은 논리적/개념적 기준으로 분류되는 데이터들은 공통된 수행 가능한 명령(operation)들을 갖습니다.
추상적 자료형(ADT, Abstract Data Type)이란 이런 데이터 타입의 개념을 좀 더 추상화시킨 것입니다. 우리는 이미 숫자형, 문자열, 리스트, 튜플, 셋, 딕셔너리 등의 데이터 타입에 대해서 배웠습니다. 그러나 프로그래밍을 하다보면 해당 자료형보다 더 복잡하지만 자료를 보관하는데 훨씬 효율적이고 강력한 성능을 갖는 자료형이 필요할 때가 있습니다. 이렇게 문제 상황 해결 및 목적에 맞는 자료 자체의 형태와 그 자료에 관계된 연산들을 고려하여 적합한 자료형을 개념적으로 생각해볼 수 있습니다. 이러한 자료형을 추상적 자료형이라 합니다.
"자료 자체의 형태와 그 자료에 관계된 연산들을 수학적으로만 정의한 것"
즉, 자료가 어떤 형태로 저장되며 자료의 삽입/삭제/탐색 등 필요한 작업은 어떠한 것이 있는지 정의만 한 것이 바로 추상적 자료형입니다. 실제로 프로그래밍적으로 해당 자료가 어떤 형태를 갖고 각 작동은 어떻게 구현할지를 고민하는 것, 다시 말해 추상적 자료형을 구체적으로 어떻게 구현하는가에 대해서 고민하고 정리하는 것은 자료 구조(data structure)의 영역입니다.
추상적 자료형 중 선형 자료 구조의 대표적인 예인 스택(stack)에 대해 생각해봅니다. 어렵게 생각하지 말고, 리스트, 튜플 등과 같이 '스택'이라는 자료형이 있다고 생각하면 됩니다. 스택은 다음과 같은 속성을 갖는 자료형입니다.
1. 후입선출(LIFO, Last In First Out)의 특징을 갖는다.
2. 다음의 작동(operation) 메서드를 갖는다.
- 자료를 삽입하는 push
- 가장 마지막에 삽입된 자료를 꺼내는 pop
- 가장 마지막에 삽입된 자료를 조회하는 peek
- 스택이 비어 있는지 확인하는 empty
- 스택 내 자료의 수를 확인하는 size
'스택'이라는 자료형이 어떤 식으로 자료를 저장하고 꺼내며 어떠한 메서드들이 있는지를 정의하는 것. 여기까지가 추상적 자료형으로써 스택의 개념입니다. 어떻게 보면 '스택'이라는 클래스(class)를 정의하는 것과도 같습니다. 프로그래밍적 센스가 좋은 분은 저러한 기능을 갖는 클래스를 어떻게 구현할 지 금방 떠올리실 수 있을 겁니다. 아래의 코드는 리스트를 이용하여 스택 클래스를 구현한 것입니다.
| class Stack(object): def __init__(self): self.items = [] def push(self, value): self.items.append(value) def pop(self): value = self.items.pop() if value is not None: return value else: print("Stack is empty.") def peek(self): if self.items: return self.items[-1] else: print("Stack is empty.") def isEmpty(self): return not bool(self.items) def size(self): return len(self.items) |
리스트를 이용한 스택 클래스 구현
자료 구조
널리 알려진 추상적 자료형들에는 몇 가지가 있습니다. 이러한 추상적 자료형의 개념적인 형태와 동작들을 배우고 이를 구체적으로 구현하는 것이 자료 구조의 목표라 할 수 있습니다. 그렇다면 자료 구조를 배워야 하는 이유는 무엇일까요?
"자료 구조를 배워야 하는 이유는 효율적인 프로그램을 만들기 위함입니다."
- 자료 구조에 따른 성능 차이
- 메서드에 따른 성능 차이
세상이 발전하면서 컴퓨터의 성능도 비약적으로 발전하고 있지만 우리가 풀어야 하는 문제들의 크기와 복잡성도 커지고 있습니다. 문제가 복잡해질수록 더 강력한 컴퓨터 성능을 요구하며, 이는 곧 효율적인 프로그래밍의 필요성을 증가시킵니다.
‘자료 구조’를 가장 일반적으로 정의하면 다음과 같습니다.
"모든 데이터 표현(representation)과 이와 관련된 작동"
어떻게 보면 추상적 자료형과도 같은 개념으로 보입니다. 그도 그럴 것이 추상적 자료형을 구체화 시킨 것이 바로 자료 구조이기 때문입니다.
앞서 자료구조를 배워야 하는 이유가 효율적인 프로그램을 만들기 위함이라고 말씀드렸습니다. 서로 다른 자료 구조는 프로그램 구동 시간에 차이를 발생시키므로 적절한 자료 구조를 선택하는 것이 효율적인 프로그래밍을 가능케 합니다. 여기서 ‘효율’이란 다음을 말합니다.
효율: 필요한 자원 제한(resource restraint) 내에서 문제를 해결하는 것
자원(resource)은 데이터를 저장하는 데 이용되는 전체 공간 및 각 하위 업무를 수행하는데 필요한 시간을 말합니다. 즉, 효율적인 프로그래밍을 가능하게 하는 자료 구조란 데이터를 저장하는 데 이용되는 전체 공간이 작으며 하위 업무를 수행하는데 필요한 시간이 짧은 자료 구조를 말합니다.
이를 위해서는 무엇보다도 먼저 해결하고자 하는 문제를 분석하는 과정을 거쳐야 합니다. 코더는 문제 분석 단계를 거치지 않고 문제 해결에 부적합할 지라도 자신에게 익숙한 자료 구조를 사용합니다. 하지만 프로그래머는 문제를 분석하고 효율적인 프로그래밍을 위한 자료 구조를 선택합니다.
자료 구조를 선정하는 단계는 다음과 같습니다.
1. 반드시 지원해야 하는 기본적인 하위 작동(operation)을 결정하기 위해 문제를 분석합니다.
- 데이터 항목을 자료 구조에 삽입할 수 있어야 하는가?
- 자료 구조에서 데이터 항목을 삭제할 수 있어야 하는가?
- 지정된 데이터 항목을 검색/탐색할 수 있어야 하는가?
2. 각 동작에 대한 자원 제한(resource restraint)을 정량화합니다.
3. 이러한 요구 사항에 가장 적합한 자료 구조를 선택합니다.
일반적으로 핵심 작동에 관련된 자원 제한이 자료 구조 선정을 결정합니다. 핵심 작동이란 자료 구조가 가져야 하는 하위 작동 중 상대적으로 중요한 작동을 말하며 이러한 하위 작동의 상대적 중요성은 다음과 같은 고려 사항을 필요로 합니다.
- 삽입: 모든 항목이 처음에 자료 구조에 삽입되는지/삽입이 다른 동작들에 산재되어 있는지
정적 어플리케이션은 데이터가 처음에 로드되고 변경되지 않는 프로그램을 말합니다. 이는 동적 어플리케이션보다 효율적인 구현을 위해서 더 간단한 자료 구조가 필요합니다.
- 삭제: 데이터 항목의 삭제 기능을 꼭 넣어야 하는지
삭제 기능은 구현이 복잡하기 때문에 고려되어야 하는 요소입다.
- 정렬: 모든 데이터 항목이 잘 정의된 순서대로 처리되는지/특정 데이터 항목 검색이 허용되는지
“Random access” 검색에는 일반적으로 더 복잡한 자료 구조가 필요합니다.
다음 글에서는 추상적 자료형과 이를 구체화 시킨 자료 구조에 대해서 하나씩 정복해가도록 해봅시다.