정보

Size: px

Start display at page:

Download "정보"

형석 백
5 years ago
Views:

1 정보 Sangwook Lee Deogi High School

2 III 문제해결과프로그래밍 1 추상화 2 알고리즘 3 프로그래밍

3 2 알고리즘 2-1 알고리즘설계 2-2 알고리즘분석 3

4 2-1 알고리즘설계 (p.108) 학습목표 순차, 선택, 반복구조의흐름을설명할수있다. 다양한제어구조를활용하여논리적이고효율적인알고리즘을설계할수있다. 4

5 [1] 알고리즘제어구조 (p.109) 알고리즘 (algorithm) 이란 문제를해결하기위한논리적인절차나방법 생활속의알고리즘 자동판매문제를해결하기위한자판기를작동시키는절차 배고픔의문제를해결하기위한음식을배달시켜먹는절차 5

6 [1] 알고리즘제어구조 (p.109) 알고리즘의조건 입력과출력이있어야한다 처리과정이명확해야한다 실행가능해야한다 종료되어야한다 배고픔해결알고리즘에서입출력은 음식선택, 음식값지불, 음식도착등이해당 6

7 [1] 알고리즘제어구조 (p.109) 알고리즘표현방법 자연어 순서도 의사코드 프로그래밍언어 7

8 [1] 알고리즘제어구조 (p.109) 순서도 기호 ( 도형 ) 를사용하여알고리즘을표현하는방법 ( 또는표현한것 ) < 제기능을하지않는램프를다루기위한순서도 > 8

9 [1] 알고리즘제어구조 (p.109) 단말 순서도에사용되는기호 ( 도형 ) 의의미 단말 반복 C 언어의 for 반복구조를표현 처리 흐름 입출력 read, print 등표시하여입출력구분필요 준비 변수선언및초기화 판단 출력 선택이나반복구조를만들때사용 편리함과가독성을위해출력시사용권장 9

10 [1] 알고리즘제어구조 (p.109) 의사코드 (pseudo-code) 란 일반적인 ( 일상적인 ) 언어를사용하여프로그래밍언어를흉내내어알고리즘을표현하는방법 ( 또는작성한코드 ) <C 스타일의사코드 > 아침이올때까지할일을작성한의사코드 10

11 [1] 알고리즘제어구조 (p.109) 알고리즘속에존재하는작업처리흐름유형 순차적처리흐름 선택적처리흐름 반복적처리흐름 순차선택반복 < 알고리즘속작업처리흐름 > 11

12 [1] 알고리즘제어구조 (p.109) 제어구조란 처리흐름을제어하는 ( 표현하는 ) 알고리즘속문장구조 알고리즘을작성하는과정은제어구조를만들어가는과정 알고리즘을표현하는방법에따라문장구조가아니라도형구조가될수있음 12

13 [1] 알고리즘제어구조 (p.109) 제어구조종류 순차 ( 제어 ) 구조 순차적처리흐름을표현하는구조 작업을제시된순서대로처리해야될때사용 선택 ( 제어 ) 구조 선택적처리흐름을표현하는구조 조건에따라여러작업중하나를선택하여처리해야될때사용 반복 ( 제어 ) 구조 반복적처리흐름을표현하는구조 조건에따라특정작업을반복하여처리해야될때사용 13

14 [1] 알고리즘제어구조 (p.109) < 순서도로표현한제어구조 > 14

15 [2] 알고리즘설계와작성 (p.110) 순차구조가사용되는경우 <1 부터 100 까지의합을구하는알고리즘 > 15

16 [2] 알고리즘설계와작성 (p.110) 선택구조가사용되는경우 < 일기예보의강수확률을보고, 우산을준비하는알고리즘 > 16

17 [2] 알고리즘설계와작성 (p.110) 반복구조가사용되는경우 < 전자레인지를작동하여음식을조리하는알고리즘 > 17

18 함께해결하기 (p.111) 순차, 선택, 반복구조를찾아표시해보자. 선택구조 반복구조 순차구조 순차구조는한작업에서한작업으로만진행가능하고이전작업으로돌아갈수없는구조 선택이나반복구조를하나의처리단위로보았을때전체적으로순차구조를가짐 18

19 2-2 알고리즘분석 (p.112) 학습목표 동일한문제에대해다양한해결전략과방식이있음을설명할수있다. 알고리즘의성능을수행시간의관점에서비교하고분석하여, 어떤방식이더효율적인지설명할수있다. 19

20 [1] 동일한문제에대한다양한알고리즘 (p.113) 동일한문제에대한다양한알고리즘존재 장소이동문제해결방법 배고픔해결문제해결방법 20

21 [1] 동일한문제에대한다양한알고리즘 (p.113) 1 부터 100 까지자연수의합을구하는알고리즘 알고리즘 1 알고리즘 2 21

22 [1] 동일한문제에대한다양한알고리즘 (p.113) 알고리즘 1 알고리즘 2 덧셈을반복적으로수행하는 반복구조를사용 덧셈, 곱셈, 나눗셈연산을 한번만수행하는 순차구조를사용 알고리즘 2 는가우스덧셈공식을이용하여 1 부터 100 까지정수의합을구함 22

23 [2] 수행시간의관점에서성능분석 (p.114) 정렬이란 자료를일정한기준에의해나열하는것 정렬순서 오름차순정렬 작은것부터 내림차순정렬 큰것부터 자료를정렬하는이유 필요한자료를효율적으로탐색하기위해 23

24 [2] 수행시간의관점에서성능분석 (p.114) 정렬알고리즘종류 버블 (bubble) 정렬 선택 (selection) 정렬 < 다양한정렬알고리즘 > 24

25 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬이란 ( 오름차순 ) 인접한 2개의자료를비교하면서가장큰자료를맨뒤로보내는정렬방식 버블정렬이라고하는이유는? 데이터가교환되면서이동하는모양이 물속의거품 (bubble) 이보글보글떠오르는모양과유사하기때문 25

26 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬알고리즘 ( 오름차순 ) 1 정렬이안된자료들중에서앞쪽부터인접한두개의자료를비교하여앞의자료가더크면위치를교환하는작업을반복하면서가장큰자료를맨뒤로보냄 2 정렬되지않은나머지값들에대해 1 반복 26

27 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬예 정렬전자료 n 개의자료를버블정렬시가장큰자료를맨뒤로보내는작업을 n-1 번반복하면정렬완료 27

28 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬예 1 단계 : 가장큰자료를끝으로보내한개의자료를정렬하기 28

29 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬예 2 단계 : 두번째큰자료를끝에서두번째로보내기 29

30 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬예 3 단계 : 세번째큰자료를끝에서세번째로보내기 30

31 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬예 4 단계 : 네번째큰자료를끝에서네번째로보내기 31

32 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬예 정렬완료 4 단계정렬 3 단계정렬 2 단계정렬 1 단계정렬 비교횟수 : 10? 회 교환횟수 :? 7 회 32

33 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬비교횟수 자료의개수가 n 개일때, 1 단계비교횟수 2단계 n-2단계 비교횟수비교횟수 (n-1) + (n-2) = n n 1 2 n-1 단계비교횟수 자료의교환은 이미정렬이되어있다면한번도일어나지않을수도있지만, 한단계에서 1 회이상일어날수있기때문에일반적으로 (n-1) 회이상일어남 33

34 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬이처리속도가느린이유 앞쪽자료부터인접한자료를비교하여상호교환하는정렬방법으로자료의비교와교환이많이일어나기때문 34

35 [2] 수행시간의관점에서성능분석 (p.114) Bubble-sort with Hungarian folk dance 일반적인버블정렬알고리즘과차이점 1. 마지막두자료비교후교환이없으면두자료모두정렬된것으로간주 2. 어떤단계를종료할때까지교환이한번도없으면정렬이완료된것으로간주 35

36 [2] 수행시간의관점에서성능분석 (p.114) 버블정렬 C 코드 정렬을위해 0~4(5 단계 ) 반복지정 void main() { int data[6] = {5, 3, 8, 1, 2, 7}; int x, y, temp; for (x = 0; x <= 4; x++) { for (y = 0; y <= 4-x; y++) { } } if (data[y] > data[y+1]) { temp = data[y]; data[y] = data[y+1]; data[y+1] = temp; } x 값의 2 가지의미 ( 역할 ) 1 5 단계를반복하기위해증가하는수 2 비교하는두자료중앞자료의마지막위치를줄이는수 인접한두자료중앞자료의위치 (y) 를 1 씩증가 인접한두자료를비교하여앞자료가더크면변숫값교환 } printf(" 버블정렬결과 \n"); for (x = 0; x <= 5 ; x++) printf("%d ", data[x]); 36

37 [2] 수행시간의관점에서성능분석 (p.115) 선택정렬이란 ( 오름차순 ) 가장작은자료를선택하여첫번째자료와교환하는정렬방식 37

38 [2] 수행시간의관점에서성능분석 (p.115) 선택정렬알고리즘 ( 오름차순 ) 1 정렬이안된자료들중에서첫번째자료를 ( 임시 ) 최솟값으로지정하고최솟값과다음자료들을비교하여더작은자료를새최솟값으로지정하는과정을반복하면서가장작은자료를찾아서첫번째자료와교환 2 정렬되지않은나머지값들에대해 1 반복 최솟값위치 최솟값위치 38

39 [2] 수행시간의관점에서성능분석 (p.115) 선택정렬예 최솟값위치 39

40 [2] 수행시간의관점에서성능분석 (p.115) 선택정렬예 정렬완료 1 단계정렬 2 단계정렬 3 단계정렬 4 단계정렬 비교횟수 : 10? 회 교환횟수 :? 3 회 40

41 [2] 수행시간의관점에서성능분석 (p.115) 선택정렬비교횟수 자료의개수가 n 개일때, 1 단계비교횟수 2단계 n-2단계 비교횟수비교횟수 (n-1) + (n-2) = n n 1 2 n-1 단계비교횟수 자료의교환은 이미정렬이되어있다면한번도일어나지않을수도있지만, 한단계에서 0~1 회일어나기때문에일반적으로 (n-1) 회이하로일어남 41

42 [2] 수행시간의관점에서성능분석 (p.115) 선택정렬 C 코드 정렬을위해 0~4(5 단계 ) 반복지정 void main() { int data[6] = {5, 3, 8, 1, 2, 7}; int x, y, min, temp; x 값의 2 가지의미 ( 역할 ) 1 5 단계를반복하기위해증가하는수 2 각단계에서첫번째값의위치를나타내는수 for (x = 0; x <= 4; x++) { } min = x; for (y = x + 1; y <= 5; y++) { if (data[min] > data[y]) min = y; } temp = data[min]; data[min] = data[x]; data[x] = temp; 최솟값의위치를첫번째값의위치로임시지정 최솟값보다더작은값을찾으면해당값을새로운최솟값으로지정 } printf(" 선택정렬결과 \n"); for (x = 0; x <= 5 ; x++) printf("%d ", data[x]); 42

43 [2] 수행시간의관점에서성능분석 (p.116) 탐색이란 주어진자료들중에서원하는자료를찾는것 탐색알고리즘종류 순차탐색 (sequential search) 이진탐색 (binary search) 43

44 [2] 수행시간의관점에서성능분석 (p.116) 순차탐색 모든자료를처음부터끝까지하나씩순서대로비교하여조건에일치하는자료를찾는방법 첫번째자료부터차례로 8 이맞는지확인하여맞으면완료하고맞지않으면다음수를하나씩비교하는과정반복 <7 장의카드에서 8 이적힌숫자카드를순차탐색하는과정 > 44

45 [2] 수행시간의관점에서성능분석 (p.116) 이진탐색 정렬된자료를반으로나눈후, 찾는값이어느쪽에있는지파악해탐색의범위를반으로줄여가며자료를찾는방법 1 전체자료중에서중앙에있는 6 과찾을값 8 을비교 2 찾을값 8 이 6 보다크므로오른쪽에있는자료들을탐색 3 오른쪽자료중에서중앙에있는 8 과찾을값 8 을비교 4 중앙에있는 8 이찾을값 8 과같으므로탐색을종료 <7 장의카드에서 8 이적힌숫자카드를이진탐색하는과정 > 45

46 [2] 수행시간의관점에서성능분석 (p.116) 순차탐색 이진탐색 장점 알고리즘간단자료정렬불필요 속도빠름 단점 속도느림 알고리즘복잡자료정렬필요 기타자료수가적을때효과적자료수가많을때효과적 < 순차탐색과이진탐색비교 > 46

47 [2] 수행시간의관점에서성능분석 (p.116) 알고리즘빠르기판단기준 알고리즘속중요한연산의실행횟수 발생할수있는최악의연산횟수를사용 순차탐색비교연산횟수 이진탐색비교연산횟수 최상의경우 ( 한번에찾은경우 ) 1 1 최악의경우 ( 마지막에찾은경우 ) n log 2 n+1 <n 개의자료를탐색할때순차탐색과이진탐색의비교연산횟수 > 47

48 [2] 수행시간의관점에서성능분석 (p.116) 시간복잡도 (time complexity) 최악의연산횟수를계수가없는최고차항만으로표시한것 작을수록효율적인 ( 빠른 ) 알고리즘 예 ) n n 1 2 log 2 n + 1 n 2 log 2 n 48

49 [2] 수행시간의관점에서성능분석 (p.116) 시간복잡도크기비교 log 2 n n nlog 2 n n 2 이진탐색순차탐색퀵정렬버블, 선택정렬 49

50 함께해결하기 (p.117) 다음은우리모둠친구들의번호를조사한것이다. 물음에답하시오. 1. 친구들의번호를버블정렬과선택정렬을이용하여각각오름차순으로정렬한후, 비교횟수와교환횟수를알아보자. 구분 버블정렬 선택정렬 비교횟수 교환횟수 7 3 [19, 3] [19, 7] [19, 5] [8, 3] [8, 7] [8, 5] [7, 5] [3, 8] [5, 19] [7, 8] 첫번째자료가최솟값이면교환하지않는다고간주했을때 50

51 함께해결하기 (p.117) 다음은우리모둠친구들의번호를조사한것이다. 물음에답하시오 에서정렬된자료에서 19 를찾으려고한다. 순차탐색과이진탐색을활용하여각각탐색해보고, 비교횟수를적어보자. 구분순차탐색이진탐색 비교횟수

52 52

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

쉽게 배우는 알고리즘 강의노트 쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr 장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고,