이산수학 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