![[자료구조] 자료구조와 Algorithm](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbT89eM%2FbtqyWXcrPkY%2FdrjDhIQuD2r1fkkhe0GF70%2Fimg.png)
알고리즘(Algorithm)의 정의
- 컴퓨터로 문제를 풀기 위한 단계적인 절차
- 9세기 페르시아의 수학자인 무하마드 알콰리즈미(Muhammad al-Kwarizmi)의 이름을 라틴어화한 algorismus에서 따온 말이다.
좋은 알고리즘(Algorithm)의 조건
- 입 력 : 0개 이상의 입력이 존재
- 출 력 : 1개 이상의 출력이 존재
- 명확성 : 각 명령어의 의미가 모호하지 않고 명확
- 유한성 : 한정된 수의 단계 후에는 반드시 종료
- 유효성 : 각 명령어들은 실행 가능한 연상
- 정밀성 : 변하지 않는 명확한 작업 단계
- 유일성 : 각 단계마다 명확한 다음 단계를 가짐
- 타당성 : 구현할 수 있고 실용적이어야 함
알고리즘(Algorithm)의 표현 방법
- 영어나 한국어와 같은 자연어
- 흐름도(Flow Chart)
- 유사 코드(pseudo-code)
- Programming 언어
=> 4가지 표현 방법으로 '배열에서 최대값 찾기 algorithm'에 대해 알아본다.
1. 자연어
- 장점 : 사람이 보기에 편하다. (읽기가 쉽다.)
- 단점 : 표현이 정확하지 않으면 의미 전달이 모호해진다. (읽기가 어렵다.)
배열에서 최대값 찾기
ArrMax(Arr)
1. 배열 Arr의 첫 번째 요소를 변수 tmp에 복사
2. 배열 Arr의 다음 요소들을 차례대로 tmp와 비교하면서 더 클경우 tmp로 복사
3. 배열 Arr의 모든 요소를 비교했으면 tmp를 반환
2. 흐름도(Flow Chart)
- 장점 : 직관적이고 이해가 쉬움
- 단점 : 알고리즘 자체가 복잡하다면 표현하기가 어려움 (표현해도 직관적으로 이해가 되지 않음)
3. 유사 코드(pseudo-code)
- 알고리즘의 고수준 기술 방법으로 자연어보다는 더 구조적이고, 프로그래밍 언어보다는 덜 구체적인 표현 방법
- 알고리즘에 있어 가장 많이 사용 됨
- 알고리즘의 핵심적인 내용에만 집중할 수 있다. (프로그램을 구현할 때의 다른 문제는 생각 X)
ArrMax(Arr)
tmp ← Arr[0];
for i ← 1 to Arr.Length do
if tmp < A[i] then
tmp ← A[i];
return tmp;
---
← 는 대입하겠다는 의미4. Programming 언어
- 가장 정확하고 구체적인 기술
- 구체적인 사항들이 algorithm의 핵심적인 내용의 이해를 방해할 수 있음
// 예시 C언어
#define MAX_LENGTH 100
int Arr[MAX_LENGTH];
int find_max_num() {
int i, tmp;
tmp = Arr[0];
for(i=1; i<(sizeof(Arr) / sizeof(int)); i++) {
if(Arr[i] > tmp) {
tmp = Arr[i];
}
}
return tmp;
}
Data Type
- Data의 집합과 연산의 집합
ADT (Abstract Data Type)
- data type을 추상적(수학적)으로 정의한 것
- data나 연산이 무엇(what)인가는 정의되지만 어떻게(how) 컴퓨터상에서 구현할 것인지는 정의되지 않음
ADT의 정의
- 객체 : Abstract Data Tpe에 속하는 객체가 정의됨
- 연산 : 이들 객체들 사이의 연산이 정의됨. 이 연산은 Abstract Data Type과 외부를 연결하는 interface의 역할을 함
자료 구조의 표현
1. 상수
=> 대문자로 표기
=> ex) #define MAX_ELEMENT 100
=> ex) #define PI 3.14
2. 변수의 이름
=> 소문자로 표기 및 단어와 단어사이엔 언더라인을 사용
=> ex) int count;
=> ex) int new_count;
3. 함수의 이름
=> 동사를 이용하여 함수가 하는 일을 표기
=> ex) int add(int a, int b) // 더하는 역할을 하는 함수가 한개로, 혼동이 없을 경우
=> ex) int list_add(int a, int b) // 더하는 역할을 하는 함수가 여러개로, 혼동이 있을 경우
4. Class의 사용
=> C++언어에서 type을 정의할 때 사용하는 keyword
=> ex) class cList { element data; cList *clink; }
Algorithm 성능분석
1. 수행 시간 측정
- algorithm의 실제 수행 시간을 측정하는 것
- 실제로 구현하는 것이 필요
- 동일한 hardware를 사용하여야 함
- 컴퓨터에서 수행시간을 측정하는 방법에는 주로 clock 함수가 사용
- clock_t clock(void); // clock함수는 호출되었을 때의 system 시각을 CLOCKS_PER_SEC 단위로 반환
2. 복잡도 분석
- 직접 구현하지 않고서도 수행 시간을 분석하는 것
- algorithm이 수행하는 연산의 횟수를 측정하여 비교
- 일반적으로 연산의 횟수는 n의 함수
- 시간 복잡도 분석 : 수행 시간 분석
- 공간 복잡도 분석 : 수행 시 필요로 하는 메모리 공간 분석
- 시간 복잡도는 algorithm을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시
- 연산의 수행횟수는 고정된 숫자가 아닌 n에 대한 함수로 나타내기 때문에 시간복잡도 함수라고 하고, T(n)으로 표기
3. 복잡도 분석의 예
- n을 n번 더하는 문제를 표현
- n을 n번 더하는 건 결국 n*n과 같다. 1번
- n을 1이 n이 될 때 까지 더한다. 2번
- 1을 n이 될 때 까지 1씩 더하며 1이 n이 될 때 까지 반복 3번
Big O 표기법
1. Big O의 개념
- 자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치므로 다른 항들은 무시
- n²과 n은 숫자가 커질 수록 점점 차이가 나며 n이 1000만 되어도 비율은 99:1정도로 차이난다.
- 따라서 시간복잡도 함수에서 가장 영향을 크게 미치는 항만을 고려한다.
2. Big O의 정의
- 연산의 횟수를 대략적으로 표기한 것
- Big O는 함수의 상한을 표시 ( n>=5이면 2n+1 < 10 이므로 2n+1 = O(n) )
3. Big O 표기의 종류
- O(1) : 상수형
- O(log n) : 로그형
- O(n) : 선형
- O(n log n) : 로그선형
- O(n^k) : k차형
- O(2ⁿ) : 지수형
- O(n!) : 팩토리얼형
https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 - 위키
https://www.desmos.com/calculator - 함수 만들어보는 사이트
'프로그래밍 > 자료구조' 카테고리의 다른 글
| [자료구조] Recursion (0) | 2019.10.15 |
|---|