Microsoft PowerPoint - 05알고리즘.pptx

Similar documents
Microsoft PowerPoint - 04알고리즘

Microsoft PowerPoint - 04알고리즘

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

2002년 2학기 자료구조

정보

슬라이드 1

슬라이드 1

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

슬라이드 1

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

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

chap 5: Trees

알고리즘 1장 기본개념

Algorithms

chap 5: Trees

chap x: G입력

Ch.8 Procedures and Environments

슬라이드 1

Discrete Mathematics

입학사정관제도

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

Microsoft PowerPoint - chap10_tree

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

Chap 6: Graphs

Microsoft PowerPoint - 6장 탐색.pptx

슬라이드 1

Microsoft PowerPoint Merging and Sorting Files.ppt

Ch.1 Introduction

Microsoft PowerPoint - lec07_tree [호환 모드]

슬라이드 1

설계란 무엇인가?

Microsoft PowerPoint - 26.pptx

제 11 장 다원 탐색 트리

Visual Basic 반복문

06_sorting

<4D F736F F F696E74202D203728B0E8BBEABAB9C0E2B5B5B0B3B7D02DC1A4B7C4B9AEC1A6292E BC8A3C8AF20B8F0B5E55D>

PowerPoint Presentation

7장

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

PowerPoint 프레젠테이션

Microsoft PowerPoint - ch00 - Introduction to Programming Language Lecture

슬라이드 1

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

6장정렬알고리즘.key

chap01_time_complexity.key

슬라이드 1

슬라이드 1

Microsoft PowerPoint - 5장 정렬

<4D F736F F F696E74202D2031C1D6C2F72D31C2F7BDC32028B0ADC0C7C0DAB7E D20C7C1B7CEB1D7B7A1B9D6BEF0BEEE20B0FAB8F1BCD2B

Microsoft PowerPoint - chap-11.pptx

Microsoft PowerPoint - ch07 - 포인터 pm0415

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

Chapter 4. LISTS

슬라이드 1

05_tree

01

08장.트리

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

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

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

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

Microsoft PowerPoint Predicates and Quantifiers.ppt

14장.탐색

PowerPoint 프레젠테이션

statistics

Chapter 08. 트리(Tree)

슬라이드 1

1장. 리스트

Chapter 4. LISTS

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

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 가함수이므로

Chap 6: Graphs

11장 포인터

슬라이드 1

09J1_ _R.hwp

Microsoft PowerPoint - chap06-2pointer.ppt

Microsoft PowerPoint Relations.pptx

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

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

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

<C6F7C6AEB6F5B1B3C0E72E687770>

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

EA0015: 컴파일러

제 3강 역함수의 미분과 로피탈의 정리

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

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

31. 을전개한식에서 의계수는? 를전개한식이 일 때, 의값은? 을전개했을때, 의계수와상수항의합을구하면? 을전개했을때, 의 계수는? 를전개했을때, 상수항을 구하여라. 37

歯MW-1000AP_Manual_Kor_HJS.PDF

Microsoft Word - FunctionCall

슬라이드 1

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

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B62D DBFB5BBF3BCF6BEF72DC5E4BFE4C0CFBCF6BEF72E >

Microsoft PowerPoint - 제8장-트리.pptx

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

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

중간고사

이 장에서 사용되는 MATLAB 명령어들은 비교적 복잡하므로 MATLAB 창에서 명령어를 직접 입력하지 않고 확장자가 m 인 text 파일을 작성하여 실행을 한다

슬라이드 1

Transcription:

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

꿈의중독자가되라 출처 : 조영탁의행복한경영이야기나는여러분이 꿈중독자 가되었으면합니다. 꿈이크고꿈이선명하면남이하지말라고해도스스로열심히노력하게될것입니다. 반대로꿈이없다면내가지금무엇을해야하는지알지못합니다. 그래서자기도모르게시간을낭비하게됩니다. 그런하루하루가쌓이면시간이갈수록엄청난차이가생기게되는것입니다. - 김우중대우창업회장, 김우중어록 에서 전세계를누볐던 80대노기업가가, 2017년 GYBM( 김우중사관학교 ) 20대연수생과의대화에서강조한내용입니다. 젊은이뿐만아니라이시대를살아가는모든이에게들려주는메시지라생각합니다. 일단꿈부터, 큰꿈을꾸는것부터시작해야합니다. 거기서새로운인생이시작됩니다. 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 명 ( 즉해외여행경험이있는사람중동남아만가본사람이 20 명 ) 유럽여행경험자 전체 60 명 A U A B 동남아여행경험자 5명 3 B

오늘의강의목표 알고리즘 (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) 예제 4 : 3, 2, 4, 1, 5 page 222 15

삽입정렬 (insert sort) 예제 5 : 3, 2, 4, 1, 5 page 223 1) [2] 과앞의원소처음부터비교 : 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 거스름돈문제 : 224 page 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 거스름돈문제 -1 : 224 page 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

정렬알고리즘퀵정렬 (quick sort) 21

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

정렬알고리즘병합정렬 (merge sort) 2. 병합 3. Sorting 과정 23

트리 (Tree) 이진트리 포화이진트리 완전이진트리 편향이진트리 24

힙 (Heap) 완전이진트리에있는노드중에서 키값이가장큰노드나키값이가장작은노드를찾기위해서만든자료구조 최대힙 부모노드의키값이자식노드의키값보다항상크거나같은크기의관계 최소힙 부모노드의키값이자식노드의키값보다항상작거나같은크기의관계 25

힙 (Heap) 26

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

정렬알고리즘힙정렬 (heap sort) 28

정렬알고리즘힙정렬 (heap sort) 29

정렬알고리즘힙정렬 (heap sort) 30

정렬알고리즘힙정렬 (heap sort) 31

정렬알고리즘힙정렬 (heap sort) 32

정렬알고리즘힙정렬 (heap sort) 33

정렬알고리즘힙정렬 (heap sort) 34

정렬알고리즘힙정렬 (heap sort) 35

정렬알고리즘힙정렬 (heap sort) 36

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

알고리즘복잡도 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 38

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

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

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

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

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

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

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 를선택하여풀면된다. 45

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

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이존재 47

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