Data Structure Chapter 1. 자료구조와알고리즘 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr
자료구조와알고리즘
일상생활에서의사물의조직화 해야할일리스트 조직도 일상생활에서의사물의조직화 사전 Ticket Box 3
일상생활과자료구조의비교 일상생활 vs 자료구조 자료구조 스택 큐 리스트 사전, 탐색구조 그래프 트리 일상생활에서의예 물건을쌓아두는것 영화관매표소의줄 할일리스트 영어사전 지도 조직도 해야할일리스트 Ticket Box a b c NULL C B A 전단 (front) 후단 (rear) 4
자료구조와알고리즘 프로그램 = 자료구조 + 알고리즘 예 ) 최대값탐색프로그램 = 배열 + 순차탐색 자료구조 score[ ] 80 70 90 30 알고리즘 tmp score[0]; for i 1 to n do if score[i]>tmp then tmp score[i]; 5
알고리즘 알고리즘 (algorithm) : 컴퓨터로문제를풀기위한단계적인절차 알고리즘의조건 입력 : 0개이상의입력이존재하여야한다. 출력 : 1개이상의출력이존재하여야한다. 명백성 : 각명령어의의미는모호하지않고명확해야한다. 유한성 : 한정된수의단계후에는반드시종료되어야한다. 유효성 : 각명령어들은실행가능한연산이어야한다. 6
알고리즘의기술방법 영어나한국어와같은자연어 흐름도 (Flow Chart) 유사코드 (Pseudo Code) C와같은프로그래밍언어 7
알고리즘의기술방법 ( 자연어 ) 자연어 인간이읽기가쉬움 자연어의단어들을정확하게정의하지않으면의미전달이모호해짐 예 ) 배열에서최대값찾기알고리즘 ArrayMax(A,n) 1. 배열 A 의첫번쨰요소를변수 tmp 에복사 2. 배열 A 의다음요소들을차례대로 tmp 와비교하면더크면 tmp 로복사 3. 배열 A 의모든요소를비교했으면 tmp 를반환 8
알고리즘의기술방법 ( 흐름도 ) 흐름도 (Flow Chart) 직관적이고이해하기쉬운알고리즘기술방법 복잡한알고리즘의경우상당히복잡해짐 예 ) 배열에서최대값찾기알고리즘 ArrayMax tmp A[0] i 1 i < n no no yes A[i]>tmp yes tmp A[i] return tmp i++ 9
알고리즘의기술방법 ( 유사코드 ) 유사코드 (Pseudo Code) 알고리즘의고수준기술방법 자연어보다는더구조적인표현방법 프로그래밍언어보다는덜구체적인표현방법 알고리즘기술에가장많이사용 프로그램을구현할때의여러가지문제들을감출수있다. 알고리즘의핵심적인내용에만집중 ArrayMax(A,n) tmp A[0]; for i 1 to n-1 do if tmp < A[i] then tmp A[i]; return tmp; 10
알고리즘의기술방법 ( 프로그래밍언어 ) 프로그래밍언어 알고리즘의가장정확한기술이가능 실제구현시, 많은구체적인사항들이알고리즘의핵심적인내용에대한 이해를방해 #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; } 11
버블정렬 (Bubble Sort) 인접한 2 개의레코드를비교하여순서대로되어있지않으면서로교환 이러한비교 - 교환과정을리스트의왼쪽끝에서오른쪽끝까지반복 ( 스캔 ) 5 3 8 1 2 7 초기상태 5 3 8 1 2 7 초기상태 5 3 8 1 2 7 5 와 3 을교환 3 5 1 2 7 8 스캔 1 3 5 8 1 2 7 교환없음 3 1 2 5 7 8 스캔 2 3 5 8 1 3 7 8 과 1 을교환 1 2 3 5 7 8 스캔 3 3 5 1 8 3 7 8 과 2 를교환 1 2 3 5 7 8 스캔 4 3 5 1 2 8 7 8 과 7 을교환 1 2 3 5 7 8 스캔 5 3 5 1 2 7 8 하나의스캔완료 1 2 3 5 7 8 정렬완료 12
버블정렬알고리즘 #define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) void bubble_sort(int list[], int n) { int i, j, temp; for( i = n-1; i > 0; i-- ) for( j = 0; j < i; j++ ) if( list[j] > list[j+1] ) SWAP(list[j], list[j+1], temp); } 13
추상데이터타입
데이터타입 데이터타입 (Data Type) 데이터의집합과연산의집합 예 )int 데이터타입 데이터 : {, -2, -1, 0, 1, 2, } 연산 : +, -, /, *, % 추상데이터타입 (ADT: Abstract Data Type) 데이터타입을추상적 ( 수학적 ) 으로정의한것 데이터나연산이무엇 (what) 인가는정의되지만데이터나연산을어떻게 (how) 컴퓨터상에서구현할것인지는정의되지않는다. 15
추상데이터타입의정의 추상데이터타입 객체 : 추상데이터타입에속하는객체가정의된다. 연산 : 이들객체들사이의연산이정의된다. 이연산은추상데이터타입과외부를연결하는인터페이스의역할을한다. 2 3 객체 9 7 연산 8 추상데이터타입 16
추상데이터타입의예시 Nat_No 객체 : 0 에서시작하여 INT_MAX 까지의순서화된정수의부분범위 연산 zero() ::= return 0; is_zero() ::= if (x) return FALSE; else return TRUE; add(x,y) ::= if( (x+y) <= INT_MAX ) return x+y; else return INT_MAX sub(x,y) ::= if ( x<y ) return 0; else return x-y; equal(x,y) ::= if( x=y ) return TRUE; else return FALSE; successor(x) ::= if( (x+y) <= INT_MAX ) return x+1; 17
추상데이터 vs VCR 추상데이터 제공하는연산만을사용가능 어떻게사용하는지를알아야함 추상데이터타입내부의데이터접근불가 어떻게구현되었는지몰라도사용가능 구현이변경되어도인터페이스가변경되지않으면그대로사용가능 VCR 인터페이스가제공하는특정한작업만을수행 사용자는이러한작업들에대한이해필요 ( 비디오를시청하기위해서는무엇을해야하는지를알아야함 ) VCR의내부를볼수없음 VCR의내부에서무엇이일어나고있는지몰라도사용가능 내부의기계장치를교환되어도인터페이스가바뀌지않으면그대로사용가능 18
알고리즘의성능분석
알고리즘의성능분석 알고리즘의성능분석기법 수행시간측정 두개의알고리즘의실제수행시간을측정하는것 실제로구현하는것이필요 동일한하드웨어를사용하여야함 알고리즘의복잡도분석 직접구현하지않고서도수행시간을분석하는것 알고리즘이수행하는연산의횟수를측정하여비교 일반적으로연산의횟수는 n의함수 시간복잡도분석 : 수행시간분석 공간복잡도분석 : 수행시필요로하는메모리공간분석 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); } 21
알고리즘의성능분석 ( 복잡도분석 ) 시간복잡도 알고리즘을이루고있는연산들이몇번이나수행되는지를숫자로표시 산술연산, 대입연산, 비교연산, 이동연산의기본적인연산 수행시간이입력의크기에따라변하면안됨 알고리즘이수행하는연산의개수를계산하여두개의알고리즘비교가능 시간복잡도함수 : 입력의개수 n에대한연산의수행횟수. T(n) 이라고표기 22
복잡도분석의예 n 을 n 번더하는문제 각알고리즘이수행하는연산의개수를셈 단, for 루프제어연산은고려X 알고리즘 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 2 + 1 23
연산의횟수를그래프로표현 그래프표현 연산의횟수 알고리즘 C 알고리즘 B 알고리즘 A 입력의개수 n 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( 최대 ) 25
빅오표기법 빅오표기법 연산의횟수를대략적 ( 점근적 ) 으로표기한것 두개의함수 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( f ( n)) f (n) n 0 26
빅오표기법의예 예제 1.1 빅오표기법 f n = 5이면 O 1 이다. n 0 = 1, c = 10일때, n 1에대하여 5 10 1이된다. f n = 2n + 1이면 O n 이다. n 0 = 2, c = 3일때, n 2에대하여 2n + 1 3n이된다. f n = 3n 2 + 100이면 O n 2 이다. n 0 = 100, c = 5일때, n 100에대하여 3n 2 + 100 5n 2 이된다. f n = 5 2 n +10n 2 + 100이면 O 2 n 이다. n 0 = 1000, c = 10일때, n 1000에대하여 5 2 n +10n 2 + 100 10 2 n 이된다. 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!) : 팩토리얼형 28
그외표기법 빅오메가표기법 모든 n n 0 에대하여 f(n) c g(n) 을만족하는 2 개의상수 c 와 n 0 가존재하면 f(n)=ω(g(n)) 이다. 빅오메가는함수의하한을표시한다. 예 ) n 5 이면 2n+1 <10n 이므로 n = Ω(n) 연산의수 O( f ( n)) 상한 f (n) ( f ( n)) 하한 n 0 입력의개수 n 29
수행시간 최선, 평균, 최악의경우 (1/3) 알고리즘의수행시간은입력자료집합에따라다를수있다. 예 ) 정렬알고리즘의수행시간 최선의경우 (best case) : 수행시간이가장빠른경우 평균의경우 (average case) : 수행시간이평균적인경우 최악의경우 (worst case) : 수행시간이가장늦은경우 100 50 최악의경우 평균적인경우 최선의경우 A B C D E F G 입력집합 30
최선, 평균, 최악의경우 (3/3) 순차탐색 최선의경우 : 찾고자하는숫자가맨앞에있는경우 O(1) 최악의경우 : 찾고자하는숫자가맨뒤에있는경우 O(n) 평균적인경우 : 각요소들이균일하게탐색된다고가정하면 (1+2+ +n)/n=(n+1)/2 O(n) 인덱스 0 에서값 5 발견숫자비교횟수 = 1 인덱스 9 에서값 43 발견숫자비교횟수 = 10 인덱스 5 에서값 26 발견숫자비교횟수 = 10 5 9 10 17 21 29 33 37 38 43 0 1 2 3 4 5 6 7 8 9 5 9 10 17 21 29 33 37 38 43 0 1 2 3 4 5 6 7 8 9 2 7 16 19 20 26 35 42 46 50 0 1 2 3 4 5 6 7 8 9 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; } 연산을호출할때구조체를함수의파라미터로전달 33
자료구조기술규칙 (1/2) 상수 대문자로표기 예 ) #define MAX_ELEMENT 100 변수의이름 소문자를사용하였으며언더라인을사용하여단어와단어를분리 예 ) int increment; int new_node; 함수의이름 동사를이용하여함수가하는작업을표기 예 ) int add(listnode *node) // 혼동이없는경우 int list_add(listnode *node) // 혼동이생길우려가있는경우 34
자료구조기술규칙 (2/2) typedef 의사용 C 언어에서사용자정의데이터타입을만드는경우에쓰이는키워드 typedef < 새로운타입의정의 > < 새로운타입이름 >; ( 예 ) typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; 35