슬라이드 1

Transcription

1 Data Structure & Algorithms SANGJI University KO Kwangman ()

2 자료 (data) 1. 자료와정보 현실세계로부터의단순한관찰이나측정을통하여수집한사실이나개념의값들또는값들의집합. 정보 (information) 의사결정에도움을주기위해유용한형태로다시작성된 (= 가공 ) 자료. Data Structure & Algorithms 2

3 일상생활에서의사물의조직화 자료구조정의? 조직도 해야할일리스트 Ticket Box Data Structure & Algorithms 3

4 a b c NULL C B A Ticket Box 전단 (front) 후단 (rear) Data Structure & Algorithms 4

5 자료구조 (data structure) 란? 다루고자하는자료원소들 (elements) 간논리적관계를기술한것 컴퓨터의휘발성또는비휘발성메모리에존재하는자료의집합 자료값에대한연산을효율적으로처리할수있도록자료의구성을조직적이고체계적으로표현하는것 Data Structure & Algorithms 5

6 자료구조의선택기준 자료의양 ( 자료가차지하는메모리공간 ) 자료의활용빈도 ( 저장방식결정 ) 사용가능한기억용량 ( 전체적인메모리공간 ) 자료의갱신정도 처리시간의제한성 프로그래밍의용이성 Data Structure & Algorithms 6

7 효율성 (Efficiency) 자료구조의목적 좀더효율적인알고리즘이될수있도록자료를구조화. 추상화 (Abstraction) 자료를보다쉽게이해할수있는방법인추상화를제공. 재사용성 (Reusability) 모듈화되어있고문맥에자유롭기 (context-free) 때문에재사용이가능. Data Structure & Algorithms 7

8 프로그램 = 자료구조 + 알고리즘 2. 알고리즘과프로그램 최대값탐색프로그램 = 배열 + 순차탐색 자료구조 score[] 알고리즘 tmp score[0]; for i 1 to n do if score[i]>tmp then tmp score[i]; Data Structure & Algorithms 8

9 알고리즘 (algorithm) 어떤문제를해결하기위해기술해놓은명확한절차로, 일련의명령 (instruction 또는 step) 집합을의미 프로그램 (program) 컴퓨터가수행할수있는상세화된명령어의집합 Data Structure & Algorithms 9

10 입력 (Input) 알고리즘의요건 제공되는자료가있을수도있고없을수도있다. 출력 (Output) 한개이상의결과가반드시생성되어야한다. 명백성 (Definiteness) 문제해결단계에서수행할내용은모호하지않고명백해야한다. 유한성 (Finiteness) 한정된수의단계후에는반드시종료되어야한다. 유효성 (Effectiveness) 알고리즘의모든명령은수행가능한것이어야한다. Data Structure & Algorithms 10

11 삽입 (insert) 대표적인알고리즘 자료구조에서새로운자료를삽입 검색 / 탐색 (search) 자료구조에서원하는자료를찾기 삭제 / 제거 (delete) 자료구조에서기존의자료를삭제 정렬 (sorting) 자료구조에있는자료들을특정키값에의해서순서대로나열 반복, 순회, Data Structure & Algorithms 11

12 자료구조, 알고리즘, 프로그램사이의관계 자료구조 알고리즘 프로그램 Data Structure & Algorithms 12

13 알고리즘기술방법 영어나한국어와같은자연어 흐름도 (flow chart) 유사코드 (pseudo-code) C/C++/Java/ 와같은프로그래밍언어 Data Structure & Algorithms 13

14 특징 인간이읽기가쉽다. 자연어로표기된알고리즘 자연어의단어들을정확하게정의하지않으면의미전달이모호해질우려가있다. ( 예 ) 배열에서최대값찾기알고리즘 ArrayMax(A,n) 1. 배열 A 의첫번쨰요소를변수 tmp 에복사 2. 배열 A 의다음요소들을차례대로 tmp 와비교하면더크면 tmp 로복사 3. 배열 A 의모든요소를비교했으면 tmp 를반환 Data Structure & Algorithms 14

15 흐름도로표기된알고리즘 특징 직관적이고이해하기쉬운알고리즘기술방법 복잡한알고리즘의경우, 상당히복잡해짐. tmp A[0] i 1 i < n no yes no A[i]>tmp yes tmp A[i] tmp i++ Data Structure & Algorithms 15

16 특징 알고리즘의고수준기술방법 유사코드로표현된알고리즘 자연어보다는더구조적인표현방법 프로그래밍언어보다는덜구체적인표현방법 알고리즘기술에가장많이사용 프로그램을구현할때의여러가지문제들을감출수있다. 즉알고리즘의핵심적인내용에만집중할수있다. Data Structure & Algorithms 16

17 특징 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; } Data Structure & Algorithms 17

18 자료구조 4. 자료구조의분류 선형구조 비선형구조 일반트리 배열 (Array) 이진트리 연결리스트 (Linked list) 단순연결리스트 이중연결리스트 트리 (Tree) AVL 트리 트리 원형연결리스트 스택 (Stack) 무방향그래프 큐 (Queue) 그래프 (Graph) 방향그래프 데크 (Deque) 가중치그래프 Data Structure & Algorithms 18

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

20 수행시간측정 컴퓨터에서수행시간을측정하는방법에는주로 clock 함수사용. clock_t clock(void); clock 함수는호출되었을때의시스템시각을 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); } Data Structure & Algorithms 20

21 복잡도분석 시간복잡도는알고리즘을이루고있는연산들이몇번이나수행되는지를숫자로표시 산술, 대입, 비교, 이동연산의기본적인연산 : 수행시간이입력의크기에따라변하면안됨 알고리즘이수행하는연산의개수를계산하여두개의알고리즘을비교할수있다. 연산의수행횟수는고정된숫자가아니라입력의개수 n에대한함수-> 시간복잡도함수라고하고 T(n) 이라고표기한다. 프로그램 A 프로그램 B 워드 2005 워드 2000 연산의수 = 8 3n+2 연산의수 =26 5n 2 +6 Data Structure & Algorithms 21

22 복잡도분석의예 n 을 n 번더하는문제 : 각알고리즘이수행하는연산의개수를세어본다. 단 for 루프제어연산은고려하지않음. 알고리즘 A 알고리즘 B 알고리즘 C sum n*n; sum 0; for i 1tondo sum sum + n; sum 0; for i 1 tondo for 1 tondo sum sum + 1; 알고리즘 A 알고리즘 B 알고리즘 C 대입연산 1 n + 1 n*n + 1 덧셈연산 n n*n 곱셈연산 1 나눗셈연산전체연산수 2 2n + 1 2n Data Structure & Algorithms 22

23 연산의횟수를그래프로표현 연산의횟수 알고리즘 C 알고리즘 B 알고리즘 A 입력의개수 n Data Structure & Algorithms 23

24 시간복잡도함수계산예 코드를분석해보면수행되는수행되는연산들의횟수를입력크기의함수로만들수있다. 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( 최대 ) Data Structure & Algorithms 24

25 빅오표기법 자료의개수가많은경우에는차수가가장큰항이가장영향을크게미치고다른항들은상대적으로무시될수있다. ( 예 ) n=1,000 일때, T(n) 의값은1,001,001이고이중에서첫번째항인의값이전체의약 99% 인 1,000,000이고두번째항의값이 1000으로전체의약 1% 를차지한다. 따라서보통시간복잡도함수에서가장영향을크게미치는항만을고려하면충분하다. n=1000 인경우 T(n)= n 2 + n % 1% 빅오표기법 : 연산의횟수를대략적 ( 점근적 ) 으로표기한것 두개의함수 f(n) 과 g(n) 이주어졌을때, 연산의횟수 O( f ( n)) 모든 n n 0 에대하여 f(n) c g(n) 을만족하는2개의상수 c와 n 0 가존재하면 f(n)=o(g(n)) 이다. 빅오는함수의상한을표시한다. ( 예 ) n 5 이면 2n+1 <10n 이므로 2n+1 = O(n) f (n) n 0 입력의개수 n Data Structure & Algorithms 25

26 빅오표기법의예 Data Structure & Algorithms 26

27 빅오표기법의종류 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!) : 팩토리얼형 시간복잡도 n logn n nlogn n n n n! Data Structure & Algorithms 27

28 빅오표기법이외의표기법 빅오메가표기법. 모든 n n 0 에대하여 f(n) c g(n) 을만족하는 2 개의상수 c 와 n 0 가존재하면 f(n)=ω(g(n)) 이다. 빅오메가는함수의하한을표시한다. ( 예 ) n 5 이면 2n+1 <10n 이므로 n = Ω(n) 빅세타표기법 모든 n n 0 에대하여 c 1 g(n) f(n) c 2 g(n) 을만족하는 3 개의상수 c 1, c 2 와 n 0 가존재하면 f(n)=θ(g(n)) 이다. 연산의수 O( f ( n)) 상한 f (n) Ω( f ( n)) 하한 빅세타는함수의하한인동시에상한을표시한다. f(n)=o(g(n)) 이면서 f(n)= Ω(g(n)) 이면 f(n)= θ(n) 이다. ( 예 ) n 1 이면 n 2n+1 3n 이므로 2n+1 = θ(n) n 0 입력의개수 n Data Structure & Algorithms 28

29 최선, 평균, 최악의경우 알고리즘의수행시간은입력자료집합에따라다를수있다. ( 예 ) 정렬알고리즘의수행시간은입력집합에따라다를수있다. 최선의경우 (best case): 수행시간이가장빠른경우 평균의경우 (average case): 수행시간이평균적인경우 최악의경우 (worst case): 수행시간이가장늦은경우 수행시간 최악의경우 평균적인경우 최선의경우 최선의경우 : 의미가없는경우가많다. 평균적인경우 : 계산하기가상당히어려움. 최악의경우 : 가장널리사용된다. 계산하기쉽고응용에따라서중요한의미를가질수도있다. ( 예 ) 비행기관제업무, 게임, 로보틱스 A B C D E F G 입력집합 Data Structure & Algorithms 29

30 최선, 평균, 최악의경우 ( 예 ) 순차탐색 최선의경우 : 찾고자하는숫자가맨앞에있는경우 O(1) 최악의경우 : 찾고자하는숫자가맨뒤에있는경우 O(n) 평균적인경우 : 각요소들이균일하게탐색된다고가정하면 (1+2+ +n)/n=(n+1)/2 O(n)

31 자료구조의 C 언어표현방법 자료구조와관련된데이터들을구조체로정의 연산을호출할경우, 이구조체를함수의파라미터로전달 ( 예 ) // 자료구조스택과관련된자료들을정의 typedef int element; typedef struct { int top; element stack[max_stack_size]; } StackType; 자료구조의요소 관련된데이터를구조체로정의 // 자료구조스택과관련된연산들을정의 void push(stacktype *s, element item) { if( s->top >= (MAX_STACK_SIZE -1)){ stack_full(); return; } s->stack[++(s->top)] = item; } 연산을호출할때구조체를함수의파라미터로전달 Data Structure & Algorithms 31

32 자료구조기술규칙 상수 대문자로표기 ( 예 ) #define MAX_ELEMENT 100 변수의이름 소문자를사용하였으며언더라인을사용하여단어와단어를분리 ( 예 ) int increment; int new_node; 함수의이름 동사를이용하여함수가하는작업을표기 ( 예 ) int add(listnode *node) // 혼동이없는경우 int list_add(listnode *node) // 혼동이생길우려가있는경우 typedef 의사용 C 언어에서사용자정의데이터타입을만드는경우에쓰이는키워드 ( 예 ) typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; typedef < 새로운타입의정의 > < 새로운타입이름 >; Data Structure & Algorithms 32