알고리즘

5

8

10

15

탐색 범위가 절반씩 줄어든다.

탐색할 데이터는 순서 없이 저장되어 있다.

시간 복잡도는 $O(\log n)$이다.

1,000개의 데이터가 존재하는 경우, 최대 10회의 탐색으로 완료된다.

큰 문제를 작은 문제로 나눌 수 있어야 한다.

작은 문제들이 반복해서 사용되며, 이 작은 문제들의 결괏값을 저장해 두고 활용한다.

상향식(bottom-up) 접근 방식 또는 하향식(top-down) 접근 방식으로 구현할 수 있다.

메모하기(memoization) 방법을 활용하여 연산과 탐색이 증가하고 실행속도가 저하된다.

ㄱ, ㄴ, ㄷ

ㄱ, ㄴ, ㄹ

ㄱ, ㄷ, ㄹ

ㄴ, ㄷ, ㄹ

퀵 정렬

셸 정렬(shell sort)

기수 정렬(radix sort)

병합 정렬(merge sort)

B[] ＝ {10, 20, 30, 40}

B[] ＝ {10, 30, 20, 40}

B[] ＝ {40, 20, 10, 30}

B[] ＝ {40, 30, 20, 10}

퀵 정렬

선택 정렬

병합 정렬

삽입 정렬

널리 사용되는 것은 최악 시간 복잡도이다.

모든 알고리즘은 최악 시간 복잡도와 평균 시간 복잡도가 다르다.

최악의 경우 실행 시간은 모든 입력에 대한 실행 시간의 하한을 제공한다.

최선의 경우 실행 시간은 모든 입력에 대한 실행 시간의 상한을 제공한다.

부분 배낭(fractional knapsack) 문제

한 정점에서 다른 정점으로의 최단 경로 탐색 문제

이진 트리의 최대합 경로 찾기 문제

최소 신장 트리(MST, Minimum Spanning Tree) 생성 문제

체이닝(chaining)

선형 조사법(linear probing)

분기 한정법(branch and bound)

이차 조사법(quadratic probing)

$f(n)=\mathrm{\Omega }(n^2)$

$f(n)=O(n^2)$

$f(n)=\mathrm{\Theta }(n\log n)$

$f(n)+n^2=O(n^2)$

3

4

5

6

ㄱ, ㄷ

ㄱ, ㄹ

ㄴ, ㄷ

ㄴ, ㄹ

count: 4, count: 8

count: 4, count: 9

count: 5, count: 9

count: 5, count: 10

(b, f)

(c, d)

(d, e)

(d, g)

스택(stack)을 이용하여 구현할 수 있다.

재귀적(recursive)으로 구현할 수 있다.

제약 충족(constraint satisfaction) 문제에 유용하다.

균형 탐색 트리(balanced search tree) 구조를 유지한다.

라빈－카프(Rabin-Karp)

벨만－포드(Bellman-Ford)

보이어－무어(Boyer-Moore)

KMP(Knuth-Morris-Pratt)

A → B → D → E → C → F → G → H

A → C → F → H → G → E → D → B

A → C → G → H → F → D → E → B

A → D → B → E → C → G → H → F