슬라이드 1

Similar documents
슬라이드 1

슬라이드 1

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

슬라이드 1

슬라이드 1

chap x: G입력

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

02장.배열과 클래스

11장 포인터

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

슬라이드 1

chap01_time_complexity.key

중간고사

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - ch07 - 포인터 pm0415

Microsoft PowerPoint - 08-Queue.ppt

untitled

Microsoft PowerPoint - 05-chap03-ArrayAndPointer.ppt

슬라이드 1

Chapter 4. LISTS

슬라이드 1

chap 5: Trees

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

중간고사 (자료 구조)

03_queue

Chap 6: Graphs

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

Chapter 4. LISTS

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

Microsoft PowerPoint - chap-11.pptx

Chap 6: Graphs

06장.리스트

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

untitled

금오공대 컴퓨터공학전공 강의자료

슬라이드 1

Microsoft PowerPoint - 제11장 포인터(강의)

OCW_C언어 기초

11장 포인터

5.스택(강의자료).key

본 강의에 들어가기 전

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션

Microsoft PowerPoint - 제11장 포인터

제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.

C 언어 프로그래밊 과제 풀이

03장.스택.key

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

Microsoft PowerPoint - chap03-변수와데이터형.pptx

1장. 리스트

Chap 6: Graphs

제 14 장포인터활용 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.

C 프로그래밊 개요

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2

untitled

슬라이드 1

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

슬라이드 1

슬라이드 1

PowerPoint 프레젠테이션

04장.큐

Microsoft PowerPoint - chap06-2pointer.ppt

K&R2 Reference Manual 번역본

2002년 2학기 자료구조

슬라이드 1

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

슬라이드 1

슬라이드 1

17장 클래스와 메소드

Microsoft PowerPoint - chap11-포인터의활용.pptx

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

Lab 3. 실습문제 (Single linked list)_해답.hwp

JAVA PROGRAMMING 실습 08.다형성

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

프로그래밍개론및실습 2015 년 2 학기프로그래밍개론및실습과목으로본내용은강의교재인생능출판사, 두근두근 C 언어수업, 천인국지음을발췌수정하였음

KNK_C_05_Pointers_Arrays_structures_summary_v02

< E20C6DFBFFEBEEE20C0DBBCBAC0BB20C0A7C7D12043BEF0BEEE20492E707074>

Microsoft PowerPoint - Chapter_08.pptx

Microsoft PowerPoint - 제4장-스택과큐.pptx

Microsoft PowerPoint - 제3장-배열.pptx

정보

Microsoft PowerPoint - 3ÀÏ°_º¯¼ö¿Í »ó¼ö.ppt

Microsoft PowerPoint - additional01.ppt [호환 모드]

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

untitled

C 프로그래밊 개요

슬라이드 1

Frama-C/JESSIS 사용법 소개

알고리즘 1장 기본개념


Microsoft PowerPoint 알고리즘 개요(Part 1).pptx

쉽게 배우는 알고리즘 강의노트

Microsoft PowerPoint - chap10-함수의활용.pptx

1. auto_ptr 다음프로그램의문제점은무엇인가? void func(void) int *p = new int; cout << " 양수입력 : "; cin >> *p; if (*p <= 0) cout << " 양수를입력해야합니다 " << endl; return; 동적할

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

ch15

설계란 무엇인가?

슬라이드 1

Transcription:

CHAP 1: 자료구조와알고리즘

일상생활에서의사물의조직화 조직도 일상생활에서의사물의조직화 Ticket Box

일상생활과자료구조의비교 일상생활에서의예 물건을쌓아두는것 영화관매표소의줄 할일리스트 자료구조 스택 큐 리스트 a b c NULL C B A 영어사전사전, 탐색구조 Ticket Box 지도 조직도 그래프 트리 전단 (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를반환

흐름도로표기된알고리즘 직관적이고이해하기쉬운 알고리즘기술방법 그러나복잡한알고리즘의경우, 상당히복잡해짐. ArrayMax tmp A[0] i 1 i < n no yes no A[i]>tmp yes tmp A[i] return 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+1) <= 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 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

연산의횟수를그래프로표현 연산의횟수 알고리즘 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( 최대 )

빅오표기법 1/2 자료의개수가많은경우에는차수가가장큰항이가장영향을크게미치고다른항들은상대적으로무시될수있다. ( 예 ) n=1,000 일때, T(n) 의값은 1,001,001 이고이중에서첫번째항인 n 2 의값이전체의약 99% 인 1,000,000 이고두번째항인 n 의값이 1000 으로전체의약 1% 를차지한다. 따라서보통시간복잡도함수에서가장영향을크게미치는항만을고려하면충분하다. n=1000 인경우 T(n)= n 2 + n + 1 99% 1% 입력의개수 n

빅오표기법 2/2 빅오표기법 : 연산의횟수를대략적 ( 점근적 ) 으로표기한것 두개의함수 f(n) 과 g(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) 연산의횟수 O( g( n)) f (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 log(n) 0 1 2 3 4 5 n 1 2 4 8 16 32 n*log(n) 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( g( n)) 상한 f (n) 하한 ( g( n)) n 0 입력의개수 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)= θ(g(n)) 이다. ( 예 ) n 1이면 n 2n+1 3n이므로 2n+1 = θ(n) 연산의수 O( g( n)) 상한 f (n) 하한 ( g( n)) n 0 입력의개수 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 < 새로운타입의정의 > < 새로운타입이름 >; ( 예 ) typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode;