CHAP 1: 자료구조와알고리즘 C 로쉽게풀어쓴자료구조 생능출판사 2005
일상생활에서의사물의조직화 조직도 일상생활에서의사물의조직화 Ticket Box
일상생활과자료구조의비교 a b c N 일상생활에서의예 물건을쌓아두는것 영화관매표소의줄 할일리스트 자료구조 스택 큐 리스트 영어사전사전, 탐색구조 지도 조직도 그래프 트리 Ticket Box C B A 전단 (front) 후단 (rear)
자료구조와알고리즘 프로그램 = 자료구조 + 알고리즘 ( 예 ) 최대값탐색프로그램 = 배열 + 순차탐색 자료구조 알고리즘 score[] 80 70 90 30 tmp score[0]; for i 1 to n do if score[i]>tmp then tmp score[i];
알고리즘 알고리즘 (algorithm): 컴퓨터로문제를풀기위한단계적인절차 알고리즘의조건 입력 : 0 개이상의입력이존재하여야한다. 출력 : 1 개이상의출력이존재하여야한다. 명백성 : 각명령어의의미는모호하지않고명확해야한다. 유한성 : 한정된수의단계후에는반드시종료되어야한다. 유효성 : 각명령어들은실행가능한연산이어야한다. 박철수의전화번호는바로ㅂ부근으로넘기면찾을수있겠군
알고리즘의기술방법 영어나한국어와같은자연어 흐름도 (flow chart) 유사코드 (pseudo-code) C와같은프로그래밍언어 ( 예 ) 배열에서최대값찾기알고리즘 0 1 2 3 4 5 6 7 8 9 10
자연어로표기된알고리즘 인간이읽기가쉽다. 그러나자연어의단어들을정확하게정의하지않으면의미전달이모호해질우려가있다. ( 예 ) 배열에서최대값찾기알고리즘 ArrayMax(A,n) 1. 배열 A의첫번쨰요소를변수 tmp에복사 2. 배열 A의다음요소들을차례대로 tmp와비교하면더크면 tmp 로복사 3. 배열 A의모든요소를비교했으면 tmp를반환
흐름도로표기된알고리즘 직관적이고이해하기쉬운알고리즘기술방법 그러나복잡한알고리즘의경우, 상당히복잡해짐. tmp A[0] i 1 i < n no yes no A[i]>tmp yes tmp A[i] tmp i++
유사코드로표현된알고리즘 알고리즘의고수준기술방법 자연어보다는더구조적인표현방법 프로그래밍언어보다는덜구체적인표현방법 알고리즘기술에가장많이사용 프로그램을구현할때의여러가지문제들을감출수있다. 즉알고리즘의핵심적인내용에만집중할수있다. ArrayMax(A,n) tmp A[0]; for i 1 to n-1 do if tmp < A[i] then tmp A[i]; return tmp; 대입연산자가 임을유의
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 type) 데이터의집합과연산의집합 ( 예 ) int 데이터타입 데이터 : {,-2,-1,0,1,2, } 연산 : +, -, /, *, % 추상데이터타입 (ADT: Abstract Data Type) 데이터타입을추상적 ( 수학적 ) 으로정의한것 데이터나연산이무엇 (what) 인가는정의되지만데이터나연산을어떻게 (how) 컴퓨터상에서구현할것인지는정의되지않는다.
추상데이터타입의정의 객체 : 추상데이터타입에속하는객체가정의된다. 연산 : 이들객체들사이의연산이정의된다. 이연산은추상데이터타입과외부를연결하는인터페이스의역할을한다. 2 3 객체 9 7 연산 8 추상데이터타입
추상데이터타입의예 : 자연수 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;
추상데이터타입과 VTR 사용자들은추상데이터타입이제공하는연산만을사용할수있다. 사용자들은추상데이터타입을어떻게사용하는지를알아야한다. 사용자들은추상데이터타입내부의데이터를접근할수없다. 사용자들은어떻게구현되었는지몰라도이용할수있다. 만약다른사람이추상데이터타입의구현을변경하더라도인터페이스가변경되지않으면사용할수있다. VCR 의인터페이스가제공하는특정한작업만을할수있다. 사용자는이러한작업들을이해해야한다. 즉비디오를시청하기위해서는무엇을해야하는지를알아야한다. VCR 의내부를볼수는없다. VCR 의내부에서무엇이일어나고있는지를몰라도이용할수있다. 누군가가 VCR 의내부의기계장치를교환한다고하더라도인터페이스만바뀌지않는한그대로사용이가능하다.
알고리즘의성능분석 알고리즘의성능분석기법 수행시간측정 두개의알고리즘의실제수행시간을측정하는것 실제로구현하는것이필요 동일한하드웨어를사용하여야함 알고리즘의복잡도분석 직접구현하지않고서도수행시간을분석하는것 알고리즘이수행하는연산의횟수를측정하여비교 일반적으로연산의횟수는 n의함수 시간복잡도분석 : 수행시간분석 공간복잡도분석 : 수행시필요로하는메모리공간분석
수행시간측정 컴퓨터에서수행시간을측정하는방법에는주로 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); }
복잡도분석 시간복잡도는알고리즘을이루고있는연산들이몇번이나수행되는지를숫자로표시 산술연산, 대입연산, 비교연산, 이동연산의기본적인연산 : 수헹시간이입력의크기에따라변하면안됨 : 기본적인연산만 알고리즘이수행하는연산의개수를계산하여두개의알고리즘을비교할수있다. 연산의수행횟수는고정된숫자가아니라입력의개수 n 에대한함수 -> 시간복잡도함수라고하고 T(n) 이라고표기한다. 프로그램 A 프로그램 B 워드 2005 워드 2000 연산의수 = 8 3n+2 연산의수 =26 5n 2 +6
복잡도분석의예 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 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
연산의횟수를그래프로표현 연산의횟수 알고리즘 C 알고리즘 B 알고리즘 A 입력의개수 n
시간복잡도함수계산예 코드를분석해보면수행되는수행되는연산들의횟수를입력크기의함수로만들수있다. 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( 최대 )
빅오표기법 자료의개수가많은경우에는차수가가장큰항이가장영향을크게미치고다른항들은상대적으로무시될수있다. ( 예 ) n=1,000 일때, T(n) 의값은 1,001,001 이고이중에서첫번째항인의값이전체의약 99% 인 1,000,000 이고두번째항의값이 1000 으로전체의약 1% 를차지한다. 따라서보통시간복잡도함수에서가장영향을크게미치는항만을고려하면충분하다. 빅오표기법 : 연산의횟수를대략적 ( 점근적 ) 으로표기한것 두개의함수 f(n) 과 g(n) 이주어졌을때, n=1000인경우 T(n)= n 2 + n + 1 99% 1% 연산의횟수 O( f ( n)) 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) n 0 입력의개수 n
빅오표기법의예
빅오표기법의종류 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 시간복잡도 1 2 4 8 16 32 1 1 1 1 1 1 1 logn 0 1 2 3 4 5 n 1 2 4 8 16 32 nlogn 0 2 8 24 64 160 n 2 1 4 16 64 256 1024 n 3 1 8 64 512 4096 32768 2 n 2 4 16 256 65536 4294967296 n! 1 2 24 40326 20922789888000 26313 10 33
빅오표기법이외의표기법 빅오메가표기법. 모든 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) 빅세타표기법 모든 n n 0 에대하여 c 1 g(n) f(n) c 2 g(n) 을만족하는 3 개의상수 c 1, c 2 와 n 0 가존재하면 f(n)=θ(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)) 하한입력의개수 n
수행시간 최선, 평균, 최악의경우 알고리즘의수행시간은입력자료집합에따라다를수있다. ( 예 ) 정렬알고리즘의수행시간은입력집합에따라다를수있다. 최선의경우 (best case): 수행시간이가장빠른경우 평균의경우 (average case): 수행시간이평균적인경우 최악의경우 (worst case): 수행시간이가장늦은경우 100 50 A B C D E F G 입력집합 최악의경우 평균적인경우 최선의경우 최선의경우 : 의미가없는경우가많다. 평균적인경우 : 계산하기가상당히어려움. 최악의경우 : 가장널리사용된다. 계산하기쉽고응용에따라서중요한의미를가질수도있다. ( 예 ) 비행기관제업무, 게임, 로보틱스
최선, 평균, 최악의경우 ( 예 ) 순차탐색 최선의경우 : 찾고자하는숫자가맨앞에있는경우 O(1) 최악의경우 : 찾고자하는숫자가맨뒤에있는경우 O(n) 평균적인경우 : 각요소들이균일하게탐색된다고가정하면 (1+2+ +n)/n=(n+1)/2 O(n)
자료구조의 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; } 연산을호출할때구조체를함수의파라미터로전달
자료구조기술규칙 상수 대문자로표기 ( 예 ) #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; typedef < 새로운타입의정의 > < 새로운타입이름 >; struct ListNode *link; } ListNode;