추상 자료형과 알고리즘 (빅-오 표기법)

728x90

반응형

SMALL

 

추상화

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

 

알고리즘

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

 

빅-오 표기법 

어떤 알고리즘이 다루게 될 요소(item)의 개수와 연관된 복잡도(Complexity)를 표현하는 방법이다.

---

01. 추상 자료형

1. 뇌의 추상화 기능

 

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

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

컴퓨터에서 복잡한 내용을 단순하게 추상화를 시켜서 프로그래밍하기 쉽게 해주는 작업이 추상화 작업이다.

---

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

큰 문제를 잘게 잘라서 하나로 해결할 수 있는 방법도 있고,

잘게 잘라진 문제를 하나로 이어서 문제를 해결하는 방법도 있다.

 

어떤 문제냐에 따라서 조금 더 단순화할 수 있는 방법을 찾아서 해결하는 것이

컴퓨터를 이용한 문제해결의 좋은 추상화 방법이다.

---

1. 자료 추상화 (Data Abstraction)

처리할 자료, 그 자료들을 이용한 연산, 자료형에 대한 추상화 표현

이런 것들을 다 자료 추상화라고 한다. 

자료	- 프로그램의 처리 대상이 되는 모든 것을 의미한다. - 어떤값(Value) 자체를 의미하기도 한다. - 어떤값의 연산도 자료에 포함이 되어진다.
연산	어떤 일을 처리하는 과정으로 연산자를 사용하여 수행된다. ex. 더하기 연산은 +연산자에 의해 수행된다.
자료형	- 처리할 자료의 집합과 자료에 대해 수행할 연산자의 집합 - 자료형을 정의할때는 자료형에 속하는 값과 이를 처리하기 위해 사용할 수 있는 연산자를 정의한다.

 

예를 들면 정수 자료형인 경우

음수, 0, 양수와 정수를 갖고 처리할 수 있는 연산자들을 같이 포함한 것 

---

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

1. 추상 자료형이란?

자료형을 정의하려면

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

---

2. 추상화와 구체화

추상화

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

 

구체화

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

 

예) 철수

추상화 : 철수의 기본적인 특징, 대표적인 특징이 "무엇"을 나타낼 수 있어서 그것이 추상화이고

구체화 : 철수에 대해서 자세히 설명할 수 있는게 구체화이다.

---

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

그래서 컴퓨터에서 프로그래밍을 할때 데이터를 어떻게 코딩할 것인지에 따라서 자료형이 달라지게 된다.

 

추상화 개념에서 동그란 링이 있어서 아 저건 "고리"구나 라고 파악할 수 있다. 

즉, 전체적인 특징 하나는 추상 자료형을 표현하고 

 

이 고리를 어디에 쓰느냐에 따라서

귀에다가 사용하면 귀걸이가 될 수도 있고,

코에다가 사용하면 코걸이가 될 수도 있고,

배꼽에다가 사용하면 배꼽걸이가 될 수도 있다.

그래서 어떻게 사용하는지에 따라서 표현되어지는 방법을 구체화라고 이야기한다. 

 

자료의 특성과 연산을 표현한 추상 자료형을

C 프로그램으로 표현을 했을 때

C++ 프로그램으로 표현을 했을 때

Java 프로그램으로 표현을 했을 때 

달라지게 된다.

---

 

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

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

 

추상화는 자료를 추상 자료형이라고 한다. 연산자는 알고리즘 정의로 나타낸다.

완벽한 프로그햄이 아니라. 이것이 어떤 프로그램인지, 무엇인지만 나타내는 추상적인 개념으로 나타낸 것이다.

이것을 실제 프로그램에 돌아갈 수 있게끔 구체화시킨 게 프로그램 구현이 된다. 

 

구체화에서의 자료는 자료형 데이터타입이 된다.

자료를 가지고 연산 처리해 주는 연산자를 추상화에서는 알고리즘 정의 구체화에서는 프로그램 구현이라고 한다.

---

02. 알고리즘 개념

1. 알고리즘이란?

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

효과적이고 정확하게 문제를 해결하려면 자료를 정의하고 그 자료를 철하기에(파일사용하기에) 적당한 알고리즘을 작성해야 프로그램 구현단계가 쉬워진다. 

---

2. 알고리즘의 조건

입력 (Input)	알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수 있어야 한다.
출력 (Output)	알고리즘 수행 후 하나 이상의 결과를 출력해야 한다.
명확성 (Definiteness)	수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세되어야 한다.
유한성 (Finiteness)	알고리즘은 수행 뒤에 반드시 종료되어야 한다.
효과성 (Effectiveness)	알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 한다. 즉 효과가 있어야 된다.

---

요리 재료 = 컴퓨터의 자료

요리 재료를 다루는 방법 = 자료에 대한 연산

케이크를 만드는 과정을 기술한 전체적인 요리법 = 알고리즘

---

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

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

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

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

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

---

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

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

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

---

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

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

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

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

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

 

만약 프로그래밍 언어를 이용해서 구체화를 할 경우

구체화할 연어도 같은 프로그래밍 언어인지 먼저 파악을 한 다음에 해야 된다.

---

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

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

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

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

 

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

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

 

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

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

그래서 가상코드를 이용한 추상화 방법이 자주 사용된다.

---

가상코드의 형식의 기본 요소

기호	변수, 자료형 이름, 프로그램 이름, 레코드 필드 명, 문장의 레이블 등을 나타낸다. - 문자나 숫자를 조합한 것으로 첫 글자는 반드시 영문자로 사용 - 문장의 레이블 다음에는 콜론(:)을 입력해 수행할 문장과 구분한다.
자료형	정수형과 실수형의 수치 자료형, 문자형, 논리형, 포인터, 문자열 등의 모든 자료형을 가상코드 기본 요소로 사용되어진다.
연산자	산술연산자, 관계연산자, 논리연산자
조건문	조건에 따라 실행할 명령문이 결정되는 선택적 제어구조를 만든다.
다단계 조건문	if문을 중첩해서 사용할 수 있다.
case 문	여러 조건식 중에서 해당 조건을 찾아서 그에 대한 명령문을 수행 중첩 if문으로 표현 가능하다.
반복문	일정한 명령을 반복 수행하는 루프(loop) 형태의 제어구조 반복문의 종류 for, while-do, do-while문
반복문 for	for문의 형식과 제어흐름  처음의 초기값이 조건식에 맞으면 명령문을 처리하고 다시 반복을 한다.
반복문 while- do	조건식을 검사하여 조건식이 참인 동안 명령문을 반복하여 수행함
반복문 do-while	조건이 참이 아니더라도 명령문이 한번은 수행된다.
함수문	처리작업 별로 모듈화하여 만든 부프로그램이다. - 어떤  문제를 처리하는 프로그램을 만들 때 프로그램을 한 개로 구성하는 것 보다 처리할 작업별로 모듈화하여 작은 단위프로그램을 여러 개 구성하는 것이 좋을 수 있다. - 전체 프로그램 중 같은 작업은 하나의 단위 프로그램에서 독립적으로 수행하게 되면 프로그램 크기가 줄어들고 수정과 관리가 쉬울 뿐만 아니라 다른 프로그램에서도 단위 프로그램을 재사용할 수 있다.   함수는 - 함수를 호출했을 때 독립적으로 실행되며 매개변수를 사용하여 다른 함수나 프로그램을 서로 연결해주는 역할도 한다. - 그래서 함수는 다른 함수와 연결하게 해주는 인터페이스 역할을 해주는 매개변수로 사용할 수도 있고, 그리고 함수를 호출한 그곳에 결과값을 반환할 수 있는 구조를 가지게 된다.
함수문 return	return 문은 함수의 실행 결과값을 함수를 호출한 위치로 반환한다 반환하고 난 다음에 End문은 함수 실행을 마친다.

---

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

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

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

정확성	올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력을 했는지 안했는지 여부를 판단한다.
명확성	알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었느냐를 말한다.
수행량	기본적으로 포함되는 일반적인 연산은 제외하고 알고리즘 특성 나타내는 중요 연산을 모두 분석 해야 한다.  그래서 수행량이 많은지 적은지 파악이 되어져야 한다.
메모리 사용량	사용하는 명령어, 변수, 입출력 자료와 정보를 저장하기 위해 메모리 사용 이 메모리의 사용량이 많냐 적냐도 알고리즘 성능 분석 기준이 되어진다.
최적성	가장 중요한것이다. 가장 좋은 알고리즘은 조건에 맞는 "최적의" 알고리즘이라고 할 수 있다. 사용자가 원하는 조건에 맞는, 원하는 결과를 나타내는 최적성이 최적의 알고리즘을 나타낸다.

---

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

공간 복잡도와 시간 복잡도 두 가지를 이용해서 알고리즘을 평가한다.

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

---

1. 공간 복잡도

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

고정공간	프로그램 크기나 입출력 회수와 상관없이 고정적으로 필요한 저장공간으로 프로그램 저장 공간과 변수 및 상수를 저장하는 공간
가변공간	실행과정에서 사용되는 자료와 변수를 저장하는 공간, 함수를 실행하는데 관련 있는 정보를 저장하는 공간

---

2. 시간 복잡도

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

컴파일 시간	프로그램마다 거의 고정적인 시간 소요가 된다. 우리가 작성한 프로그램을 컴퓨터가 이해할 수 있는 2진수 형태로 변환하는 과정을 컴파일 과정이라고 한다. 그 과정에 드는 시간이 컴파일 시간이다.
실행 시간	컴파일이 다 되어졌으면 실제 실행되는 시간 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 시간이 계산되어진다.
실행 빈도수의 계산	지정문, 조건문, 반복문 내의 제어문과 반환문은 실행시간 차이가 거의 없으므로 하나의 단위시간을 갖는 기본 명령문으로 취급한다.  그래서 이런 기본 명령문들의 횟수를 카운트해서 시간 복잡도를 계산할 수 있다.

---

3. 알고리즘 성능 분석 표기법

시간복잡도를 정확히 계산할 수 있다면

'빅-세타 표기법'을 사용하는 게 제일 좋다.

 

시간 복잡도를 정확히 분석하기 어렵다면

상한을 구하여 '빅-오 표기법'으로 사용하거나 하한을 구하여 빅-오메가 표기법을'' 사용한다.

 

일반적으로 최악의 경우를 고려한 해결책을 찾기 때문에

'빅-오 표기법'을 주로 사용한다. 

 

1. 빅-오 표기법

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

- 함수의 상한을 나타내기 위한 표기법이다.

- 최악의 경우에도 수행 시간 안에는 알고리즘 수행 완료를 보장하는 형태가 빅-오 표기법이다.

 

먼저 실행 빈도수를 구하여

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

---

2. 빅-오메가 표기법

Ω(f(n))과 같이 표기, "BIg Omega of f (n)"으로 읽는다.

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

 

어떤 알고리즘의 시간 복잡도가 Ω(f(n))으로 분석되었다면,

이 알고리즘 수행에는 적어도 f(n)의 수행 시간이 필요함을 의미한다.

---

3. 빅-세타 표기법

θ(f(n))과 같이 표기, "Big Theta of f (n)"으로 읽는다.

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

---

각 실행 시간 함수에서 n값의 변화에 따른 실행 빈도수 비교

n값이 커질수록 타임이 커지는 것을 알 수 있다. 

2의 n승 형태의 실행빈도수가 기하급수적으로 늘어나는 것을 확인할 수 있다.

---

시간 복잡도에 따른 알고리즘 수행 시간 비교

2의 n승은 입력크기가 1,000이 될 때 3 곱하기 10의 283년이나 걸리고

그 이후는 너무 길어져서 불필요한 분석이라 표현하지 않았다 한다. 

 

이렇게 시간 복잡도를 이용해서

알고리즘 수행 시간을 비교하면서 좋은 알고리즘인지 아닌지 성능 분석을 할 수 있다.

---