추상 자료형과 자료구조

3. 추상 자료형과 자료구조#

슬라이드

본문 내용을 요약한 슬라이드를 다운로드할 수 있다.

3.1. 알고리즘과 자료구조#

3.1.1. 알고리즘#

알고리즘은 주어진 문제의 모든 사례에 대해 동일하게 작동하는 단계별 명령의 목록, 쉽게 말해 컴퓨터 프로그램을 의미한다. 문제를 해결하는 알고리즘이 존재할 경우 계산 가능하다computable 라고 말한다.

문제 하나에 대해 다양한 알고리즘이 존재할 수 있다. 그리고 특정 알고리즘을 실행할 때 적절한 시간 내에 실행이 멈추지 않거나 메모리를 너무 많이 사용해서 프로그램이 제대로 실행하지 않을 수도 있다.

또한 문제를 해결하는 알고리즘은 하나의 특정 프로그래밍언어로만 구현될 수 있는 것은 아니다. 실제로 하나의 프로그래밍언어로 구현될 수 있는 알고리즘은 일반적으로 다른 프로그래밍언어로도 구현될 수 있다. 다만 사용되는 프로그래밍언어의 특성에 따라 구현 방식이 달라지고, 그에 따라 알고리즘의 성능이 다를 수 있다.

주어진 문제를 해결하는 알고리즘을 특정 프로그래밍언어로 구현하려면 다음 두 가지가 요구된다.

  • 문제의 사례들을 표현하는 데에 필요한 자료구조

  • 문제 해결에 필요한 알고리즘 작성에 필요한 명령문

3.1.2. 자료구조#

자료구조는 프로그램 내에서 데이터를 어떻게 구성하고, 저장하고, 다룰 수 있는지를 정의한다. 자료구조를 잘 이해하면 자료를 효과적으로 활용하는 알고리즘을 개발할 수 있다.

대부분의 프로그래밍언어는 정수, 부동소수점, 부울값 등 기본 자료형 이외에 아래 데이터들에 대한 자료구조를 제공한다.

  • 리스트/어레이

  • 튜플

  • 문자열

반면에 알고리즘 작성에 필수적인 명령문은 다음과 같다.

  • 변수 할당

  • 조건문: if...else... 등

  • 반복문: for, while 등

원칙적으로는 앞서 언급된 기본 자료구조와 명령문만을 이용하여 컴퓨터로 해결이 가능한 모든 문제에 대한 알고리즘을 구현할 수 있다. 하지만 문제를 보다 효율적인 알고리즘으로 해결하려면 코드 추상화와 함께 고성능의 자료구조가 요구된다.

3.2. 코드 추상화#

프로그래밍에서는 많은 종류의 코드 추상화를 사용하지만 여기서는 절차 추상화와 데이터 추상화 두 종류만 언급한다.

절차 추상화

계산 가능한 문제를 해결하는 알고리즘은 적절한 API(Application Programming Interface)를 조합하여 작성한다. 하지만 각각의 API를 어떻게 구현하는가는 사용자 입장에서는 관심대상이 아니다.

예를 들어, 제곱근을 계산하는 함수 sqrt()는 math 모듈에 정의되어 있으며 아래와 같이 활용할 수 있다.

import math

math.sqrt(16)

4.0

즉, sqrt() 함수가 어떻게 정의되었는가는 모른 채 제곱근을 계산하는 함수라는 사실과 어떻게 활용하는가를 알기만 하면 된다.

이와 같이 해당 함수가 어떻게 구현되었는지 알지 못하더라도 함수의 기능만 알면 누구나 쉽게 활용할 수 있도록 프로그램을 구현하는 과정을 절차 추상화procedural abstraction라 부른다.

데이터 추상화

추상 자료형Abstract data type(ADT)은 특정 종류의 데이터와 그 데이터를 다루는 메서드를 하나로 묶어 다루는 방법을 묘사한다. 추상 자료형을 이용하여 적절한 자료구조를 정의하는 기법이 데이터 추상화data abstraction다.

클래스를 이용하여 자료구조가 데이터와 함께 관련 메서드를 하나로 묶어 처리하도록 한다는 의미에서 데이터 추상화를 데이터 캡슐화data encapsulation라고 부르기도 한다.

3.3. 추상 클래스, 추상 메서드, 자료구조#

파이썬은 이를 위해 클래스를 활용한다. 사용자의 입장에서 클래스로 선언된 자료구조가 구체적으로 어떻게 구현되었는가는 중요하지 않다. 대신에 해당 자료구조가 담고 있는 데이터가 무엇인가와 데이터를 다루는 메서드의 기능을 어떻게 활용할 수 있는가만 알면 된다.

추상 클래스abstract class는 추상 자료형에서 명시된 값의 저장 방식과 저장된 값들을 처리하는 필수 기능을 담당하는 메서드 일부를 구체적으로 구현하지 않은 채로 선언하는 클래스다. 이때 본문이 구현되지 않은채로 선언되는 메서드를 추상 메서드abstract method라 부른다.

반면에 자료구조data structure는 추상 클래스를 상속하면서 동시에 구현되지 않은 메서드를 모두 구체적으로 구현한 클래스다. 즉, 추상 자료형에서 묘사된 모든 기능을 실제로 활용될 수 있도록 선언된다.

추상 자료형과 자료구조를 분리해서 다루는 이유는 데이터 추상화를 이용하면 다루고자 하는 데이터의 기본 속성과 사용법의 핵심을 보다 쉽게 전달할 수 있기 때문이다. 해당 추상 자료형을 어떻게 하나의 자료구조로 구현할 것인가는 경우에 따라 부차적인 문제일 수 있다.

물론 문제를 해결하는 알고리즘을 구현하려면 적절한 추상 자료형을 구체적인 자료구조로 구현해야 한다. 하지만 구현된 자료구조의 활용법은 해당 추상 자료형의 기본 속성과 API들의 기능을 이해하는 것으로 쉽게 이해될 수 있다.

Contents