[특강자료]알고리즘-김현환PE.key

Transcription

1 VER 1.12 알고리즘 김현환 PE(98 회정보관리 )

2 ! 강의순서 (0.5hr) / (3hr+) (0.5hr)! 강의목적

3 Ⅰ. 1. 알고리즘의마인드맵 2. 출제경향분석 3

4 1. (1/6) 4

5 1. (2/6) 5

6 1. (3/6) 6

7 1. (4/6) 7

8 1. (5/6) 8

9 1. (6/6) 9

10 2. (1/6)! 기출통계 (5 회 ) * 총계 (1 교시형 /2 교시형 ) 구분 96회 98회 99회 101회 102회 관리 1(1/0) 1(0/1) 2(1/1) 1(0/1) 1(0/1) 응용 1(0/1) 1(0/1) - 1(0/1) - 합계 2(1/1) 2(0/2) 2(1/1) 2(0/2) 1(0/1)! 주요출제영역 자료구조 알고리즘기법 알고리즘설계 스택 버블정렬 문자열탐색 점근표기법 분할과정복 큐 삽입정렬 해시테이블 복잡도 탐욕알고리즘 링크리스트 힙정렬 최소신장트리 동적계획법 트리 퀵정렬 최단경로탐색 백트래킹 그래프 이진탐색 휴리스틱탐색 10

11 2. (2/6)! 96 회 [ 관 1] 그래프를이용하여최적경로를찾는데이용되는최소신장트리 (Minimal spanning Tree) 알고리즘에대하여설명하시오. [ 응 2] 데이터압축기법인런렝스 (Run Length) 코딩과허프만 (Huffman) 코딩에대하여설명하시오.! 98 회 [ 관 4] 인공지능응용정보시스템이나게임개발시길찾기에이용되는 ijkstra 알고리즘과 * 알고리즘을 비교설명하시오. [ 응 4] 해쉬테이블 (Hash Table) 의개념과장단점, 활용분야및충돌해결 (ollision Resolution) 의여러가지 기법에대하여설명하시오.! 99 회 [ 관 4] 퀵정렬 (Quick Sort) 알고리즘을설명하고, 다음데이터를퀵정렬알고리즘을사용해서정렬하는 과정을설명하시오. 30, 15, 16, 24, 38, 33, 17, 29, 32 11

12 2. (3/6)! 101 회 [ 관 2] _node (linked list)..! (, _tmain()) 12

13 2. (4/6) 1) 숫자 10, 5, 8, 3, 1, 7 을삽입하되작은수부터연결리스트가유지되도록함수 ordered_insert(int k) 를작성하시오. ( 단, k 는삽입하려는정수 ) 2) 연결리스트를구성하는각 node 의변수 data 를모두출력하는함수 print_list(node* t) 를작성하시오. ( 단, t 는 node 에대한시작포인터이고, 화면에출력할함수는 printf() 를사용 ) 3) 삭제하려는숫자를인수로받아그노드를삭제하는함수 delete_node(int k) 를작성하시오. ( 단, k 는삭제하려는정수 ) [ 응 3] 쓰레드이진트리 (Threaded inary Tree) 를정의하고쓰레드이진트리를표현하는일반적규칙과쓰레드이진트리를나타내기위한노드구조를제시하시오. 또한다음에제시된이진트리에대하여전위운행방식에의한쓰레드이진트리가메모리내에서어떻게표현되는지연결리스트를사용하여그림으로제시하시오. 13

14 2. (5/6)! 102 회 [ 관4] S_reateStack()... (push) ( void S_Push(S* Stack, ElementType ata). (pop) ( ElementType S_Pop(S* Stack) 14

15 2. (6/6) void S_Push(S* Stack, ElementType ata) { // 내용을채우세요 } ElementType S_Pop(S* Stack) { // 내용을채우세요 } int main(void) { int i = 0;!! } S* Stack = NULL; S_reateStack(&Stack, 10); S_Push(Stack, 3); S_Push(Stack, 37); S_Push(Stack, 11); S_Push(Stack, 12); 15

16 3.! 학습토픽리스트 " 링크드리스트 " 이진탐색 " 스택 " 문자열탐색 " 큐 " 최소신장트리 " 트리 " 최단경로탐색 " 그래프 " 휴리스틱탐색 " 버블정렬 " 알고리즘성능분석 " 삽입정렬 " 분할과정복 " 힙정렬 " 탐욕알고리즘 " 퀵정렬 " 동적계획법 " 해시테이블 " 백트래킹 16

17 Ⅱ. 1. 링크리스트 2. 스택 3. 큐 4. 트리 5. 그래프 17

18 3. (1/6)! 노드와링크드리스트 노드 링크드리스트 다음노드에대한포인터 데이터 노드 head tail 정의 : 배열처럼데이터집합을보관하는기능을가지면서배열과는달리유연하게크기를! 바꿀수있는자료구조 구성요소 : Node( 데이터, 포인터 ) 정의 : 데이터와포인터로이루어진노드를연결해서만든리스트 특징 : 리스트사이에노드삽입 / 제거용이, 순차검색에활용!! 구성요소 : Node, Head, Tail

19 3. (2/6)! 링크드리스트추가 노드추가

20 3. (3/6)! 링크드리스트삭제 삭제대상 이전노드로하여금삭제한노드가가리키던 노드를가르키게한다.

21 3. (4/6)! 링크드리스트삽입 5 새노드 앞노드의포인터가 새노드를가르키게하고 5 새노드의포인터가 뒤노드를가르키게한다

22 3. (5/6)! 더블링크드리스트 이전노드를가리키는포인터 다음노드를가리키는포인터 링크드리스트의탐색기능을개선한자료구조 양방향탐색이가능 head tail

23 3. (6/6)! 환형링크드리스트 tail 은자신의뒷노드로서 head 를가르킨다 head 는자신의앞노드로서 tail 을가르킨다. head 와 tail 이연결되어있는더블링크드리스트자료구조 tail 은 head 의 앞노드 head 는 tail 의 뒷노드 head tail

24 3. (6/6)! 링크드리스트의특징 - / / - - 4yte - -

25 1. (1/3)! 스택의정의 1. LIFO 구조 : 먼저삽입된데이터가 가장마지막에나오는 자료구조. 2. 구현방식 : 배열또는리스트형식. 3. 구성요소 : Stack Pointer, Top 4. 주요연산 : Push, Pop 먼저들어오면개고생!!

26 1. (2/3)! 스택구현방안 배열방식 링크리스트방식 구성요소 배열의최대용량 배열버퍼 최상위위치 링크리스트의 Header 링크리스트의 Tail #define MX 5! 구현 int Stack[MX]; int Top; Top 은배열의마지막위치를가리킨다 주소공간 typedef struct _taglinkedliststack Node* List; Node* Top; } LinkedListStack; Top 포인터는리스트의마지막을가리킴

27 1. (3/3)! 스택연산 삽입 (Push) 삭제 (Pop) 200 Pop 작업전 스택포인터 100 Push 스택포인터 200 (top) 100 (top) 작업후 스택포인터 200 (top) 100 스택포인터 (top) 100

28 2. (1/3)! 큐의정의 1. FIFO 구조 : 먼저삽입된데이터가 가장먼저나오는 자료구조. 2. 구현방식 : 순환큐, 링크드큐 3. 구성요소 : Front, Rear 4. 주요연산 : Enqueue, equeue 선착순!!!

29 2. (2/3)! 큐구현방안 순환큐 링크드큐 구성요소 순환큐의최대용량 인덱스 (Front, Rear) 순환큐버퍼 링크드큐의 Front 링크드큐의 Rear 노드의수 front rear front rear 구현 dequeue enqueue #define MX 5 int Front, Rear; int Queue[MX]; typedef struct _taglinkedqueue Node* Front; Node* Rear; } LinkedQueue; Rear 포인터는리스트의마지막을가리킴

30 2. (3/3)! 큐연산 삽입 (Enqueue) 삭제 (equeue) enqueue dequeue 작업전 front rear 1 front rear 작업후 front rear front rear

31 4. (1/11)! 트리의구성 범례 레벨 1 형제노드 EO 루트 가지 레벨 2 개발본부장영업본부장경영본부장 잎 레벨 3 선행기술팀오피스실영업팀경영기획팀 구성요소 노드 경로 - 부모노드 - 깊이 레벨 4 오피스팀 모바일팀 - 자식노드 - 형제노드 - 차수 - 높이 - 무게

32 4. (2/11)! 이진트리란? E F 1. 정의 : 모든노드가최대 2 개의 자식을가질수있는트리.! 2. 유형 포화이진트리 완전이진트리 경사이진트리 3. 순회 : 전위, 중위, 후위! 4. 활용 : 컴파일러, 자료검색

33 4. (3/11)! 이진트리의유형 포화이진트리완전이진트리경사이진트리 E F G E leaf 노드들이모두같은높이에존재노드총개수 : 2ᴷ - 1 leaf 노드들이트리의왼쪽부터차곡차곡채워진형태 한쪽방향으로노드들이채워진형태

34 4. (4/11)! 이진트리의순회방식 전위 (Preorder) 중위 (In order) 후위 (Postorder) E F G E F G E F G 방향 : 근 -> 좌 -> 우 표식 :! 방향 : 좌 -> 근 -> 우 표식 :! 방향 : 좌 -> 우 -> 근 표식 :

35 4. (5/11)! 이진트리의순회상세 (Preorder) E F E F E F E F E F E F

36 4. (6/11)! VL 트리란? alanced Factor E 1. 정의 : 좌우서브트리의높이차 1 이하인이진탐색트리.! 2. 주요특징 O(log N) 의검색성능보장 VL 형태로트리유지 3. alanced Factor : +1, 0, -1 경우만허용, 그외의경우 Rotation! 4. 회전방식 : LL, LR, RL, RR

37 4. (7/11)! VL 트리의불균형을초래하는 4 가지타입 LL 타입 LR 타입 RL 타입 RR 타입 왼쪽서브트리의왼쪽서브트리에노드삽입 왼쪽서브트리의오른쪽서브트리에노드삽입 오른쪽서브트리의왼쪽서브트리에노드삽입 오른쪽서브트리의오른쪽서브트리에노드삽입

38 4. (8/11)! VL 트리의 Rotation 방법 (LL 회전 ) Phase #1 Phase #2 Phase #3 Phase #4 7 Pivot 설정 7 오른쪽회전 7 2 삽입 왼쪽서브트리의왼쪽서브트리에노드삽입 7~ 2 까지의경로에서가운데노드 5 를 Pivot 노드로설정 Pivot 노드를루트노드방향으로오른쪽회전 Pivot 노드는최종적으로루트노드

39 4. (9/11)! VL 트리의 Rotation 방법 (LR 회전 ) Phase #1 Phase #2 Phase #3 Phase # 오른쪽회전 Pivot 설정 6 왼쪽회전 6 6 삽입 왼쪽서브트리의오른쪽서브트리에노드삽입 7 ~ 6 까지의경로에서마지막노드 6 을 Pivot 노드로설정 Pivot 노드를부모노드 5 방향으로왼쪽회전 Pivot 노드를부모노드 7 방향으로오른쪽회전

40 4. (10/11)! VL 트리의 Rotation 방법 (RL 회전 ) Phase #1 Phase #2 Phase #3 Phase # 왼쪽회전 9 9 오른쪽회전 삽입 8 Pivot 설정 오른쪽서브트리의왼쪽서브트리에노드삽입 7 ~ 8 까지의경로에서마지막노드 8 을 Pivot 노드로설정 Pivot 노드를부모노드 9 방향으로오른쪽회전 Pivot 노드를부모노드 7 방향으로왼쪽회전

41 4. (11/11)! VL 트리의 Rotation 방법 (RR 회전 ) Phase #1 Phase #2 Phase #3 Phase #4 7 7 Pivot 설정 7 왼쪽회전 삽입 오른쪽서브트리의오른쪽서브트리에노드삽입 7 ~ 9 까지의경로에서가운데노드를 Pivot 노드로설정 Pivot 노드를루트노드방향으로왼쪽회전 Pivot 노드는최종적으로루트노드

42 5. (1/8)! 그래프의정의 정점의집합간선의집합그래프 E E 정의 : 정점의집합을 V, 간선의집합을 E, 그래프를 G 라하면 G = (V, E)

43 5. (2/8)! 그래프의유형 무방향그래프방향그래프완전그래프 E E E - edge 에방향성이없이연결 - vertex 들의순서가정해지지않음 - 실선으로 edge 표현 - edge 에방향성이존재 - vertex 들의순서가정해짐 - 화살표로 edge 의방향표시 - 모든 vertex 쌍을연결하는 edge 존재 - edge 수 = (n*(n-1)) / 2 단, n = vertex 수

44 5. (3/8)! 그래프표현방법 ( 인접행렬 ) E E E 대칭 는,, E와인접 는,, 와인접 는, E와인접 는, 와인접 E는, 와인접 1열 : (, ), (, ), (, E) 2열 : (, ), (, ), (, ) 3열 : (, ), (, E) 4열 : (, ), (, ) 5열 : (E, ), (E, )

45 5. (4/8)! 그래프표현방법 ( 인접리스트 ),, E,,, E E, E, 규칙 각정점 인접정점들 각각의 vertex에대한인접한 vertex들을나열각 vertex를시작으로인접 vertex를 list로연결특징연결된 vertex들만리스트로관리하여기억장소낭비최소상대적으로 edge수가많을경우, 기억장소낭비증가 E E

46 5. (5/8)! 그래프탐색 깊이우선탐색 너비우선탐색 - 스택기반 - 백트래킹접근 - 미로찾기활용 - 큐기반 - 최단경로접근 - 라우팅알고리즘활용

47 5. (6/8)! 그래프탐색 (FS) E E E H H H F F F 규칙 특정 vertex 를시작점으로선택 선택된 vertex 에 방문 표시 선택된 vertex 에연결된여러 vertex 들을검사 검사한 vertex 들중에미방문 vertex 를새롭게선택, 원래 vertex 는 Stack 에삽입 검사한 vertex 들중에미방문한 vertex 가하나도없으면, 최종적으로삽입된 vertex 를꺼내서새롭게선택 E F H

48 5. (7/8)! 그래프탐색 (FS) E E E H H H F F F 규칙 특정 vertex 를시작점으로선택 선택된 vertex 에 방문 표시 선택된 vertex 에연결된여러 vertex 들을검사 검사한 vertex 들중에미방문 vertex 를새롭게선택, 원래 vertex 는 Queue 에삽입 검사한 vertex 들중에미방문한 vertex 가하나도없으면, Queue 의 Front 에서 vertex 를꺼내새롭게선택 E F H

49 5. (8/8)! 너비우선탐색상세 ( 후반부생략 ) E F H E F H E F H E F H E E F H E F G E F H F G 큐큐큐큐큐큐

50 Ⅲ. 1. 버블정렬 2. 삽입정렬 3. 힙정렬 4. 퀵정렬 5. 이진탐색 6. 문자열탐색 7. 해시테이블 8. 최소신장트리 9. 최단경로탐색 10. 휴리스틱탐색 50

51 1. (1/3)! 버블정렬의정의 여러개의자료중에서서로이웃하는키값을 두개씩비교하여순서를결정하는정렬방법 주요특징 간단한알고리즘느린속도 Flag를통해속도개선가능

52 1. (2/3)! 버블정렬의단계 For i = 0 To N - 1 인접한두개의키값을비교한다.! 앞의키값이뒤의키값보다크면교환! 더이상비교할대상이없을때까지처음부터반복 a[i] > a[i+1] true temp = a[i] a[i] = a[i+1] a[i+1] = temp false

53 1. (3/3)! 버블정렬의사례 Phase #1 Phase #2 Phase #3 Phase #4 여기서부터시작 여기서부터시작 여기서부터시작 여기서부터시작 비교및교환 비교 비교및교환 비교 비교 비교및교환 비교및교환 속도 최악 : n * (n - 1) / 2 최선 : (n - 1) 평균 : O(n²)

54 2. (1/3)! 삽입정렬의정의 첫번째키는정의된것으로보고두번째키부터 순서에맞는위치에삽입시켜정렬하는방법 주요특징 간단한알고리즘 레코드의이동이많음 비교적크기가작은 데이터집합정렬에유리

55 2. (2/3)! 삽입정렬의단계 For i = 2 To N 삽입대상위치를 2 번째부터마지막까지지정 비교대상을처음부터바로전까지지정 정렬대상영역의값들과뽑아낸요소와비교 삽입할값보다큰값을가진모든요소들을 한자리씩오른쪽으로이동 새로생긴빈자리에해당요소를삽입 전체데이터집합의정렬이완료될때까지반복 temp = a[i] For j = i - 1 To 1 step - 1 temp < a[j] true a[j+1] = a[j] a[j] = temp false

56 2. (3/3)! 삽입정렬의사례 Phase #1 Phase #2 Phase #3 속도 추출 추출 추출 [ 최악 ] - n * (n - 1) / 2 - 역순정렬시! [ 최선 ] 이동 이동 이동 (n - 1) 삽입 삽입 삽입 - 이미정렬된상태! [ 평균 ] - O(n²)

57 3. (1/4)! 힙정렬의정의 트리내의모든노드가부모노드보다커야한다는 규칙을만족하는완전이진트리 주요유형 min heap : 루트는항상작은값 max heap : 루트는항상큰값

58 3. (2/4)! 힙정렬의단계 정렬하고자하는데이터를 heap에넣는다. heap을정렬한다. heap의 Root를추출한다. heap을재정렬한다. 추출할데이터가없을때까지 1 ~ 4 반복한다.

59 3. (3/4)! 힙정렬의삽입 삽입 7 3 교환 Heap의최고깊이, 최우측에새노드를추가삽입한노드를부모노드와비교삽입한노드가부모노드보다크면연산종료삽입한노드가부모노드보다작으면다음단계진행부모노드와삽입한노드의위치를서로교환더이상교환할노드가없을때까지반복

60 3. (4/4)! 힙정렬의삭제 삭제 2 이동 교환 교환

61 4. (1/4)! 퀵정렬의정의 Pivot 을기준으로 작은값은왼쪽, 큰값은오른쪽에위치시키는 분할과정복에기반한알고리즘 주요특징 분할과정복기반재귀호출구조알고리즘이상대적으로복잡정렬위한별도스택필요

62 4. (2/4)! 퀵정렬의단계 quicksort(left, right) 정렬할원소들의집합에서 Pivot 값을설정 Pivot 보다큰값은오른쪽, 작은값은왼쪽 분할된집합의크기가 1 이될때까지반복 left < right true select pivot = a[left] loop until i < j loop until pivot < a[j] loop until pivot > a[i] temp = a[i] a[i] = a[j] a[j] = temp false j-- i++ a[left] = a[i] a[i] = pivot quicksort(left, i-1) quicksort(i+1, right)

63 4. (3/4)! 퀵정렬의성능!! 최악 : n * (n - 1) / 2 최선 : n * log₂ n 평균 : O(n * log₂ n)

64 4. (4/4)! 퀵정렬의사례 단계정렬과정세부내용 Phase #1 1 Pivot 2 진행 Pivot 으로 5 를선택 2 Pivot 보다크거나같은값탐색 3 Pivot 보다작은값탐색 Phase # 왼쪽과오른쪽으로진행하면서각각값이탐색된경우 탐색된위치의값을교환 Phase # 왼쪽과오른쪽의 index 가겹치거나역전이되면, Pivot 과역전된오른쪽 index 의값간교환 Phase # 분할 Pivot 과탐색 index 간교환으로위치확정 Pivot 을기준점으로왼쪽, 오른쪽집합분할 집합의크기가 1 이될때까지반복

65 5. (1/4)! 이진탐색의정의 정렬된데이터집합에서탐색범위를 1/2 씩 줄여나가면서수행하는방식 주요특징 분할과정복기반정렬된데이터집합에서사용고속탐색

66 5. (2/4)! 이진탐색의단계!!! 데이터집합의가운데있는기준값과찾는키값비교찾는키값 > 기준값 : 오른쪽부분검색찾는키값 < 기준값 : 왼쪽부분검색키값을찾을때까지이진검색을순환적반복

67 5. (3/4)! 이진탐색의사례 데이터집합 탐색범위 1 = n * (1/2)ˣ [8 을찾는경우 ] 기준값 1 8 < 12 -> 왼쪽검색 검색범위 1 = n * (1/2ˣ) 2ˣ = n 2 8 > 3 -> 오른쪽검색 기준값 log₂2ˣ = log₂n 3 8 = 8 -> 검색완료 검색범위 기준값 x = log₂n 탐색속도 O( log₂n )

68 5. (4/4)! 이진탐색과순차탐색의비교 구분장점단점 순차탐색 알고리즘단순, 이해용이 적은자료집합에서높은성능 자료의사전정렬불필요 많은자료집합에서잦은비교횟수 타알고리즘대비느린속도 이진탐색 알고리즘단순, 이해용이 많은자료집합에서도사용가능 적은비교횟수, 빠른속도 자료의사전정렬필요

69 6.! 문자열탐색의유형!!! 무식한탐색 카프라빈탐색 KMP 탐색 보이어무어탐색

70 6. (1/22)! 무식한탐색 처음부터끝까지 1:1 비교를수행하는방법

71 6. (2/22)! 무식한탐색방법 문자열집합 가나가라다사 비교 패턴 가 라 탐색완료

72 6. (3/22)! 카프라빈탐색 해시값을활용하여비교를수행하는방법

73 6. (4/22)! 카프라빈탐색방법 해시값 H₀ : ( 가 *2³ + 나 *2² + 가 *2¹ + 라 *2⁰) 문자열집합 가나가라다사아가바 패턴 가 라 다 사 해시값 : ( 가 *2³ + 라 *2² + 다 *2¹ + 사 *2⁰)

74 6. (5/22)! 카프라빈탐색방법 제외 해시값 H₁ : 2(H₀ - 가 *2³) + 다 *2⁰ 문자열집합 가나가라다사아가바 포함 패턴 가 라 다 사 해시값 : ( 가 *2³ + 라 *2² + 다 *2¹ + 사 *2⁰)

75 6. (6/22)! 카프라빈탐색방법 제외 해시값 H₂ : 2(H₁ - 나 *2³) + 사 *2⁰ 문자열집합 가나가라다사아가바 일치 포함 패턴 가 라 다 사 해시값 : ( 가 *2³ + 라 *2² + 다 *2¹ + 사 *2⁰)

76 6. (7/22)! 카프라빈탐색방법 해시값 H₁ : ( 나 *2³ + 가 *2² + 라 *2¹ + 다 *2⁰) 2( 나 *2² + 가 *2¹ + 라 *2⁰) + 다 *2⁰ 2( 가 *2³ + 나 *2² + 가 *2¹ + 라 *2⁰ - 가 *2³) + 다 *2⁰ 2(H₀ - 가 *2³) + 다 *2⁰ 해시값도출공식 Hᵢ = 2(Hᵢ ₁ - S[i-1] * 2ᵐ ¹) + S[i+m-1]*2⁰ S 는문자열, S[n] 은문자열내의 n 번째문자, m 은패턴의길이

77 6. (8/22)! 카프라빈탐색의문제점 문자열집합과패턴길이의크기에따라 해시크기가매우커질수있다. 컴퓨터레지스터의용량초과 오퍼플로우발생

78 6. (9/22)! 카프라빈탐색의해결방법 나머지연산을통해해시크기를제한 Hᵢ = (2(Hᵢ ₁ - S[i-1] * 2ᵐ ¹) + S[i-m+1]*2⁰) mod q 단, q 는충분히큰 Prime Number 로선정

79 6. (10/22)! KMP 탐색 검색위치를본문의왼쪽부터시작해서 오른쪽으로옮겨가며문자를직접비교하는방법 단, 비교가필요한부분만비교를수행

80 6. (11/22)! KMP 탐색 패턴과본문내의문자열을한차례비교한후, 다음단계의검색에서사용가능한 정보 가남음 이정보를활용하여불필요한비교패스

81 6. (12/22)! KMP 탐색 접두부 : 문자열의머리부분 접미부 : 문자열의꼬리부분 경계 : 접두부와접미부쌍

82 6. (13/22)! KMP 탐색방법 접두부 접미부 가나다가나 접두부 / 접미부파악 가가나 나가나 가나다 다가나 가나다가 나다가나

83 6. (14/22)! KMP 탐색방법 가나다가나 경계

84 6. (15/22)! KMP 탐색방법 문자열 일치접두부의길이 가나다가나마바가나 문자열 일치접두부의최대경계너비 가나다가나라 패턴 가 나 다 가 나 라 이동거리 : 일치접두부의길이 - 최대경계너비 경계 이동 가 나 다 가 나 라

85 6. (16/22)! 보이어무어탐색 문자열을오른쪽에서왼쪽으로비교하는방법 불일치발생시최대의효율로이동

86 6. (17/22)! 보이어무어탐색방법 나쁜문자이동 착한접미부이동 - 패턴에서불일치문자검색 - 본문의불일치문자위치와 - 일치하도록패턴이동 - 패턴에서접미부검색 - 본문의접미부와패턴의접두부가 - 일치하도록패턴이동

87 6. (18/22)! 보이어무어탐색방법 ( 나쁜문자이동 ) 1 불일치문자 2 패턴에서불일치문자검색 3 같은위치에오도록패턴이동

88 6. (19/22)! 보이어무어탐색방법 ( 나쁜문자이동 ) 1 불일치문자 2 패턴에서불일치문자검색 3-1 만큼이동? 어디선가누군가에무슨일이생기면, 차차차착한접미부이동이 ~~

89 6. (20/22)! 보이어무어탐색방법 ( 착한접미부이동 ) 불일치 착한접미부 착한접미부와 일치하는문자열 본문의착한접미부와일치하는 패턴의부분을해당위치까지이동

90 6. (21/22)! 보이어무어탐색방법 ( 착한접미부이동 ) 불일치 착한접미부 패턴에는착한접미부와 일치하는부분이없음

91 6. (22/22)! 보이어무어탐색방법 ( 착한접미부이동 ) 착한접미부의접미부 패턴의착한접미부와일치하는부분을 착한접미부의접미부에일치하도록이동

92 4. (1/10)! 해시테이블의정의 해시함수를이용하여키값을버킷의슬롯에 배열시켜빠르게탐색하는알고리즘 주요특징 고정길이 One way O(1) 의탐색속도충돌처리매커니즘필요

93 4. (2/10)! 해시테이블의구성 Key 집합 bucket 15 key #1 key #2 해시함수 %, ->, &, 주소값 key #3 key # slot

94 4. (3/10)! 해시함수 (ivision) 나눗셈법 인자는테이블크기에가장가까운 Prime Number 가효율이좋음 주소 = 입력값 % 인자 원본데이터 해싱 주소값 : 19 % 7 = 크기 :

95 4. (4/10)! 해시함수 (Folding) 자릿수접기 인자는테이블크기에가장가까운 Prime Number 가효율이좋음 주소 = 각자리수의합 % 인자 원본데이터 해싱 주소값 : ( ) % 7 = 크기 :

96 4. (5/10)! 해시함수 그런데, 해싱을하다보면동일한값이출몰할때가있다. 어떡하지? 충돌해결이필요!!

97 4. (6/10)! 해시테이블의충돌해결 폐쇄주소법 개방주소법 - 해시함수에의해 - 얻어진주소만을사용! 직접체이닝 간접체이닝 - 해시함수가아닌다른주소 - 사용하도록허용! 선형탐사 제곱탐사 이중해싱 재해싱

98 4. (7/10)! 해시테이블의충돌해결 (haining) 체이닝 : 각데이터를해당주소에있는링크드리스트에삽입하여문제를해결 충돌 충돌 충돌 해시테이블은링크드리스트에대한포인터를관리

99 4. (8/10)! 해시테이블의충돌해결 (Linear Probing) 선형탐사 : 충돌이발생하면현재주소에서고정폭으로다음주소이동 충돌 37 #1 11 # 충돌 23 충돌 #2 11 # 고정폭만큼이동 : 1 # # 고정폭만큼이동 : 1 고정폭만큼이동 : 1

100 4. (9/10)! 해시테이블의충돌해결 (Quadratic Probing) 제곱탐사 : 충돌이발생하면현재주소에서제곱수만큼다음주소이동 충돌 37 #1 11 # 충돌 23 충돌 #2 11 # 제곱수만큼이동 : 1² # # 제곱수만큼이동 : 1² 제곱수만큼이동 : 2²

101 4. (10/10)! 해시테이블의충돌해결 (ouble Hashing) 이중해싱 : 충돌이발생하면제 2 의해시함수결과를더해다음주소이동 충돌 37 #1 11 # 충돌 23 #2 11 # hash1() + hash2() 이동폭 # hash1() + hash2() 이동폭 테이블의끝을만나면처음으로돌아감

102 7. (1/6)! MST (Minimum Spanning Tree) Graph Spanning Tree MST E E E E - vertex 와 edge 간의연결구조 - G = (V, E)! - 그래프의모든 vertex 를포함, - 비순환방식으로연결되어있는서브그래프! - 가중치의총합이가장적은신장트리 - 비순환구조 - 그래프내의 edge 들만을포함 - vertex 의수가 n 일때 n-1 개의 edge 포함

103 7. (2/6)! MST 알고리즘유형 PRIM KRUSKL - 시작점기반최소가중치 - 정점마다 edge 검사 - 우선순위큐기반구현 - 가중치의오름차순정렬수행 - 최소가중치 edge 선택 - 분리집합기반구현

104 7. (3/6)! Prim 알고리즘 E (4) (5) E E H (1) (7) H H F (2) (3) F (6) F 규칙 임의의 vertex를선택, 신장트리의루트노드로삽입선택된 vertex와인접 vertex들사이의 edge 가중치검사최소가중치를가지는 edge를선택해당 edge로두정점을연결했을때, cycle이발생하면버리고, 그렇지않으면신장트리에삽입선택된 edge는 edge 리스트에서제거 edge 리스트에더이상의 edge가없을때까지 2~5 반복

105 7. (4/6)! Prim 알고리즘상세 E (4) H (1) (1) (1) (1) F (2) (2) (3) F (2) (3) F (4) (5) E (4) (5) (4) (5) (1) (7) H (1) (6) H (1) F (6) (3) F (3) F (2) (3) (2) (2)

106 7. (5/6)! Kruskal 알고리즘 E (5) (3) E E H (2) (7) H H F (4) (1) F (6) F 규칙 정렬된 edge 리스트 그래프내의모든 edge 을가중치의오름차순으로정렬 현재 edge 들중에서가중치가가장적은 edge 를선택 해당 edge 로두정점을연결했을때, cycle 이발생하면버리고, 그렇지않으면신장트리에삽입 선택된 edge 는 edge 리스트에서제거 edge 리스트에더이상의 edge 가없을때까지 2~3 반복 1 : {G,F} 2 : {,} 3 : {, } 4 : {,G} 5 : {,} 6 : {F,H} 7 : {,} 9 : {,E} 10 : {,} 11 : {,F}

107 7. (6/6)! Kruskal 알고리즘상세 F H F F E F H F F E F H

108 8. (1/5)! 최단경로탐색 모로가도서울만가면된다??? 가장빠른경로로가야된다

109 8. (2/5)! 최단경로탐색의정의 국도 50km 30km 40km 대구대전평택 50km 부산 서울 60km 대전 80km 고속도로 정의 : 그래프내의한 vertex 에서다른 vertex 로이동할때 가중치합이최소값이되는경로를탐색하는알고리즘

110 8. (3/5)! 최단경로탐색유형 ijkstra ellmanford - 사이클없는방향성에만적용 - 가중치합최소 - Link State 알고리즘활용 - 사이클없는방향성에만적용 - 가중치의음수값도고려 - istance Vector 알고리즘활용

111 8. (4/5)! ijkstra 알고리즘 E F 6 H E H 13 F E F H 규칙 각 vertex들은시작점으로부터자신에게이르는경로의길이를저장할곳을준비모든 vertex들은경로의길이를무한대로초기화시작 vertex의경로길이를 0으로초기화하고최단경로에추가연결된 vertex들의경로길이를갱신인접한 vertex가최단경로에이미존재하면, 이전경로길이와비교. 작으면수정, 크면무시그래프내의모든 vertex들이최단경로로만들어질때까지 4 ~5 반복

112 8. (5/5)! ellmanford 알고리즘 E F 6 H E H 9 F E F H 규칙 각 vertex들은시작점으로부터자신에게이르는경로의길이를저장할곳을준비모든 vertex들은경로의길이를무한대로초기화시작 vertex의경로길이를 0으로초기화하고최단경로에추가음의가중치를고려하면서연결된 vertex들의경로길이를갱신인접한 vertex가최단경로에이미존재하면, 이전경로길이와비교. 작으면수정, 크면무시그래프내의모든 vertex들이최단경로로만들어질때까지 4 ~5 반복

113 Ⅲ. 1. 점근표기법 2. 복잡도 3. 분할과정복 4. 탐욕알고리즘 5. 동적계획법 6. 백트래킹 113

114 1. (1/3)! 점근표기법 알고리즘의수행시간을대략적으로나타내는방법

115 5. (2/3)! 점근표기법의유형 O(n²) ɵ(n²) Ʊ (n²) 37n + 5 2n² + 4n 3n³ ig O : 어떤최악의상황에서도성능을보장. ig Omega : 아무리좋은케이스라도그성능이상을낼수없음 ig Theta : 알고리즘이처리해야하는수행시간의상한과하한을동시에표현

116 5. (3/3)! ig O 표기법으로표현한알고리즘의성능간그래프 행렬곱셈 버블, 삽입 퀵, 합병정렬 순차탐색 이진탐색 해시테이블

117 5. (1/1)! 복잡도 시간복잡도 : 문제를해결하는시간과입력의함수관계! 공간복잡도 : 문제를해결하기위해필요한저장공간과함수관계

118 5. (1/2)! 분할과정복의정의 문제를잘개쪼개서해결!! Top-own 접근 분할정복결합 2 개이상하위문제로나눔분할된하위문제를해결정복된답을취합

119 5. (2/2)! 분할과정복의사례 다 가라나 정렬할데이터집합을반으로분할 다 가라나 하위데이터집합의크기가 1 이될때까지 분할반복 다 가라나 두데이터집합을합한것만큼의버퍼마련 가 다나라 두데이터집합의첫번째요소들을비교, 작은요소를버퍼에추가 가 나다라 최종적으로정렬된하나의데이터집합생성

120 5. (1/2)! 동적계획법의정의 부분문제의답을기반으로전체문제답을해결 ottom-up 기반 분할해탐색최적해 문제를부분문제로분할 분할된부분문제를해결 결과를테이블에저장 부분문제해를이용 상위문제해결

121 5. (2/2)! 동적계획법의사례 (Floyd lgorithm) table l 단계 l₁ 시작 l₂ 최단거리 = 38 목표 최단경로 = l₁ 단계 3 단계 4 단계 5 단계 6 단계

122 5. (1/5)! 탐욕적방법의정의 해당순간에최적이라고생각되는것을선택해나가는방법 근시안적해법 해선택실행가능성검사해검사 부분문제의최적해를구하고 결과를부분해집합에추가 문제의제약조건 위반여부검사 새로운부분해집합이 문제의해가되는지확인 전체문제의해미완성

123 5. (2/5)! 탐욕적방법사례 ( 고정길이코드와접두어코드 ) SII a b c d SII ( ) 고정길이코드 : 모든코드의길이가똑같은값을갖는코드체계 접두어코드 : 코드집합의어느코드도다른코드의접두어가되지않는코드 사례 abcd 의고정길이코드변환 : abcd 의접두어코드변환 :

124 5. (3/5)! 탐욕적방법사례 ( 허프만코딩 ) 문자열 aaabaacdd 빈도수 해선택 a b c d b c 2 실행가능성 검사 접두어코드 a : 0 b : 100 c : 101 d : a d 0 1 b c 6 실행가능성 검사 5 해선택 0 b 4 2 d 1 c 3 해선택 실행가능성 검사

125 5. (4/5)! 탐욕적방법사례 ( 허프만코딩압축풀기 ) 9 압축데이터 a 0 b d 1 c 압축해제버퍼 직접변환해보세요!

126 5. (5/5)! 탐욕적방법과동적계획법비교,, ijkstra lgorithm, Huffman oding knapsack Problem, Floyd Shortest Path

127 5. (1/2)! 백트래킹의정의 여러후보해중에서특정조건을충족시키는 모든해를찾는알고리즘 후보해목록확인부분해계산최종해 현재위치한부분해에서 선택이가능한목록확인 목록의부분해들을 하나씩계산 해가요구하는조건을 만족하는지확인 요구조건불만족

128 5. (2/2)! 백트래킹의사례 ( 미로탈출 ) S S 백트래킹 S G G G 백트래킹 S 백트래킹 S 백트래킹 S 백트래킹 G G G

129 IV. 1. 사례 #1 2. 사례 #2 3. 사례 #3 4. 사례 #4 129

130 1. 1 (1/2)! 사례 #1 1 단락. 해당알고리즘의정의를명확하게작성 2 단락. 가. 알고리즘의수행절차 나. 알고리즘의수행사례 3 단락. 알고리즘의활용

131 1. 1 (2/2)! 사례 #2 1 단락. 해당알고리즘의정의를명확하게작성 2 단락. 가. 알고리즘의원리 나. 알고리즘의유형 3 단락. 알고리즘의활용

132 2. 2 (1/6)! 사례 #3-1

133 2. 2 (2/6)! 사례 #3-2

134 2. 2 (3/6)! 사례 #3-3

135 2. 2 (4/6)! 사례 #4-1

136 2. 2 (5/6)! 사례 #4-2

137 2. 2 (6/6)! 사례 #4-3