자료구조와 알고리즘, 추상 데이터타입 개념

자료구조와 알고리즘

 

자료구조의 필요성

 

• 컴퓨터에서 처리할 자료들을 효율적으로 관리하기 위해 구조화
• 자료의 특성에 따라 자료의 형태를 구성하고 처리하고 저장

 

자료구조란?

 

자료를 효율적으로 처리할 수 있도록 자료를 조직화하고 체계적으로 구조화하여 표현한 것이다.

• 프로그램 = 자료구조 + 알고리즘

 

알고리즘이란?

• 해야 할 일을 컴퓨터가 수행하여야 할 단계적인 절차를 자세히 기술하는 것
• 컴퓨터로 문제를 풀기 위한 단계적인 절차
• 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것
• 특정한 일을 수행하는 명령어들의 집합(명령어란 컴퓨터에서 수행되는 문장들)

 

알고리즘의 조건

• 입력 : 0개 이상의 입력이 존재하여야 한다.
• 출력 : 1개 이상의 출력이 존재하여야 한다.
• 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.
• 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.
• 유효성 : 각 명령어들은 실행 가능한 연산이여야 한다.

 

알고리즘의 기술 방법

• 영어나 한국어와 같은 자연어
• 흐름도(flow chart)
• 의사 코드(pseudo-code)
• 프로그래밍 언어

 

 

추상 자료형

 

자료형이란 데이터의 종류로서, 정수, 실수, 문자열 등이 기초적인 자료형의 예이다.

 

 

자료형을 정의할 때에는 실행 가능한 연산에 대해서도 고려해야 한다.

 

 

• 자료형 = (데이터의 집합 + 연산의 집합)

 

 

추상 데이터 타입(ADT: Abstract Data Type)

데이터 타입을 추상적(수학적)으로 정의한 것이다.

데이터나 연산이 무엇(what)인가는 정의되지만 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의되지 않는다.

자료구조는 추상 자료형이 정의한 연산들을 구현체를 가리키고, 추상 자료형은 구현 방법을 명시하지 않다는 점에서 자료구조와 다르다.

예를 들어, 스택(Stack)의 형태는 LIFO 값들의 모임이고 push, pop, size 등의 연산을 정의할 수 있다. 그렇지만 스택이 내부적으로 배열로 구현되는지 연결 리스트로 구현되는지, 또는 size 연산을 수행할 때 원소의 개수를 일일이 세는지 아니면 개수를 따로 저장해 두는지와 같은 세부 사항들은 추상 자료형에서는 다루지 않으며, 그것을 다루는 것은 자료구조의 영역이다.

 

 

추상 데이터 타입의 유래

• 추상화(abstraction)
  • 추상화란 사용자에게 중요한 정보는 강조되고 반면 중요하지 않은 구현 세부 사항은 제거하는 것
  • -> 정보은닉기법(information hiding)
  • -> 추상 자료형(ADT)

 

추상 데이터 타입의 정의

• 객체
  • 추상 데이터 타입에 속하는 객체가 정의된다.
• 연산
  • 객체들 사이의 연산이 정의된다.
  • 연산은 추상 데이터 타입과 외부를 연결하는 인터페이스의 역할을 한다.

 

추상 자료형(ADT)

• 사용자들은 ADT가 제공하는 연산만을 사용할 수 있다.
• 사용자들은 ADT가 제공하는 연산들을 사용하는 방법을 알아야 한다.
• 사용자들은 ADT 내부의 데이터를 접근할 수 없다.
• 사용자들은 ADT가 어떻게 구현되는지 모르더라도 ADT를 사용할 수 있다.
• ADT의 구현을 변경하더라도 인터페이스가 변경되지 않으면 사용자들은 ADT를 같은 방식으로 사용할 수 있다.