자료구조와 알고리즘 (1)
다음 글은 위 책을 공부하면서 정리한 내용이다.
1. 자료구조와 알고리즘
자료구조란?
사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있다. 이를 자료 구조(data structure)라 부른다. 컴퓨터 프로그램을 흔히 자료구조 + 알고리즘으로 이루어져 있다고한다.
알고리즘이란?
컴퓨터로 문제를 풀기 위한 단계적인 절차, 엄밀하게 이야기하면 알고리즘이란 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것이다.
따라서 알고리즘에는 입력은 없어도 되지만 출력은 반드시 하나이상 있어야 하고 모호한 방법으로 기술된 명령어들의 집합은 알고리즘이라 할 수 없다. 또한 실행할 수 없는 명령어(ex. 0으로 나누는 연산)를 사용하면 역시 알고리즘이 아니다. 또한 무한히 반복되는 명령어들의 집합도 알고리즘이 아니다.
2. 추상 자료형
자료형 : 데이터의 종류 (ex. 정수, 실수, 문자열)
자료형은 프로그래밍 언어가 기본적으로 제공한다. 이 책에서 앞으로 기본적으로 제공되는 자료형 이외에도 스택, 큐, 리스트, 트리와 같은 새로운 자료형들을 공부할 것이다.
C언어에서 제공하는 자료형에는 정수, 실수, 문자를 나타내는 기초적인 자료형도 있고 다른 자료형을 묶을 수 있는 배열이나 구조체도 있다.
추상 자료형(abstract data type) : 추상적, 수학적으로 자료형을 정의한 것.
자료구조는 이러한 추상 자료형을 프로그래밍 언어로 구현한 것이라 할 수 있다.
소프트웨어 개발과 유지보수에 있어서 가장 중요한 이슈는 "어떻게 소프트웨어 시스템의 복잡성을 관리할 것인가"이다. 이러한 복잡성에 대처하기 위한 새로운 아이디어들이 등장하였고 그 중 유력한 주제가 추상화(abstraction)와 관련된 도구들의 개발이었다. 추상화란 어떤 시스템의 간략화된 기술 또는 명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것이다.
다시 말하면, 추상 자료형(ADT)은 실제적인 구현으로부터 분리되어 정의된 자료형을 말한다. 즉 자료형을 추상적(수학적)으로 정의함을 의미한다. 추상 자료형에서는 데이터나 연산이 무엇인지는 정의되지만 데이터나 연산을 어떻게 컴퓨터 상에서 구현할 것인지는 정의되지 않는다. 예를 들어 연산을 정의할 때 연산의 이름, 매개 변수, 반환형은 정의하지만 연산을 구현하는 구체적인 코드는 주어지지 않는 것이다. 다만 연산을 정의하는 추상적인 의사 코드는 주어질 수 있다.
추상 자료형이 구현될 때 보통 구현세부사항은 외부에 알리지 않고 외부와의 인터페이스만을 공개하게 된다. 추상 자료형의 사용자는 구현세부사항이 아닌 인터페이스만 사용하기 때문에 추상 자료형의 구현 방법은 언제든지 안전하게 변경될 수 있다. 구현으로부터의 명세의 분리가 추상 자료형의 중심 아이디어이다.
객체지향언어에서는 "클래스"개념을 사용하여 추상 자료형이 구현된다. 객체지향언어에서는 private나 protected 키워드를 이용하여 내부 자료의 접근을 제한할 수 있다. 또한 클래스는 계층구조(상속)로 구성될 수 있다.
참고
- C언어로 쉽게 풀어쓴 자료구조 책