배열은 가장 기본적인 선형 데이터 구조입니다. 배열에서 최대값과 최소값을 찾아야 할 때, 어떤 방법으로 효율적으로 찾을 수 있을까요? N개의 정수로 이루어진 배열에서 최대값과 최소값을 찾기 위해 몇 번의 비교가 필요할까요?

예를 들어 N=8인 배열 {5, 6, 8, 3, 7, 9, 1, 2}가 있다고 가정해 봅시다.

방법 1: 개별 탐색

최대값 찾기와 최소값 찾기를 별개의 문제로 간주하고 각각 해결합니다. 이 방법은 배열을 두 번 순회하므로 총 2N번의 연산이 필요합니다.

#include <iostream>

void findMaxMinIndividually(int arr[], int size) {
    if (size <= 0) return;

    int maxVal = arr[0];
    int minVal = arr[0];

    for (int i = 1; i < size; ++i) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
        if (arr[i] < minVal) {
            minVal = arr[i];
        }
    }

    std::cout << "Maximum: " << maxVal << std::endl;
    std::cout << "Minimum: " << minVal << std::endl;
}

int main() {
    int data[] = {10, 8, 9, 7, 4, 5};
    int length = sizeof(data) / sizeof(data[0]);
    findMaxMinIndividually(data, length);
    return 0;
}

방법 2: 쌍 비교 후 전체 비교 (원본 수정)

일반적으로 최대값과 최소값은 다른 값입니다 (N=1이거나 모든 요소가 같지 않은 한). 먼저 인접한 두 수를 한 쌍으로 묶습니다. 예를 들어, {5, 6, 8, 3, 7, 9, 1, 2}를 {(5,6), (8,3), (7,9), (1,2)}와 같이 묶습니다. 그런 다음 각 쌍 내에서 두 수를 비교하여 더 작은 수를 먼저, 더 큰 수를 나중에 오도록 조정합니다. 예를 들어, {(5,6), (3,8), (7,9), (1,2)}가 됩니다. 이 단계에서 N/2번의 비교가 수행됩니다. 이렇게 재구성된 배열에서 모든 첫 번째 요소(작은 수들)와 모든 두 번째 요소(큰 수들)를 분리합니다. 즉, {5, 3, 7, 1}과 {6, 8, 9, 2}로 나눕니다. 최대값은 두 번째 그룹에서, 최소값은 첫 번째 그룹에서 나올 가능성이 높습니다. 각 그룹을 개별적으로 순회하여 최대값과 최소값을 찾으면 됩니다. 전체적으로 약 1.5N번의 비교가 필요합니다.

주의: 이 방법은 N이 짝수일 때 잘 작동하지만, N이 홀수일 경우 올바른 결과를 얻지 못할 수 있습니다. 예를 들어 N=5이고 배열이 {3,4,3,4,5}라면, 첫 번째 요소 그룹은 {3,3,5}, 두 번째 요소 그룹은 {4,4}가 됩니다. 이 경우 최대값이 4로 잘못 계산될 수 있습니다. 방법 2와 3은 이러한 엣지 케이스를 명확히 다루지 않습니다. 실제 구현 시에는 이러한 상황을 고려해야 합니다.

방법 3: 쌍 비교 후 전체 비교 (원본 유지)

방법 2에서 원본 배열이 변경되는 단점을 보완합니다. 원본 배열을 유지하면서 순회합니다. 마찬가지로 인접한 두 수를 한 쌍으로 {(5,6), (8,3), (7,9), (1,2)}로 묶습니다. 현재까지 발견된 최대값과 최소값을 저장할 변수 max와 min을 사용합니다. 먼저 첫 번째 쌍의 두 수를 비교하여 더 큰 수를 max에, 더 작은 수를 min에 저장합니다. 다음 쌍 (8,3)을 처리할 때, 8이 3보다 크다는 것을 알게 되면, 8을 현재 max와 비교하고, 3을 현재 min과 비교하여 필요에 따라 업데이트합니다. 이 과정은 모든 쌍에 대해 반복됩니다. 총 비교 횟수는 여전히 약 1.5N번입니다. 각 쌍 내에서 한 번의 비교로 두 수의 대소 관계를 파악한 후, 각각 현재 최대값 및 최소값과 비교함으로써 0.5N번의 비교를 절약합니다.

#include <iostream>
#include <algorithm> // std::max, std::min 사용

void findMaxMinPaired(int arr[], int size) {
    if (size <= 0) return;

    int maxVal, minVal;
    int startIndex = 0;

    if (size % 2 == 0) {
        // N이 짝수이면 첫 두 요소를 초기 max/min으로 설정
        if (arr[0] > arr[1]) {
            maxVal = arr[0];
            minVal = arr[1];
        } else {
            maxVal = arr[1];
            minVal = arr[0];
        }
        startIndex = 2;
    } else {
        // N이 홀수이면 첫 요소를 초기 max/min으로 설정
        maxVal = arr[0];
        minVal = arr[0];
        startIndex = 1;
    }

    // 쌍별로 비교
    for (int i = startIndex; i < size - 1; i += 2) {
        int currentMax, currentMin;
        if (arr[i] > arr[i+1]) {
            currentMax = arr[i];
            currentMin = arr[i+1];
        } else {
            currentMax = arr[i+1];
            currentMin = arr[i];
        }
        
        // 전체 max/min 업데이트
        maxVal = std::max(maxVal, currentMax);
        minVal = std::min(minVal, currentMin);
    }

    std::cout << "Maximum: " << maxVal << std::endl;
    std::cout << "Minimum: " << minVal << std::endl;
}

int main() {
    int data[] = {10, 8, 9, 7, 4, 5};
    int length = sizeof(data) / sizeof(data[0]);
    findMaxMinPaired(data, length);
    return 0;
}

방법 4: 분할 정복

분할 정복(Divide and Conquer) 접근 방식을 사용합니다. N개의 숫자에 대한 최대값과 최소값을 찾기 위해, 배열을 앞뒤 N/2개로 분할하여 각각의 최대값과 최소값을 재귀적으로 찾습니다. 그런 다음 두 부분에서 얻은 최대값들 중 더 큰 값과 최소값들 중 더 작은 값을 최종 결과로 취합니다. 이 방법 역시 비교 횟수는 약 1.5N번입니다.