2D 배열의 피크 요소 찾기: 이진 탐색 알고리즘과 C++ 구현

피크(peak) 요소란 어떤 항목이 자신의 상하좌우 네 방향 이웃 요소 모두보다 크거나 같은 값을 가질 때를 말합니다. 이웃 요소는 위, 아래, 왼쪽, 오른쪽에 위치한 요소들을 의미하며, 대각선 방향의 요소는 이웃으로 간주하지 않습니다. 하나의 행렬에는 두 개 이상의 피크 요소가 존재할 수 있으며, 피크 요소가 반드시 행렬 전체에서 가장 큰 값일 필요는 없다는 점에 유의해야 합니다.

입력 및 출력

입력:
서로 다른 숫자로 구성된 행렬.
10  8  10  10
14 13  12  11
15  9  11  11
15  9  11  21
16 17  19  20

출력:
행렬의 피크 요소.
여기서 피크 요소는: 21

알고리즘

findMaxMid(rows, mid, max)

입력: 행렬의 행 개수, 중간 열 인덱스(mid), 출력용 인자로 전달되는 최댓값 변수

출력: 갱신된 최댓값과 해당 요소의 행 인덱스

Begin
    maxIndex := 0
    for each row index i in the matrix, do
        if max < matrix[i, mid], then
            max = matrix[i, mid]
            maxIndex := i
    done
    return maxIndex
End

findPeakElement(rows, columns, mid)

입력: 행렬의 행과 열 개수, 탐색 기준이 되는 중간 열 위치(mid)

출력: 행렬에서 찾아낸 피크 요소

Begin
    maxMid := 0
    maxMidIndex := findMaxMid(rows, mid, maxMid)

    if mid가 첫 번째 열 또는 마지막 열이면
        return maxMid

    if maxMid가 같은 행의 왼쪽·오른쪽 요소보다 크거나 같으면
        return maxMid

    if maxMid가 왼쪽 요소보다 작으면
        res := findPeakElement(rows, columns, mid - mid/2)
        return res

    if maxMid가 오른쪽 요소보다 작으면
        res := findPeakElement(rows, columns, mid + mid/2)
        return res
End

알고리즘의 작동 원리

이 알고리즘은 1차원 배열의 피크 찾기 문제를 2차원으로 확장한 것으로, 열을 기준으로 이진 탐색을 수행합니다. 먼저 중간 열에서 최댓값을 찾은 뒤, 그 값이 좌우 이웃보다 크거나 같으면 이미 피크 요소이므로 즉시 반환합니다. 만약 왼쪽 이웃이 더 크다면 탐색 범위를 왼쪽 절반으로, 오른쪽 이웃이 더 크다면 오른쪽 절반으로 줄여 재귀적으로 탐색을 반복합니다. 매 단계마다 탐색 대상 열이 절반씩 줄어들기 때문에 전체 시간 복잡도는 O(rows × log(columns))입니다. 또한 첫 번째 열과 마지막 열은 한쪽 방향의 이웃만 존재하므로, 해당 열의 최댓값이 곧 피크 요소가 됩니다.

C++ 예제 코드

#include <iostream>
#define M 4
#define N 4
using namespace std;

int arr[M][N] = {
    {10, 8, 10, 10},
    {14, 13, 12, 11},
    {15, 9, 11, 21},
    {16, 17, 19, 20}
};

int findMaxMid(int rows, int mid, int& max) {
    int maxIndex = 0;

    for (int i = 0; i < rows; i++) {   // 중간 열에서 최댓값 탐색
        if (max < arr[i][mid]) {
            max = arr[i][mid];
            maxIndex = i;
        }
    }
    return maxIndex;
}

int findPeakElement(int rows, int columns, int mid) {
    int maxMid = 0;
    int maxMidIndex = findMaxMid(rows, mid, maxMid);

    if (mid == 0 || mid == columns - 1)   // 첫 번째/마지막 열이면 maxMid가 곧 피크
        return maxMid;
    // maxMid 자체가 피크인 경우
    if (maxMid >= arr[maxMidIndex][mid - 1] && maxMid >= arr[maxMidIndex][mid + 1])
        return maxMid;

    if (maxMid < arr[maxMidIndex][mid - 1])   // 왼쪽 요소보다 작으면 왼쪽 절반 탐색
        return findPeakElement(rows, columns, mid - mid / 2);
    return findPeakElement(rows, columns, mid + mid / 2);   // 오른쪽 절반 탐색
}

int main() {
    int row = 4, col = 4;
    cout << "The peak element is: " << findPeakElement(row, col, col / 2);
}

실행 결과

The peak element is: 21