[C언어로 쉽게 풀어쓴 자료구조] Chapter1. 자료구조와 알고리즘

1.1 자료구조와 알고리즘

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

 

자료구조 : 프로그램에서 자료들을 정리하여 보관하는 여러 구조

 

알고리즘 : 

• 컴퓨터로 문제를 풀기 위한 단계적인 절차
• 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 장치가 이해할 수 있는 언어로 기술한 것
• 특정한 일을 수행하는 명령어들 중 알고리즘이 되기 위한 조건들을 만족하는 집합

 

● 알고리즘 정의

입력(0개 이상), 출력(1개 이상), 명백성(의미는 모호하지 않고 명확),

유한성(한정된 수의 단계 후에는 반드시 종료), 유효성(종이, 연필 또는 컴퓨터로 실행 가능한 연산) 

 

● 알고리즘 기술법

1. 한글이나 영어 같은 자연어 - 모호성 제거 필요
2. 흐름도(flowchart) - 알고리즘이 복잡할수록 기술하기 어려움
3. 의사 코드(pseudo-code) - 자연어보단 체계적이고 프로그래밍 언어보다는 덜 엄격한 알고리즘 기술에 사용되는 코드
4. 프로그래밍 언어

1.2 추상 자료형

자료형 : 데이터의 종류

1. 기초 자료형 : char, int, float, double ...
2. 파생 자료형 : 배열, 포인터 ...
3. 사용자 정의 자료형 : 구조체, 공용체, 열거형 ...

-자료형 사용 시 데이터뿐만 아니라 데이터 간에 가능한 연산도 고려, 복잡한 자료형 구현 시 연산은 함수로 정의

 

● 추상 자료형(ADT: abstract data type) : 추상적, 수학적으로 자료형 정의

   추상화 : 어떤 시스템의 간략화된 기술 또는 명세로서 시스템의 핵심적인 구조나 동작에만 집중하는 것

ADT는 실제적인 구현으로부터 분리되어 추상적으로 자료형을 정의.

데이터나 연산이 무엇인지는 정의도지만 어떻게 컴퓨터 상에서 구현할 것인지는 정의되지 않음

= 사용자마다 구현 방법이 다양함, ADT 구현방식을 몰라도 사용가능, ADT 내부의 데이터에 접근 불가

 

※ 객체지향언어에서 ADT 구현 방식 : 클래스

ADT의 객체 = 클래스의 속성           ADT의 연산 = 클래스의 멤버함수

private, protected 키워드를 통해 내부 자료 접근 제한

클래스를 계층구조(상속 개념에 사용)로 구성 가능

 

※ Nat_No 추상 자료형에 is_greater(x, y) 연산 구현

Boolean is_greater(x,y) ::= if (x>y) return TRUE
			    else return FALSE

1.3  알고리즘의 성능 분석

1. 수행시간 측정방법

clock() 함수 또는 time() 함수를 사용해 프로그램 수행시간을 측정.

- 알고리즘 비교 시 똑같은 하드웨어로 비교해야 되는 문제

- 사용한 소프트웨어 환경, 언어마다 수행 속도 차이 존재 (컴파일 언어가 인터프리트 언어보다 빠름)

- 입력값마다 상이한 결과 도출 가능

 

2. 알고리즘의 복잡도 분석방법

구현하지 않고도 모든 입력을 고려하며, 실행 하드웨어나 소프트웨어 환경과 관계없이 알고리즘 효율성 평가 가능

 

● 시간복잡도 함수

알고리즘의 절대적인 수행시간 x, 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시

이때, 입력의 개수 n에 따른 연산의 수를 함수로 나타낸 것이 시간복잡도 함수, T(n)이다.

ex) n*n 구현

알고리즘 A= sum ← n*n             알고리즘 B= for i←i to n do                      알고리즘 C = for i←1 to n do

                                                                            sum← sum+n                                          for j←1 to n do

                                                                                                                                                  sum <- sum + 1

	알고리즘 A	알고리즘 B	알고리즘 C
대입연산	1	n	n*n
덧셈연산		n	n*n
곱셈연산	1
나눗셈연산
전체 연산 수	2	2n	2n^2

 

● 빅오 표기법

※두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n> n0에 대하여 |f(n)| ≤ c|g(n)| 을 만족하는 2개의 상수 c와 n0가

존재하면 f(n) = O(g(n))이다.

 

- 시간복잡도 함수에서 차수가 가장 큰 항만을 고려하여 표기하는 방법

- n이 커짐에 따라 2n과 5n의 차이가 미미하며 중요한 것은 B의 수행시간이 n에 정비례한다는 것이다.

- O(n)은 '빅오 of n'이라고 읽으며 n의 값에 따른 함수의 상한값을 나타낸다.

- 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항은 생략하므로 기본연산의 횟수가 n에 대한 다항식으로

표현되었을 경우 다항식의 최고차항만을 남긴다. 

- 상한을 표기하는 것이므로 정하기에 따라 2n+1의 상한도 O(n^2)로 나타낼 수 있다는 점에서 빅오 표기법은

최소 차수 함수로 표기되었을 경우만 의미가 있다.

 

 

O(1)<O(logn)<O(√n)<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)

 

● 빅오메가 표기법, 빅세타 표기법

※ 빅오메가 표기법

두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n> n0에 대하여 |f(n)| ≥ c|g(n)| 을 만족하는 2개의 상수 c와 n0가

존재하면 f(n) = Ω(g(n))이다.

- 함수의 하한을 나타낸다.

 

※ 빅세타 표기법

두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n> n0에 대하여  c1|g(n)| ≤ |f(n)| ≤ c2|g(n)| 을 만족하는 3개의 상수

c1, c2, n0 가 존재하면 f(n) = Θ(g(n))이다.

 

● 최선, 평균, 최악의 경우

알고리즘의 효율성을 주어지는 자료집합에 따라 최악, 최선, 평균의 경우로 나누어 평가할 수 있다.

다만 평균 수행시간은 광범위한 자료 집합에 대하여 알고리즘을 적용시켜 평균값을 계산하여야 하므로 보통은

최악의 경우의 수행시간이 시간 복잡도 척도로 많이 쓰인다.

최악의 경우란 입력 자료 집합을 알고리즘에 최대한 불리하게 만들어서 얼마의 시간이 소모되는 지를 분석하는 것이다.