01장.자료구조와 알고리즘

Transcription

1 DATA STRUCTURES USING C CHAPTER 자료구조와알고리즘 1/30

2 자료구조 일상생활에서자료를정리하고조직화하는이유는? 사물을편리하고효율적으로사용하기위함 다양한자료를효율적인규칙에따라정리한예 2/30

3 컴퓨터에서의자료구조 자료구조 (Data Structure) 컴퓨터에서자료를정리하고조직화하는다양한구조 일상생활에서의예 물건을쌓아두는것 영화관매표소의줄 자료구조 스택 큐 a b c NULL 할일리스트 리스트 영어사전사전, 탐색구조 지도 조직도 그래프 트리 C B A Ticket Box 전단 (front) 후단 (rear) 3/30

4 자료구조의분류 단순자료구조 정수실수문자문자열포인터 스택 3장큐 4장덱리스트 6장 배열연결리스트 2장 5장 자료구조 복합자료구조 선형구조 8장트리우선순위큐 일반트리이진트리 10장 이진탐색트리 AVL 트리 9장 순환알고리즘 7 장 비선형구조 그래프 방향그래프 무방향그래프 11 장 정렬알고리즘 13 장 맵 14 장 가중치그래프 12 장 4/30

5 컴퓨터프로그램의구성 컴퓨터프로그램은무엇으로이루어져있나? 프로그램 = 자료구조 + 알고리즘 5/30

6 ( 예 ) 최대값탐색프로그램 = 배열 + 순차탐색 6/30

7 알고리즘 컴퓨터로문제를풀기위한단계적인절차 예 ) 전화번호부에서특정사람이름찾기 알고리즘의조건 입력 : 0개이상의입력이존재하여야한다. 출력 : 1개이상의출력이존재하여야한다. 명백성 : 각명령어의의미는모호하지않고명확해야함. 유한성 : 한정된수의단계후에는반드시종료되어야함. 유효성 : 각명령어들은실행가능한연산이어야한다. 박철수의전화번호는바로부근으로넘기면찾을수있겠군 7/30

8 알고리즘의기술방법 방법들 영어나한국어와같은자연어 흐름도 (flow chart) 유사코드 (pseudo-code) 특정한프로그래밍언어 (C언어, C++, java 등 ) ( 예 ) 배열에서최대값찾기알고리즘 /30

9 알고리즘의기술방법 (1) (1) 자연어로표기된알고리즘 인간이읽기가쉽다. 단어들을정확하게정의하지않으면의미전달이모호해질우려가있다. ArrayMax(A,n) 1. 배열 A 의첫번째요소를변수 tmp 에복사 2. 배열 A 의다음요소들을차례대로 tmp 와비교하면더크면 tmp 로복사 3. 배열 A 의모든요소를비교했으면 tmp 를반환 9/30

10 알고리즘의기술방법 (2) (2) 흐름도로표기된알고리즘 직관적이고이해하기쉬운알고리즘기술방법 그러나복잡한알고리즘의경우, 상당히복잡해짐. tmpmax A[0] i 0 i<n no no A[i]>tmpMax yes tmpmax A[i] tmpmax i++ 10/30

11 알고리즘의기술방법 (3) (3) 유사코드로표현된알고리즘 알고리즘의고수준기술방법 자연어보다는더구조적인표현방법 프로그래밍언어보다는덜구체적인표현방법 알고리즘기술에가장많이사용 프로그램을구현할때의여러가지문제들을감출수있음 알고리즘의핵심적인내용에만집중할수있음 ArrayMax(A,n) tmp A[0]; for i 1 to n-1 do if tmp < A[i] then tmp A[i]; return tmp; 대입연산자가 임을유의 11/30

12 알고리즘의기술방법 (4) (4) 특정언어로표현된알고리즘 알고리즘의가장정확한기술가능 실제구현시의많은구체적인사항들이알고리즘의핵심적인내용들의이해를방해할수있음 예 ) C 언어로표기된알고리즘 #define MAX_ELEMENTS 100 int score[max_elements]; int find_max_score(int n) { int i, tmp; tmp=score[0]; for(i=1;i<n;i++){ if( score[i] > tmp ){ tmp = score[i]; } } return tmp; } 12/30

13 자료형과추상자료형 추상화란? 어떤시스템의간략화된기술또는명세 시스템의정말핵심적인구조나동작에만집중 자료형 (data type) 데이터의집합과연산의집합 데이터 : {,-2,-1,0,1,2, } 예 ) int 데이터타입연산 : +, -, /, *, % 추상자료형 (ADT: Abstract Data Type) 데이터타입을추상적 ( 수학적 ) 으로정의한것 데이터나연산이무엇 (what) 인가를정의함 데이터나연산을어떻게 (how) 구현할것인지는정의하지않음 13/30

14 추상자료형의정의 데이터 + 연산 객체 연산 자연수 ADT 데이터 : 1에서시작하여 INT_MAX까지의순서화된정수의부분범위연산 : add(x,y): x+y가 INT_MAX보다작으면 x+y를반환 distance(x,y): x가 y보다크면 x-y를반환하고작으면 y-x를반환 equal(x,y): x와 y가같은값이면 TRUE, 아니면 FALSE를반환 successor(x): x가 INT_MAX보다작으면 x+1을반환한다. 14/30

15 추상자료형과자료구조 추상자료형과자료구조의관계 자료구조는추상자료형을프로그래밍언어로구현한것 먼저각자료구조의추상자료형을소개 추상자료형의구현 이책에서는 C 언어를사용 추상자료형의데이터 : 구조체를사용 추상자료형의연산 : 함수를사용 다른방법 : 객체지향언어 (C++, Java 등 ) 15/30

16 알고리즘의성능분석 알고리즘의성능분석기법 실행시간을측정하는방법 두개의알고리즘의실제실행시간을측정하는것 실제로구현하는것이필요 동일한하드웨어를사용하여야함 알고리즘의복잡도를분석하는방법 직접구현하지않고서도수행시간을분석하는것 알고리즘이수행하는연산의횟수를측정하여비교 일반적으로연산의횟수는 n의함수 시간복잡도분석 : 수행시간분석 공간복잡도분석 : 수행시필요로하는메모리공간분석 16/30

17 (1) 실행시간측정 clock 함수사용 : clock_t clock(void); 호출되었을때의시스템시각반환 CLOCKS_PER_SEC 단위 실행시간측정프로그램예 #include <stdio.h> #include <stdlib.h> #include <time.h> void main( void ) { clock_t start, finish; double duration; start = clock(); // 실행시간을측정하고자하는코드... //... finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("%f 초입니다.\n", duration); } 17/30

18 (2) 복잡도분석 시간복잡도 산술, 대입, 비교, 이동의기본적인연산고려 알고리즘수행에필요한연산의개수를계산 입력의개수 n에대한함수-> 시간복잡도함수, T(n) 알고리즘 A 알고리즘 B 18/30

19 복잡도분석의예 n 을 n 번더하는문제 각알고리즘이수행하는연산의개수계산 단 for 루프제어연산은고려하지않음 알고리즘 A 알고리즘 B 알고리즘 C sum n*n; sum 0; for i 1 to n do sum sum + n; sum 0; for i 1 to n do for j 1 to n do sum sum + 1; 알고리즘 A 알고리즘 B 알고리즘 C 대입연산 1 n + 1 n*n + 1 덧셈연산 n n*n 곱셈연산 1 나눗셈연산 전체연산수 2 2n + 1 2n /30

20 연산의횟수를그래프로표현 연산의횟수 알고리즘 C 알고리즘 B 알고리즘 A 입력의개수 n 20/30

21 시간복잡도함수계산예 코드를분석해보면수행되는수행되는연산들의횟수를입력크기의함수로만들수있다. ArrayMax(A,n) tmp A[0]; 1번의대입연산 for i 1 to n-1 do 루프제어연산은제외 if tmp < A[i] then n-1번의비교연산 tmp A[i]; n-1번의대입연산 ( 최대 ) return tmp; 1번의반환연산 총연산수 = 2n( 최대 ) 21/30

22 빅오표기법 차수가가장큰항이가장영향을크게미치고다른항들은상대적으로무시될수있음 예 : T(n) = n 2 + n + 1 n=1 일때 : T(n) = = 3 (33.3%) n=10 일때 : T(n) = = 111 (90%) n=100 일때 : T(n) = = (99%) n=1,000 일때 : T(n) = = (99.9%) n=100 인경우 T(n)= n 2 + n % 1% 22/30

23 빅오표기법의정의 두개의함수 f(n) 과 g(n) 이주어졌을때, 모든 n n0 에대하여 f(n) c g(n) 을만족하는 2 개의상수 c 와 n0 가존재하면 f(n)=o(g(n)) 이다. 연산의횟수를대략적 ( 점근적 ) 으로표기한것 빅오는함수의상한을표시한다. ( 예 ) n 5 이면 2n+1 <10n 이므로 2n+1 = O(n) 연산의횟수 O( g( n)) f (n) n 0 입력의개수 n 23/30

24 빅오표기법의예 예제 1.1 빅오표기법 f(n)=5 이면 O(1) 이다. 왜냐하면 n0=1, c=10 일때, n 1 에대하여 이되기때문이다. f(n)=2n+1 이면 O(n) 이다. 왜냐하면 n0=2, c=3 일때, n 2 에대하여 2n+1 3n 이되기때문이다. f(n)=3n 이면 O(n 2 ) 이다. 왜냐하면 n0=100, c=5 일때, n 100 에대하여 3n 이되기때문이다. f(n)=5 2 n + 10n 이면 O(2 n ) 이다. 왜냐하면 n0=1000, c=10 일때, n 1000 에대하여 5 2 n + 10n < 10 2 n 이되기때문이다. 24/30

25 빅오표기법의종류 O(1) : 상수형 O(logn) : 로그형 O(n) : 선형 O(nlogn) : 로그선형 O(n 2 ) : 2차형 O(n 3 ) : 3차형 O(n k ) : k차형 O(2 n ) : 지수형 O(n!) : 팩토리얼형 25/30

26 빅오표기법의종류 시간복잡도 n logn n nlogn n n n n! /30

27 빅오메가표기법 정의 모든 n n0 에대하여 f(n) c g(n) 을만족하는 2 개의상수 c 와 n0 가존재하면 f(n)=ω(g(n)) 이다. 빅오메가는함수의하한을표시 ( 예 ) n 1 이면 2n+1 > n 이므로 n = Ω(n) 연산의수 O( g( n)) 상한 f (n) ( g( n)) 하한 n 0 입력의개수 n 27/30

28 빅세타표기법 정의 모든 n n0 에대하여 c1 g(n) f(n) c2 g(n) 을만족하는 3 개의상수 c1, c2 와 n0 가존재하면 f(n)=θ(g(n)) 이다. 연산의수 O( g( n)) 상한 빅세타는함수의하한인동시에상한을표시한다. f(n)=o(g(n)) 이면서 f(n)= Ω(g(n)) 이면 f(n)= θ(n) 이다. ( 예 ) n 1 이면 n 2n+1 3n 이므로 2n+1 = θ(n) n 0 f (n) ( g( n)) 하한입력의개수 n 28/30

29 최선, 평균, 최악의경우 실행시간은입력집합에따라다를수있음 최선의경우 (best case): 수행시간이가장빠른경우 의미가없는경우가많다. 평균의경우 (average case): 수행시간이평균적인경우 계산하기가상당히어려움. 최악의경우 (worst case): 수행시간이가장늦은경우 가장널리사용된다. 계산하기쉽고응용에따라서중요한의미를가질수도있다. ( 예 ) 비행기관제업무, 게임, 로보틱스 29/30

30 예 : 순차탐색의최선, 평균, 최악 int sequentialsearch(int list[], int n, int key) { for(int i=0 ; i<n ; i++) } // 탐색에성공하면키값의인덱스반환 if(list[i]==key) return i; return 1; // 탐색에실패하면 -1 반환 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 최선의경우 : O(1) 최악의경우 : O(n) 인덱스 0 에서 5 발견숫자비교횟수 = 1 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 평균적인경우 : (1+2+ +n)/n=(n+1)/2 O(n) 인덱스 0 에서 43 발견숫자비교횟수 = 10 30/30