Deep Into Algorithm from MIT의 첫 강의 극댓값 찾기 (Peak finding) 입니다.

문제

우리가 풀어야 할 정확한 문제는 Find a peak if it exists 입니다. 즉 배열에서 극댓값이 존재한다면 그 값을 찾으면 됩니다.
a peak : 이므로 극댓값이 여러 개여도 하나만 찾으면 됩니다.
if it exists : 극댓값의 정의에 따라 배열에 극댓값이 존재할 수도 있고, 없을 수도 있어서 이 조건이 붙은 것입니다.

이제 1차원 배열 과 2차원 배열 에서의 극댓값을 각각 정의하고 찾아보겠습니다.

1차원 배열에서 극댓값 찾기

극댓값

1차원 배열에서는 극댓값을 다음과 같이 정의합니다.

즉, 중간 값이 양 옆의 값보다 크거나 같다면 그 중간 값이 극댓값이 됩니다. 배열의 가장자리의 경우는 존재하는 한 쪽 값만 확인하면 됩니다. 이 정의에서는 등호가 있기 때문에 극댓값이 항상 존재합니다. 극댓값을 정의했으니 극댓값을 찾는 알고리즘을 보겠습니다. 이 포스트에서는 2 가지의 알고리즘을 소개할 것입니다. 또한 배열의 길이를 n 이라고 설정하겠습니다.

1. Straight forward 알고리즘

극댓값을 찾는 가장 간단한 알고리즘입니다. 배열의 처음 원소부터 극댓값인 지 검사하고 극댓값이 아니면 다음 원소를 검사하는 알고리즘입니다.

분석

이 알고리즘으로 프로그램을 만들면, 극댓값이 배열의 i 번째에 있다면 i개의 원소를 검사하고 프로그램이 멈출 것입니다. 따라서 최악의 시간 복잡도 는 극댓값이 n 번째에 있을 때 이므로 T(n) = O(n) 이 되고, 선형 시간 알고리즘입니다.

시간 복잡도 : $T(n) = O(n)$

좀 더 효율적인 방법이 있을까요? 네 있습니다. Straight forward보다 효율적인 분할 정복 알고리즘에 대해 알아보겠습니다.

2. 분할 정복 알고리즘

다음 4가지의 단계를 반복하는 알고리즘 입니다. 이 알고리즘은 각 단계에서 봐야하는 배열의 길이가 $\frac{1}{2}$배로 줄어드는 특징이 있습니다.

1. 중간 원소를 선택
2. 왼쪽 원소 ,오른쪽 원소와 중간 원소 비교
3. 왼쪽 원소, 오른쪽 원소보다 중간 원소가 크면 중간 원소가 극댓값 (stop)
4. 그렇지 않다면 더 큰 쪽의 부분으로 1부터 다시 반복

마지막 4 부분이 헷갈릴 수 있습니다. 고로 예시를 보겠습니다.

예시

분석

시간 복잡도를 먼저 말하자면 T(n) = T(n/2) + O(1) 입니다.
O(1)은 극댓값을 확인하는 부분입니다. 실제로 중간 원소를 찾는 것, 양 옆과 비교를 하면 3번의 연산을 하는데 이것은 O(1)과 같습니다.
만약 중간 원소가 극댓값이 아니라면 n/2 길이의 배열을 다시 검사해야 합니다. 이 부분이 T(n/2)가 되는 것입니다. 그래서 T(n) = T(n/2) + O(1) 이 된 것입니다. 이 T(n)을 빅오 노테이션만 이용해서 표현해보겠습니다.

$T(1) = O(1)$

$T(2) = O(1) + O(1)$

…

$T(n) = O(1) + O(1) + … + O(1) = O(log_2 \; n)$       ( $O(1)$이 $log_2 \;n$개 )

따라서 $T(n) = O(log \; n)$ 인 로그 시간 알고리즘입니다. 이는 선형 시간 알고리즘보다 효율적입니다.

시간 복잡도 : $T(n) = T(\frac{n}{2})+O(1) = O(log \; n)$

2차원 배열에서 극댓값 찾기

극댓값 정의

2차원 배열에서는 극댓값을 다음과 같이 정의합니다.

즉, 중간 값이 양 옆, 위 아래의 값보다 크거나 같다면 그 중간 값이 극댓값이 됩니다. 배열의 가장자리의 경우는 존재하는 주변 원소만 확인하면 됩니다. 이 정의에서는 등호가 있기 때문에 극댓값이 항상 존재합니다. 극댓값을 정의했으니 극댓값을 찾는 알고리즘을 보겠습니다. 1차원 배열과 마찬가지로 2 가지의 알고리즘을 소개할 것입니다. 또한 배열이 n개의 행, m개의 열 을 가진다고 설정하겠습니다.

1. Greedy Ascent 알고리즘

가장 간단한 방법입니다. 시작 원소를 정하고 극댓값이 아니라면 주변 원소 중 가장 큰 원소를 선택하고 그 원소가 극댓값인 지 검사하는 과정을 반복하는 알고리즘입니다.

분석

이 알고리즘의 경우 시간 복잡도는 $O(nm)$ 이 됩니다. $n=m$이라면 $O(n^2)$ 이 됩니다. 분할 정복을 이용한 좀 더 효율적인 알고리즘을 보겠습니다.

2. 분할 정복 알고리즘 (1차원을 확장)

다음 5 가지 과정을 반복하는 알고리즘입니다. 이 알고리즘은 각 단계에서 봐야하는 배열의 col이 $\frac{1}{2}$배로 줄어드는 특징이 있습니다.

1. 중간 col을 본다.
2. col의 최댓값 위치 (i,j) 찾는다.          => 위 아래 값 check
3. (i,j)를 (i,j-1)와 (i,j+1)과 비교한다.      => 양 옆 col check
4. (i,j)가 양 옆보다 크거나 같으면 (i,j)는 극댓값 (stop)
5. 그렇지 않다면 더 큰 col 부분으로 1부터 다시 반복

분석

이 알고리즘의 시간 복잡도는 T(n,m) = T(n,m/2) + O(n) 입니다.
O(n)은 최댓값을 찾는 부분입니다. 빅오 노테이션으로 $T(n,m)$을 표현해보겠습니다.

$T(n,1) = O(n)$

…

$T(n,m) = O(n) + O(n) + … + O(n) = O(n * log \; m)$       ( $O(n)$이 $log \; m$개 )