[Algorithm] 알고리즘 기초 (3)

+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다.

탐색 문제 1

정렬되지 않은 배열 E[1...n]에서, 어떤 값 k가 있는지 찾으시오.

만약 있다면 E[i]=k인 i를, 없으면 -1을 출력하라.

ans = -1

E = list(map(int, input().split()))
k = int(input())

for i in range(len(E)):
    if k == E[i]:
        ans = i
        break

print(ans + 1)

=> 모든 원소를 하나씩 k 값인지 탐색

 

비교를 한 번 할 때마다, 원소 한개가 답인지 아닌지를 알 수 있다.

따라서 총 n번의 비교가 필요하다.

- 비교를 하지 않으면 답인지 아닌지 알 수 없다.

- n번 비교를 하지 않으려면 공짜로는 되지 않는다.

(이진 탐색의 경우 입력된 값이 모두 정렬되어 있어야 한다.)

---

탐색 문제 2

정렬된 배열 E[1...n]에서, 어떤 값 k가 있는지 찾으시오.

만약 있다면 E[i]=k인 i를, 없으면 -1을 출력하라.

 

< 알고리즘 1 >

b개씩 배열의 요소들을 묶고 맨 앞 요소와 비교한다.

E[1], E[b+1], E[2b+1], ... 와 k를 비교한다.

E[ib+1] <= k < E[(i+1)b+1] 인 i를 찾는다.

E[ib+1], E[ib+2], ..., E[(i+1)]b 에서 k값을 찾는다.

 

시간 복잡도: 최악의 경우 n/b + b번 비교

 

b = n^(1/2)일 때, 최소값 2 × n^(1/2)  = O(n^(1/2))

 

< 알고리즘 2: 이진 탐색 > n = 2^k 이라고 가정, T(1) = 1 (k = logn)

T(n) = 1 + T(n/2)

=> 1: 가운데 원소 비교, T(n/2): 나머지(절반) 요소들 비교= 1 + (1 + T(n/4)) = 1 + 1 + (1 + T(n/8))= 1 + ... + 1 + T(n/2^k) = 1 × k + T(1) =   k + 1 = O(log n)

 

=> O(n^(1/2))보다 O(log n)이 더 작다.

---

함수의 증가

우리 알고리즘이 입력 n개가 주어졌을 때, 답을 구하는 데 걸리는 연산의 개수를 f(n)으로 정의하자.

- f(n)은 자연수에 대해 정의된 함수이다. (정의역이 자연수)

- f(n)은 증가 함수이다.

=> f(n)이 n이 증가함에 따라 얼마나 빨리 커지는지를 아는 것이 알고리즘의 성능을 평가하는데 중요하다.(느리게 증가하는 것이 바람직하다!)

 

f(n) = O(g(n))=> n0 <= n에 대하여 f(n) <= cg(n)=> f는 g보다 빠르게 증가하지 않는다.

 

f(n) = Ω(g(n))

=> n0 <= n에 대하여 f(n) >= cg(n)

=> g는 f보다 빠르게 증가하지 않는다.

 

f(n) = Θ(g(n))

=> f(n) = O(g(n)) 인 동시에 f(n) = Ω(g(n))

 

+ 위와 같이 정의되었음에도, f(n) = Θ(g(n)) 대신 f(n) = O(g(n))을 사용하기도 한다.

 

함수의 증가 그래프

---

점화식의 이해

고등학교 교과 과정에서 배운 수열의 귀납적 정의와 유사하다.

- 차이점: 바로 인접한 항간의 관계만을 다루는 것이 아니다.

- 어떤 함수를 자신보다 더 작은 변수에 대한 함수 자신과의 관계로 표현한 것이다.

(수열 = 정의역이 정수인 함수)

ex) 수열: an = an-1 + 2

=> 함수 a: a(n) = a(n-1) + 2 => 함수 f: f(n) = f(n-1) + 2

---

점화식을 푸는 법

1. 반복 대치

- 주어진 조건을 이용하여 점점 작은 함수로 반복하여 대치하는 방법

 

2. 추정 후 증명

- 점화식의 결론을 추정하고, 수학적 귀납법을 이용하여 증명하는 방법 (답을 먼저 찍기)

- 반복 대치가 복잡할 경우 유용하다.

- 추정이 쉽지 않을 수 있다.

 

3. 마스터 정리 (Master Theorem)

- 주어진 점화식에 대해서 공식을 통하여 푸는 방법이다.

---

반복 대치의 예 (1)

T(n) = T(n-1) + n, T(1) = 1 일 때, 시간 복잡도를 구하라.

 

풀이: T(n-1) = T(n-2) + n - 1, T(n-2) = T(n-3) + n - 2 ... 을 이용한다.

 

T(n) = T(n-1) + n

= (T(n-2) + n - 1) + n

= ((T(n-3) + n - 2)  + n-1) + n

...

= T(1) + 2 + 3 + ... + n

= n(n+1) / 2 = Θ(n^2)

---

반복 대치의 예 (2)

T(n) = 2T(n/2) + n, T(1) = 1 일 때, 시간 복잡도를 구하라.

 

풀이

1. T(n/2) = 2T(n/4) + n/2, T(n/4) = T(n/8) + n /4 ... 을 이용한다.

2. n = 2^k, k = log(n)이라고 가정한다.

 

T(n) = 2T(n/2) + n

= 2(2T(n/4) + n/2) + n = 4T(n/4) + n + n

= 2(2(2T(n/8) + n /4)  + n/2) + n = 8T(n/8) + n + n + n 

...

= 2^k × T(n/2^k) + kn

= n × T(1) + nlog(n)= Θ(n × log(n))