[88] 자료구조 03차시 추상 자료형과 알고리즘

1. 추상 자료형

가. 뇌의 추상화 기능

기억할 대상의 구별되는 특징만을 단순화하여 기억하는 기능

철수를 기억하기 위해 철수에 대한 모든 정보를 구체적이고 세세하게 저장하기는 어려움.

그 대신 철수를 다른 사람과 구별할 수 있는 철수만의 특징을 찾아서 기억함.

자세하고 복잡한 것 대신 필수적이고 중요한 특징만 골라서 단순화시키는 작업이 추상화 작업임.

나. 컴퓨터를 이용한 문제해결에서의 추상화

크고 복잡한 문제를 단순화시켜 쉽게 해결하기 위한 방법

1) 자료 추상화(Data Abstraction)

처리할 자료, 연산, 자료형에 대한 추상화 표현

2) 자료

프로그램의 처리 대상이 되는 모든 것을 의미

어떤 값(Value) 자체를 의미하기도 함.

3) 연산

어떤 일을 처리하는 과정으로 연산자를 사용하여 수행됨.

4) 자료형

처리할 자료의 집합과 자료에 대해 수행할 연산자의 집합

자료형을 정의할 때는 자료형에 속하는 값과 이를 처리하기 위해 사용할 수 있는 연산자를 정의함.

다. 추상 자료형(ADT, Abstract Data Type)

1) 추상 자료형이란?

자료형을 정의하려면 구체적으로 구현하기 전에 자료형에 대한 자료의 특성, 연산자, 연산자가 무엇을 수행하는지 등 자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형

2) 추상화와 구체화

추상화 - "무엇(What)인가?"를 논리적으로 정의

구체화 - "어떻게(How) 할 것인가?"를 실제적으로 표현

3) 같은 사물이라도 "어떻게(How) 쓰느냐"에 따라 용도가 달라짐.

 

기본틀: "고리"는 추상화된 기본틀

구체화: 기본틀을 용도에 맞게 귀걸이나 코걸이로 사용하는 것

4) 자료와 연산에 있어서의 추상화와 구체화의 관계

구분	자료	연산자
추상화	추상 자료형	알고리즘 정의
구체화	자료형	프로그램 구현

2. 알고리즘 개념

가. 알고리즘이란?

주어진 문제해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서

효과적이고 정확하게 문제를 해결하려면 자료를 정의하고 그 자료를 처리하기에 적당한 알고리즘을 작성해야 함.

1) 입력(Input)

알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수 있어야 함.

2) 출력(Output)

알고리즘 수행 후 하나 이상의 결과를 출력해야 함.

3) 명확성(Definiteness)

수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세되어야 함.

4) 유한성(Finiteness)

알고리즘은 수행 뒤에 반드시 종료되어야 함.

5) 효과성(Effectiveness)

알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 함.

나. 알고리즘의 표현 방법의 종류

1) 자연어를 이용한 서술적 표현 방법

알고리즘을 사람이 쓰는 자연어로 표현하는 방법

자연어는 서술적일 뿐만 아니라 쓰는 사람에 따라 일관성이나 명확성을 유지하기 어려움.

따라서 누구라도 쉽게 이해하고 쓸 수 있어야 하는 알고리즘을 표현하는데 한계가 있음.

2) 순서도(Flow chart)를 이용한 도식화 표현 방법

알고리즘을 순서도를 작성하는 규칙에 따라 도식화하는 방법

순서도를 이용하면 명령의 흐름을 쉽게 파악할 수 있지만 복잡한 알고리즘을 표현하는 데는 한계가 있음.

3) 프로그래밍 언어를 이용한 구체화 방법

알고리즘을 프로그래밍 언어를 사용하여 표현하는 방법

이 방법을 사용하면 알고리즘 자체가 구체화되므로 추가로 구체화 작업을 할 필요가 없음.

하지만 특정한 프로그래밍 언어로 작성하기 때문에 해당 언어를 모르면 이해하기 어려움.

다른 프로그래밍 언어로 프로그램을 개발하는 경우에는 알고리즘을 번역하고 다른 프로그래밍 언어로 변환해야 하므로 비효율적임.

4) 가상코드(Pseudo-code)를 이용한 추상화 방법

알고리즘을 프로그래밍 언어로 표현했을 때 생기는 단점을 보완하는 방법

특정 프로그래밍 언어는 아니지만 프로그래밍 언어의 형태를 갖춘 가상코드를 사용하여 알고리즘을 표현함.

가상코드는 프로그래밍 언어가 아니므로 직접 실행할 수 없지만, 형태가 일반적인 프로그래밍 언어와 유사하기 때문에 원하는 특정 프로그래밍 언어로 변화(구체화 작업)하기가 쉬움.

다. 순서도를 이용한 도식화

순서도는 특정 기호를 사용하여 알고리즘의 실행 단계를 표현함.

https://ko.wikipedia.org/wiki/순서도

순서도 - 위키백과, 우리 모두의 백과사전

라. 가상코드를 이용한 추상화

가상코드는 의사코드 또는 알고리즘 기술언어(ADL, Algorithm Description Language)로도 부름.

의사코드를 사용하여 프로그래밍 언어의 일반적인 형태와 유사하게 알고리즘을 표현

특정 프로그래밍 언어가 아니므로 직접 실행은 불가능

일반적인 프로그래밍 언어의 형태이므로 원하는 특정 프로그래밍 언어로의 변환 용이

1) 기호

변수, 자료형 이름, 프로그램 이름, 레코드 필드명, 문장의 레이블 등을 나타냄.

문자나 숫자를 조합한 것으로 첫 글자는 반드시 영문자로 사용

문장의 레이블 다음에는 콜론(:)을 입력해 수행할 문장과 구분함.

2) 자료형

정수형과 실수형의 수치 자료형, 문자형, 논리형, 포인터, 문자열 등의 모든 자료형을 사용

3) 연산자

산술연산자, 관계연산자, 논리연산자

4) 조건문

조건에 따라 실행할 명령문이 결정되는 선택적 제어구조를 만듦.(if, then, else)

5) case문

여러 조건식 중에서 해당 조건을 찾아서 그에 대한 명령문을 수행

중첩 if 문으로 표현 가능

6) 반복문

일정한 명령을 반복 수행하는 루프(loop) 형태의 제어구조

for, while-do, do-while 등이 있음.

7) 함수문

처리작업 별로 모듈화하여 만든 부프로그램

어떤 문제를 처리하는 프로그램을 만들 때 프로그램을 한 개로 구성하는 것보다 처리할 작업 별로 모듈화하여 작은 단위 프로그램을 여러 개 구성하는 것이 좋을 수도 있음.

전체 프로그램 중 같은 작업은 하나의 단위 프로그램에서 독립적으로 수행하게 되면 프로그램 크기가 줄어들고 수정과 관리가 쉬울 뿐만 아니라 다른 프로그램에서도 단위 프로그램을 재사용할 수 있음.

함수는 함수를 호출했을 때 독립적으로 실행되며 매개변수를 사용하여 다른 함수나 프로그램을 서로 연결함.

return 문은 함수의 실행 결과값을 함수를 호출한 위치로 반환함.

end 문은 함수 실행을 마침.

https://ko.wikipedia.org/wiki/의사코드

의사코드 - 위키백과, 우리 모두의 백과사전

3. 알고리즘 성능 분석 방법

가. 알고리즘 성능 분석 기준

기준에는 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등이 있음.

1) 정확성

올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부

2) 명확성

알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었냐를 말함

3) 수행량

기본적으로 포함되는 일반적인 연산은 제외하고 알고리즘 특성을 나타내는 중요 연산을 모두 분석해야 함.

4) 메모리 사용량

사용하는 명령어, 변수, 입출력 자료와 정보를 저장하기 위해 메모리 사용

5) 최적성

가장 중요, 가장 좋은 알고리즘은 조건에 맞는 최적의 알고리즘이라고 할 수 있음.

나. 알고리즘 성능 분석 방법

일반적으로 실행에 필요한 공간 측면에서 분석하는 공간 복잡도와 실행에 소요되는 시간 측면에서 분석하는 시간 복잡도를 추정하여 평가함.

1) 공간 복잡도

알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양

공간 복잡도 = 고정 공간 + 가변 공간

고정 공간: 프로그램 크기나 입출력 횟수와 상관없이 고정적으로 필요한 저장 공간으로 프로그램 저장 공간과 변수 및 상수를 저장하는 공간

가변 공간: 실행 과정에서 사용되는 자료와 변수를 저장하는 공간, 함수를 실행하는 데 관련 있는 정보를 저장하는 공간

2) 시간 복잡도

알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요 시간

시간 복잡도 = 컴파일 시간 + 실행 시간

컴파일 시간: 프로그램마다 거의 고정적인 시간 소요

실행 시간: 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행 시간 보다는 명령문의 실행 빈도수에 따라 계산

실행 빈도수 계산에서 지정문, 조건문, 반복문 내의 제어문과 반환문은 실행 시간 차이가 거의 없으므로 하나의 단위 시간을 갖는 기본 명령문으로 취급

https://ko.wikipedia.org/wiki/시간_복잡도

시간 복잡도 - 위키백과, 우리 모두의 백과사전

3) 빅-오 표기법

\(O(f(n))\)과 같이 표기, "Big Oh of f(n)"으로 읽음.

함수의 상한을 나타내기 위한 표기법

최악의 경우에도 수행 시간 안에는 알고리즘 수행 완료 보장

먼저 실행 빈도수를 구하여 실행 시간 함수 \(f(n)\)을 찾고, 이 함수값에 가장 큰 영향을 주는 \(n\)에 대한 항을 한 개 선택하여 계수는 생략하고 \(O\)의 오른쪽 괄호 안에 표시

4) 빅-오메가 표기법

\(\Omega(f(n))\)과 같이 표기, "Big Omega of f(n)"으로 읽음.

함수의 하한을 나타내기 위한 표기법

어떤 알고리즘의 시간 복잡도가 \(\Omega(f(n))\)으로 분석되었다면, 이 알고리즘 수행에는 적어도 \(f(n)\)의 수행 시간이 필요함을 의미

5) 빅-세타 표기법

\(\Theta(f(n))\)과 같이 표기, "Big Theta of f(n)"으로 읽음.

상한과 하한이 같은 정확한 차수를 표현하기 위한 표기법

\(f(n) = \Theta(g(n))\)이 되려면, \(f(n) = O(g(n))\)이면서 \(f(n) = \Omega(g(n))\)이어야 함.

 

시간 복잡도를 정확히 계산할 수 있다면 "빅-세타 표기법"을 사용함.

시간 복잡도를 정확히 분석하기 어렵다면 상한을 구하는 "빅-오 표기법"으로 사용하거나 하한을 구하여 "빅-오메가 표기법"을 사용함.

일반적으로 최악의 경우를 고려한 해결책을 찾기 때문에 "빅-오 표기법"을 주로 사용함.