C++에서 무작위 쌍이 최대 가중치 쌍일 확률 구하기

문제 개요

두 개의 서로 다른 배열이 주어졌을 때, 무작위로 선택한 하나의 쌍(pair)이 최대 가중치 쌍(maximum weighted pair)일 확률을 구하는 문제입니다.

여기서 '쌍'은 첫 번째 배열(arr1)의 원소 하나와 두 번째 배열(arr2)의 원소 하나로 구성됩니다. 즉, 프로그램은 첫 번째 원소가 arr1의 최댓값이고 두 번째 원소가 arr2의 최댓값인 경우, 그러니까 최대 가중치 쌍이 뽑힐 확률을 계산해야 합니다.

예제 1

입력

arr1[] = { 2, 23 }
arr2[] = { 10, 3, 8 }

출력

probability of maximum pair : 0.166667

설명

두 배열로 만들 수 있는 쌍의 집합은 {(2, 10), (2, 3), (2, 8), (23, 10), (23, 3), (23, 8)}로 총 6개입니다. 이 가운데 최대 가중치 쌍은 (23, 8) 하나뿐이므로 확률은 1 / 6 = 0.166667이 됩니다.

예제 2

입력

arr1[] = { 4, 5, 6 }
arr2[] = { 6, 2, 6 }

출력

probability of maximum pair : 0.222222

설명

이번에는 만들 수 있는 쌍이 총 9개이고, 최대 가중치 쌍인 (6, 6)이 두 번 등장합니다. 따라서 확률은 2 / 9 = 0.222222입니다.

접근 방법

• 두 배열의 원소를 입력받습니다.
• 각 배열에서 최댓값을 찾고, 해당 최댓값이 등장하는 횟수를 셉니다. 최대 가중치 쌍의 총 개수는 두 배열의 최댓값 등장 횟수를 곱한 값입니다.
• 최대 가중치 쌍의 개수를 전체 쌍의 개수(size_1 × size_2)로 나누어 확률을 계산합니다.
• 계산된 확률을 출력합니다.

알고리즘

Start
Step 1 → 최대 가중치 쌍의 확률을 계산하는 함수 선언
    double max_pair(int arr1[], int arr2[], int size_1, int size_2)
        int max_pair1 = INT_MIN, count_1 = 0 선언
        FOR i = 0 ~ size_1 - 1 반복
            IF arr1[i] > max_pair1
                max_pair1 = arr1[i], count_1 = 1
            ELSE IF arr1[i] == max_pair1
                count_1++
        int max_pair2 = INT_MIN, count_2 = 0 선언
        FOR i = 0 ~ size_2 - 1 반복
            IF arr2[i] > max_pair2
                max_pair2 = arr2[i], count_2 = 1
            ELSE IF arr2[i] == max_pair2
                count_2++
        return (double)(count_1 * count_2) / (size_1 * size_2)
Step 2 → main() 함수
    int arr1[] = { 2, 23 }, int arr2[] = { 10, 3, 8 } 선언
    size_1 = sizeof(arr1) / sizeof(arr1[0]), size_2 = sizeof(arr2) / sizeof(arr2[0]) 계산
    max_pair(arr1, arr2, size_1, size_2) 호출 후 결과 출력
Stop

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 확률을 반환하는 함수
double max_pair(int arr1[], int arr2[], int size_1, int size_2){
    // 배열 1의 최댓값과 그 등장 횟수
    int max_pair1 = INT_MIN, count_1 = 0;
    for (int i = 0; i < size_1; i++){
        if (arr1[i] > max_pair1){
            max_pair1 = arr1[i];
            count_1 = 1;
        }
        else if (arr1[i] == max_pair1){
            count_1++;
        }
    }
    // 배열 2의 최댓값과 그 등장 횟수
    int max_pair2 = INT_MIN, count_2 = 0;
    for (int i = 0; i < size_2; i++){
        if (arr2[i] > max_pair2){
            max_pair2 = arr2[i];
            count_2 = 1;
        }
        else if (arr2[i] == max_pair2){
            count_2++;
        }
    }
    return (double)(count_1 * count_2) / (size_1 * size_2);
}

int main(){
    int arr1[] = { 2, 23 };
    int arr2[] = { 10, 3, 8 };
    int size_1 = sizeof(arr1) / sizeof(arr1[0]);
    int size_2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << "probability of maximum pair in both the arrays are " << max_pair(arr1, arr2, size_1, size_2);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

probability of maximum pair in both the arrays are 0.166667

복잡도 분석

시간 복잡도: 두 배열을 각각 한 번씩 순회하므로 O(n + m)입니다(n, m은 각 배열의 크기).
공간 복잡도: 추가적인 자료구조 없이 상수 공간만 사용하므로 O(1)입니다.

핵심 정리

이 문제의 핵심은 모든 쌍을 일일이 나열하지 않고도 확률을 구할 수 있다는 점입니다. 첫 번째 배열에서 최댓값이 count_1번, 두 번째 배열에서 최댓값이 count_2번 등장한다면, 최대 가중치 쌍은 정확히 count_1 × count_2개 존재하고 전체 쌍의 개수는 size_1 × size_2개이므로, 확률은 (count_1 × count_2) / (size_1 × size_2)라는 간단한 식으로 계산됩니다.