탐색 문제의 최적성과 점화식

탐색 문제의 최적성

입력으로 주어진 수들 중 어떤 값을 찾는 탐색 문제는 항상 정렬만이 최적의 답은 아니다

 

문제 1.

정렬되지 않은 배열 A = {1,2,...,n} 중에서, 특정한 수 하나만 빼고, 무작위의 순서로 총 n-1개의 숫자가 한번에 하나씩 입력된다. 배열 A에서 빠진 하나의 수를 찾아라

 

이러한 문제를 봤을 때 가장 먼저 떠오르는 풀이법은 입력된 숫자들을 boolean배열에 저장하면서 숫자가 나왔을 때 그 배열을 true값으로 바꾸고, n-1개의 숫자가 모두 들어오면 배열을 처음부터 뒤져서 false인 값을 찾는다.

이런식으로 하면 boolean배열이 하나 필요하고,

for문을 이용해 배열을 돌면서 boolean을 찾기 때문에 최소 1번, 최대 n번의 비교가 필요한 방법이다. 이 방법의 시간 복잡도는 O(n)이다.

O(n)도 문제를 풀다보면 정말 나쁘지 않은 시간복잡도이다. 오히려 반가운 시간 복잡도일 수 있다.

하지만 단순히 하나의 값을 찾기위해 배열을 사용하는건 조금 아쉽다.

 

그렇다면 어떻게 할까?

방법은 수학시간에 배운 1~n까지의 합을 이용하는 것이다. 문제에서 입력할 수를 특정지어주었기 때문에

변수 x를 0으로 초기화한 후, 입력받을 때마다 x에 집어넣는다. 이후 n-1개를 모두 입력받았으면 

1~n까지의 합과 x를 빼면 배열에 없는 수를 바로 찾아낼 수 있다.

이 경우 입력만 받으면 끝나기 때문에 추가적인 검색 시간이 필요하지 않다.

 

문제 2.

정렬된 배열 E[1...n]에서, 어떤 값 k가 있는지 찾고, 만약 있다면 E[i]=k인 i를, 없으면 -1을 내보내시오.

 

해결방법 1. for문을 이용해 배열을 돌며 k가 있는지 찾고 인덱스 반환, 없으면 -1출력한다. -> O(n)의 시간 복잡도

해결방법 2. 특정한 상수 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번 비교 (k가 맨 끝에 있을경우)

이 방법이 최선일까?? 절대 그렇지 않다. 

이 배열은 정렬되어있기 때문에 이진 탐색을 이용하면,

해결방법 3. 이진 탐색의 경우, n=2^k로 가정하면

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

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

      = 1+1+(1+T(n/8)) = .... = 1+...+1+T(n/2^k) = k+1 = O(logn) 번 비교한다.

 

점화식의 이해

앞서 설명한 하노이탑과 같이 알고리즘 문제를 풀다보면 문제에 규칙이 있어서 이를 재귀적으로 풀 수 있는 문제가 많이 보인다. 이는 고등학교에서 배운 수열의 귀납적 정의 와 유사한데, 차이점은 점화식은 바로 인접한 항간의 관계뿐만 아니라 어떤 함수를 자신보다 더 작은 변수에 대한 함수 자신과의 관계로 표현한 것이다.

이렇게 문제를 분석하여 풀 수 있는 크기의 작은 문제들로 나눠 각 문제들 간의 관계를 이용한 해법이 바로 점화식이다.

예를 들어

f(n) = n*f(n-1)

f(n) = f(n-1) + f(n-2) 과 같이 f(n)이라는 큰 함수를 f(n-1),f(n-2)의 관계로 풀어 재귀적으로 호출시키면 f(1)부터 쭉 풀어쓸 수 있게된다.

 

이렇게 점화식을 푸는 방법을 반복 대치라 하는데 반복 대치라 함은 주어진 조건을 이용하여, 점점 작은 함수로 반복하여 대치하는 방법이다.

반복 대치의 예를 살펴보자

 

반복 대치의 예 1) T(n) = T(n-1) + n, T(1) = 1

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 

 

반복대치의 예 2) T(n) = 2T(n/2) + n, T(1) = 1

T(n/2) = 2T(n/4) + n/2, T(n/4) = 2T(n/8) + n/4 ... 이므로 n = 2^k인 이분탐색일 떄

= 2^k * T(n/2^k) + kn 으로, 시간 복잡도는 O(nlogn)이 되는 것이다.

이 복잡도가 실제로 맞는지 검증하기 위해서 우리는 추정후 증명이라는 검증방법을 적용해보자

추정후 증명이란? 점화식의 결론을 추정하고, 수학적 귀납법을 이용하여 증명해나가는 방법이다. 이 방법은 앞서 설명한 반복대치가 복잡할 경우 유용하게 쓰인다.

예시 2번을 사례로

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

추정: T(n) = O(nlogn), 따라서 T(n) <= cnlogn이라 추정한다.(c는 상수)

그렇다면 2T(n/2) + n <= cnlogn 임을 보이면 된다.

2T(n/2)+n <= 2c(n/2)log(n/2) + n (T(n) <= cnlogn 이므로)

= cnlog(n/2)+n  = cnlogn + n -cnlog2 <= cnlog n 이므로 

2T(n/2) + n <= cnlogn 은 성립한다.

 

추정후 증명 - 함정

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

T(n) = O(n)이라 추정해보자. 즉 T(n) <= cn이다.

2T(n/2) + n <= 2c(n/2) + n = (c+1) * n = O(n) 인데, 이는 cn + n <= cn 이라는 의미이므로 처음 가정에 어긋난다.

만약 T(n) <= (c+1)n이었다면 식은 성립한다.

 

그렇다면 T(n) = 2T(n/2) + 1 이라면??

추정후 증명 - 미묘

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

T(n) = O(n)이라 추정해보자. 즉 T(n) <= cn이다.

T(n) = 2T(n/2) + 1 <= 2c(n/2) + 1 = cn+1 이므로 이 또한 될 수 없다.

 

이렇게 탐색 문제를 최적화하는 방법과 수학적 귀납법을 통한 반복 대치의 증명을 살펴보았다.