Microsoft PowerPoint - 04알고리즘

Similar documents
Microsoft PowerPoint - 04알고리즘

Microsoft PowerPoint - 05알고리즘.pptx

2002년 2학기 자료구조

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

정보

chap 5: Trees

슬라이드 1

슬라이드 1

알고리즘 1장 기본개념

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

Algorithms

슬라이드 1

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

chap x: G입력

슬라이드 1

-09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - - 한빛미디어 Sortng Algorth

Ch.8 Procedures and Environments

Discrete Mathematics

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

Chap 6: Graphs

슬라이드 1

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

Microsoft PowerPoint - 26.pptx

슬라이드 1

chap 5: Trees

슬라이드 1

슬라이드 1

PowerPoint Presentation

쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table

Microsoft PowerPoint - 6장 탐색.pptx

설계란 무엇인가?

06_sorting

Microsoft PowerPoint - chap10_tree

Visual Basic 반복문

<4D F736F F F696E74202D203728B0E8BBEABAB9C0E2B5B5B0B3B7D02DC1A4B7C4B9AEC1A6292E BC8A3C8AF20B8F0B5E55D>

chap01_time_complexity.key

6장정렬알고리즘.key

Microsoft PowerPoint Merging and Sorting Files.ppt

Ch.1 Introduction

Microsoft PowerPoint - 5장 정렬

Microsoft PowerPoint - ch00 - Introduction to Programming Language Lecture

Microsoft PowerPoint - chap-11.pptx

Microsoft PowerPoint - ch07 - 포인터 pm0415

PowerPoint 프레젠테이션

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

SNU =10100 =minusby by1000 ÇÁto0.03exÇÁto0.03exÇÁ=10100 =minusby by1000 ·Îto0.03ex·Îto0.03ex·Î=10100 =minusby by1000

Microsoft PowerPoint - ch11_정렬 [호환 모드]

Chapter 4. LISTS

윈도우즈프로그래밍(1)

<4D F736F F F696E74202D2031C1D6C2F72D31C2F7BDC32028B0ADC0C7C0DAB7E D20C7C1B7CEB1D7B7A1B9D6BEF0BEEE20B0FAB8F1BCD2B

입학사정관제도

Microsoft PowerPoint Predicates and Quantifiers.ppt

Microsoft PowerPoint - lec07_tree [호환 모드]

01

Microsoft PowerPoint Relations.pptx

14장.탐색

7장

Chap 6: Graphs

쉽게배우는알고리즘 8장. 동적프로그래밍 프로그래밍 Dynamic Programming (DP)

PowerPoint 프레젠테이션

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2

statistics

<C6F7C6AEB6F5B1B3C0E72E687770>

예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = B = >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = >> tf = (A==B) % A

PowerPoint 프레젠테이션

제 11 장 다원 탐색 트리

Microsoft PowerPoint - chap06-2pointer.ppt

o 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. o 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 o 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드,

05_tree

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


Microsoft Word - FunctionCall

<B4EBC7D0BCF6C7D02DBBEFB0A2C7D4BCF62E687770>

FGB-P 학번수학과권혁준 2008 년 5 월 19 일 Lemma 1 p 를 C([0, 1]) 에속하는음수가되지않는함수라하자. 이때 y C 2 (0, 1) C([0, 1]) 가미분방정식 y (t) + p(t)y(t) = 0, t (0, 1), y(0)

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

11장 포인터

Chapter 4. LISTS

歯MW-1000AP_Manual_Kor_HJS.PDF

Overview Decision Tree Director of TEAMLAB Sungchul Choi

Poison null byte Excuse the ads! We need some help to keep our site up. List 1 Conditions 2 Exploit plan 2.1 chunksize(p)!= prev_size (next_chunk(p) 3

슬라이드 1

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

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각

Microsoft PowerPoint - 27.pptx

정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2

데이터 구조의 개요

HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M.

1 1 장. 함수와극한 1.1 함수를표현하는네가지방법 1.2 수학적모형 : 필수함수의목록 1.3 기존함수로부터새로운함수구하기 1.4 접선문제와속도문제 1.5 함수의극한 1.6 극한법칙을이용한극한계산 1.7 극한의엄밀한정의 1.8 연속

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B62D DBFB5BBF3BCF6BEF72DC5E4BFE4C0CFBCF6BEF72E >

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

슬라이드 1

adfasdfasfdasfasfadf

3.2 함수의정의 Theorem 6 함수 f : X Y 와 Y W 인집합 W 에대하여 f : X W 는함수이다. Proof. f : X Y 가함수이므로 f X Y 이고, Y W 이므로 f X W 이므로 F0이만족된다. 함수의정의 F1, F2은 f : X Y 가함수이므로

슬라이드 1

스무살, 마음껏날아오르기위해, 일년만꾹참자! 2014학년도대학수학능력시험 9월모의평가 18번두이차정사각행렬 가 를만족시킬때, 옳은것만을 < 보기 > 에서있는대로고른것은? ( 단, 는단위행렬이다.) [4점] < 보기 > ㄱ. ㄴ. ㄷ. 2013학년도대학수학능력시험 16번

중간고사

Chapter 08. 트리(Tree)

정렬문제란크기비교가가능한데이터의시퀀스를오름또는내림차순으로재배치하는문제를말한다. 즉, 다음의정수리스트를오름차순으로정렬하면, [4,2,3,1,6,8,3,2,6,7] 다음과같이된다. [1,2,2,3,3,4,6,6,7,8] 이장에서는정수리스트를오름차순으로정렬하는함수를다양한알고

Transcription:

이산수학 Discrete Mathematics 알고리즘 (Algorithm) 인천대학교컴퓨터공학과공학시인이숙이철호교수 Jullio@chol.com zullio@inu.ac.kr 010 3957 6683 모바일컴퓨팅연구실 07 401 호

상어가바다의절대제왕이된이유 출처 : 조영탁의행복한경영이야기 상어는물고기중유일하게부레가없다. 부레없는물고기는물속에서생존이불가능하다. 행동이매우불편하고, 조금만바다속에머물러있어도바닥으로가라앉아죽고만다. 상어는태어난순간부터죽을때까지끊임없이몸을움직여야했다. 에릭호퍼는말합니다. 불완전한열등동물인인간이자연계에서동물이상의존재가될수있었던것은약점을이점으로바꾸는비범한천재적재능덕분이었다. 주어진조건이아닌나의대응이결과를만듭니다. 힘겨운노력이쌓여상어는바다의절대제왕으로거듭났다. - 유대인생각공부 ( 쑤린지음 ) 에서 2

지난주에 어떤회사에근무하는 60 명의직원에게해외여행경험을물었다. 유럽여행을가본사람은 35 명, 동남아여행을가본사람은 28 명이었다. 해외여행을한번도가본적이없는사람은 5 명이었다. 동남아여행은가봤지만유럽여행을가본적없는사람은몇명일까? 유럽여행자 : A = 35 명동남아여행자 : B = 28 명전체 : U = 60 명 ~(A U B) = 5 명 A U B = U 5 = 55 명 A B = (A + B) (A U B ) = 35 + 28 55 = 8 ~A = B - A B = 28 8 = 20 유럽만가본사람 : 27 동남아만가본사람 : 20 둘다가본사람 : A B = 8 그러므로여행경험자중유럽을가본적없는사람은 20 명 ( 즉동남아만가본사람 ) 유럽여행경험자 전체 60 명 A U A B 동남아여행 B 경험자 5명 3

오늘의강의목표 알고리즘 (Algorithm) - 알고리즘 - 탐색 (search) - 정렬 (sort) - 함수의증가 - 알고리즘복잡도 4

알고리즘이란? 알고리즘 (algorithm) : 컴퓨터프로그램으로특정한일을수행하는명령어의유한한순서있는집합 가장효율적인알고리즘을찾는것이중요 수학 문제를풀기위해정의나정리들을활용 컴퓨터 수행가능한효율적인알고리즘을사용 1830 년배비지 (Babbage) 와러브레이스 (Lovelace) 처음주창 1973 년컴퓨터과학자인크누스 (Knuth) 정립 컴퓨터프로그래밍의기술 (The Art of Computer Programming) 5

알고리즘 알고리즘 (algorithm) 특정문제를해결하기위해기술한일련의명령문 프로그램 (program) 알고리즘을컴퓨터가이해하고실행할수있는특정프로그래밍언어로표현한것표현 : 순서도 (flow chart), 유사코드 (pseudo code), 언어 (language) 6

알고리즘의주요특성 1) 입력 (input) : 문제를풀기위한입력 2) 출력 (output) : 문제를해결했을때답의출력 3) 명확성 (definiteness) : 각단계가실행된후에는결과가확정 ( 정의 ) 4) 정확성 (correctness) : 주어진문제를정확하게해결해야함 5) 유한성 (finiteness) : 유한횟수의명령이수행된후출력을만들어야 6) 효율성 (effectiveness) : 정확하면서도효율적으로유한시간내에수행 7) 일반성 (generality) : 요구되는형태의모든문제에적용 7

자료구조와알고리즘 프로그램 = 자료구조 + 알고리즘 ( 예 ) 최대값탐색프로그램 = 배열 + 순차탐색 자료구조 알고리즘 score[] 80 70 90 30 tmp score[0]; for i 1 to n do if score[i]>tmp then tmp score[i]; 8

탐색 (search) 알고리즘 탐색 (search) 주어진파일또는원소들중에서어떤특정한원소를찾는것 선형 ( 순차 ) 탐색 (sequential search) : 원소들이정렬되어있지않을경우 원소들을처음부터비교하여찾는것 이진탐색 (binary search) : 원소들이정렬되어있을경우 순차탐색보다빠름배열가운데의원소값과찾으려는값을비교하여, 비교된결과에따라왼쪽원소의배열또는오른쪽원소의배열중에서다시찾기를계속함 9

선형탐색 (sequential search) 10

이진탐색 (binary search) 11

이진탐색 (binary search) 예제 3-page 220 1, 2, 3, 5, 6, 7, 8, 10, 12,13,15,16,18,19,20,22 19를찾음??? 1. 두개로나눔 a) 1, 2, 3, 5, 6, 7, 8, 10 b) 12,13,15,16,18,19,20,22 2. 찾으려는 19와 a) 의가장마지막큰항과비교하면 19가큼으로 b) 를둘로쪼개서탐색 c) 12,13,15,16 d) 18,19,20,22 3. c) 의마지막항과 19 를비교하여크므로 d) 를둘로나누어탐색 e) 18,19 f) 20,22 4. e) 의마지막항과 19 를비교, 크지않으므로둘로나눔 g) 18 h) 19 5. 탐색하려는 19 가 g) 의 18 보다크므로 h) 항으로탐색 6. 탐색처음포이트가끝포이트보다작지않으며, 19 와같은지를비교하여, 같으면탐색결과를찾았다고보고. 12

분할정복알고리즘 (divide and conquer algorithms) 그대로해결할수없는문제를작은문제로분할하여, 문제를해결하는방법이나알고리즘알고리즘이효율적인이유 큰문제를작은문제로나누어서해결할수있음 13

정렬 (sort) 알고리즘 임의로나열되어있는데이터주어진항목에따라크기순서대로작은순서부터 ( 오름차순, ascending order) 또는큰순서부터 ( 내림차순, descending order) 늘어놓는것 정렬되어있는데이터들은다음과같은작업을수행할때응용 (1) 데이터를탐색할때 (2) 리스트 (list) 에있는다른항목들을비교할때 14

버블정렬 (bubble sort) 15

삽입정렬 (insert sort) 예제 5 : 3, 2, 4, 1, 5 1) [3] 과앞의원소처음부터비교 : 3, [2], 4, 1, 5 2, [3], 4, 1, 5 2) [4] 와앞의원소처음부터비교 : 2, 3, [4], 1, 5 2, 3, [4], 1, 5 3) [1] 과앞의원소처음부터비교 : 2, 3, 4, [1], 5 1, 2, 3, 4, [5] 4) [5] 와앞의원소처음부터비교 : 1, 2, 3, 4, [5] 1, 2, 3, 4, 5 16

욕심쟁이알고리즘 (greedy algorithm) 최적해문제 매선택에서지금당장의순간에최적인해를수행 전체적으로최적해가아닐수있음 17

욕심쟁이알고리즘 (greedy algorithm) 예제 6 거스름돈문제 25 센트, 10 센트, 5 센트, 1 센트동전으로가장적은수의동전을사용하여 67 센트를거슬러주는방법 1) 67 25 = 42 센트 25 센트 1 개 2) 42 25 = 17 센트 25 센트 1 개 3) 17 10 = 7 센트 10 센트 1 개 4) 7 5 = 2 센트 5 센트 1 개 5) 2 1 = 1 센트 1 센트 1 개 6) 1-1 = 0 센트 1 센트 1 개전체해 ) 25 센트 2 개, 10 센트 1 개, 5 센트 1 개, 1 센트 2 개 18

욕심쟁이알고리즘 (greedy algorithm) 예제 6 거스름돈문제 25 센트, 10 센트, (5 센트 : 사용안함 ), 1 센트동전으로가장적은수의동전을사용하여 30 센트를거슬러주는방법 1) 30 25 = 5센트 25센트 1개 2) 5 1 = 4센트 1센트 1개 3) 4 1 = 3센트 1센트 1개 4) 3 2 = 2센트 1센트 1개 5) 2 1 = 1센트 1센트 1개 6) 1-1 = 0센트 1센트 1개 전체해 ) 25센트 1개, 1센트 5개 전체 6개사용 그러나 10센트 3개로해결가능 19

정렬알고리즘 퀵정렬 (quick sort) - 분할정복방법을통해리스트를정렬 - 리스트가운데서하나의원소를고름 ( 피벗 ) - 피벗앞에는피벗보다값이작은모든원소들이오고, 피벗뒤에는피벗보다값이큰모든원소들이오도록피벗을기준으로리스트를둘로나눔 ( 분할 ) - 분할을마친뒤에피벗은더이상움직이지않는다. - 분할된두개의작은리스트에대해 - 재귀 (Recursion) 적으로이과정을반복 - 재귀는리스트의크기가 0 이나 1 이될때까지반복 - 재귀호출이한번진행될때마다최소한하나의원소는최종적으로위치가정해짐. 20

정렬알고리즘 병합정렬 (merge sort) 리스트의길이가 0 또는 1 이면이미정렬된것 정렬되지않은리스트를절반으로잘라비슷한크기의두부분리스트로나눔 각부분리스트를재귀적으로합병정렬 두부분리스트를다시하나의정렬된리스트로합병 21

정렬알고리즘 힙정렬 (heap sort) 1) n 개의노드에대한완전이진트리를구성루트노드부터부노드, 왼쪽자노드, 오른쪽자노드순으로구성 2) 최대힙을구성최대힙이란부노드가자노드보다큰트리를말함단말노드를자노드로가진부노드부터구성아래부터루트까지올라오며순차적으로만들어감 3) 가장큰수 ( 루트에위치 ) 를가장작은수와교환 4) 2) 와 3) 을반복한다. 힙 (heap) : 최댓값및최솟값을찾아내는연산을빠르게하기위해고안된완전이진트리 (Complete binary tree) 를기본으로한자료구조 (treebased structure) 22

알고리즘의복잡도 시간복잡도 (time complexity) 알고리즘수행시간분석결과 공간복잡도 (space complexity) 알고리즘의메모리사용량에대한분석결과 23

알고리즘복잡도 O(1) : 상수 (constant) O(log n) : 로그 (logarithmic) O(n) : 1차 (linear) O(n log n) : 선형연산 (linear-arithmetic) O(n 2 ) : 2차 (quadratic) O(n 3 ) : 3차 (cubic) O(2 n ) : 지수 (exponential) O(n!) : factorial 24

알고리즘복잡도 big-o 추정에따른함수들의증가그래프 함수의증가값 N 값 25

차수그래프 상한값표시하한값표시중간값표시 26

함수의증가 ( 복잡도 ) big-o 표기 : 최악의경우복잡도 ( 상한선표기법 ) big-omega 최선의복잡도 ( 하한선표기법 ) big-theta 평균복잡도 27

big-o 표기법 최악의경우복잡도 ( 상한선표기법 ) 임의의함수에대하여 " 함수의입력값 ( 정의역의원소 ) 이커짐에따라그출력값 ( 그원소의상 ) 이얼마나빠르게커지는가 " 를표현 28

big-omega 표기법 최선의복잡도 ( 하한선표기법 ) big-theta 표기법평균복잡도 29

big-o 표기법 ( 상한표기법 ) 어떤함수 g(n) 이 O(n 2 ) 에속한다는말은함수 g(n) 이임의의 N 값보다큰값에대하여어떤 2차함수 cn 2 보다는작은값을가지게된다는의미 그래프상에서아래에위치한다는의미 즉그함수 g(n) 은어떤 2차함수 cn 2 보다는궁극적으로좋다는의미 30

big-o 표기의예 ( 예제 1-page 234) 보이라 은 임을 풀이 ) x >1 일때, x < x 2 이고 1 < x 2 이다 x > 1에서 (C = 4, k=1) x > 2 에서 (C = 3, k=2) Big O 를보이는데단지한가지해답이있는것이아니다. 적당히큰 k 과 C 를선택하여풀면된다. 31

big-omega( ) ( 하한표기법 ) 어떤함수 g(n) 이 (n 2 ) 에속한다는말은그함수는궁극에가서는어떤임의의 N 값보다큰값에대해서는어떤 2차함수cn 2 의값보다는큰값을가지게된다는것을의미 그래프상에서는윗부분에위치 그함수g(n) 은어떤2차함수cn 2 보다는궁극적으로나쁘다는의미 32

big-theta 표기법 함수 f(n) 에대해서 (f(n)) = O(f(n)) (f(n)) 의관계가성립즉, n N 인모든정수n에대해서 c f(n) g(n) d f(n) 이성립하는실수 c 0와 d 0, 그리고음이아닌정수 N이존재 33

쉬어가는시간 1 g 또하나의천칭문제??? 1 g 단위로자를수있는 40 g 짜리분동이있다. 이것을잘라서 1 ~ 40 g까지무게를측정하려한다. 40 g짜리분동을가장적은수의토막으로잘라만들려면어떻게잘라야할까? (40 개 ) 이름, 학번, 답과이유를설명 1 g 짜리 40 개가위와같이있다. 어떻게잘라야할까? 34