[알고리즘] 순차탐색, 이진탐색

#1 최대값 찾기

25

15

35

60

45

80

55

75

알고리즘 1 : 값들을 하나씩 모두 비교해가면서 최대값 찾기

알고리즘 2 : 토너먼트 방식

어떤 것이 효율적? => 몇 번의 비교연산을 해야 하는가?

#2 "뒤섞인" 카드에서 원하는 카드 찾기

데이터 찾기 => 탐색

A

4

5

7

10

J

K

순차적으로 왼쪽부터 하나씩 비교하며 탐색한다 => 순차탐색(Sequential search)

10

5

A

J

7

K

.

∴ 6번 뒤집어서 K 발견

#3 "순서대로 나열"된 카드에서 10 찾기

A

4

5

7

10

J

K

---

7

.

.

.

임의로 정 중앙에 있는 카드를 하나 뒤집어 본다 => 이진탐색(Binary search)

순서대로 나열 되었으니까 뽑은 7번 카드 기준으로 오른쪽 카드만 확인한다

7

J

남은 오른쪽 카드 중 임의로 중간에 있는 카드를 뒤집는다

7

10

J

.

=> J 카드보다 10번 카드가 작으므로, 7번 카드와 J 카드 사이에 있는 카드가 10번이 된다

∴ 3번 뒤집어서 10번 카드 발견

※ 그렇다고 이진탐색이 순차탐색보다 효율성이 좋다고 말할 수 없다.

데이터가 뒤섞인 경우 순차탐색의 효율성이 좋고, 

순서가 나열된 데이터의 경우에서 이진탐색의 효율성이 좋다

∴ 데이터의 조건에 다라 효율적인 알고리즘이 다르다.

---

+ 알고리즘 설계 기법

주어진 문제 / 속성 / 조건 등 매우 다양한 알고리즘이 있지만! 일반적이고 범용적인 기법은 없다.

대표적인 설계기법은,

분할정복(divide-and-conquer)방법

동적프로그래밍(dynamic programming)방법

욕심쟁이(greedy)방법 

이 있다.