[자료구조 기초 - 실수(Float)]백준 평균은 넘겠지(4344번) 풀이 (C++/Python)

수학에서 자연수는 무엇일까요?

1, 2, 3, 4처럼 현실에서 물건 개수를 셀 때 쓰이는 숫자입니다.

 

그러면 정수는 무엇일까요?

자연수 뿐만 아니라 0도 포함되고 부호가 -인 음수도 포함됩니다.

 

그러면 실수는 무엇일까요?

엄밀한 수학적 정의를 생략해서 간단하게 설명하면 정수에 소수를 더한 것입니다.

예를 들어 정수 14가 있다면 여기에 0보다 크고 1보다 작은 소수 0.25를 더해서 14.25입니다.

혹은 정수 14에 무한 소수 0.111111...를 추가해서 실수 14.111111...이 됩니다.

여기서는 정수에 유한 소수 더해진 실수만 다루겠습니다.

 

자, 그러면 코딩하는 과정에서 늘 만나는 float, double.

보통 인터넷 검색하면 어떻게 나올까요?

자료형	float	double
크기	4바이트(32비트)	8바이트(64비트)
유효 숫자	약 7자리	약 15~16자리
표현 범위	약 -3.4 * 10^38 ~ 3.4 * 10^38	약 -1.7 * 10^308 ~ 1.7 * 10^308
리터럴 접미사	3.14f 혹은 3.14F	접미사 없음(3.14 그대로)
부호 비트	1비트	1비트
지수부	8비트	11비트
가수	23비트	52비트

이렇게 교과서에 나온 내용 그대로 나올 것입니다.

하지만 여기서 이 내용을 본다고 해서 바로 이해가 될까요?

이것만 봐서는 바로 이해되기 어렵습니다.

 

그래서 제가 IEEE 754 규정을 참고해서 컴퓨터 공학에서의 실수 부분을 다른 방식으로 접근할려고 합니다.

참고 링크 : IEEE 754 - 위키백과, 우리 모두의 백과사전

처음부터 너무 깊게 들어가면 어려우니 하나씩 파보도록 하겠습니다.

 

처음에는 부호 비트 1비트, 가수부 2비트, 지수부 1비트로 시작합니다.

참고로 부호 비트는 항상 1비트이며 부호 비트가 0이면 양수, 부호 비트가 1이면 음수입니다.

여기서는 부호 비트 0인 경우에만 다루겠습니다.

지수부가 0인 경우 값은 다음과 같이 계산됩니다.

$$\text{value} = a_1 \times 2^{-1} + a_2 \times 2^{-2}$$

예시로 부호 비트, 가수부, 지수부 순서로 0 10 0이라면

1. 부호 비트가 0이므로 양수(+)

2. 지수부가 모두 0이므로 0.xxx 계산

3. 가수부가 10이므로 0.10(2)이며 이것을 10진수로 변환하면 1 * 0.5 + 0 * 0.25 = 0.5가 됩니다.

4. 최종 적으로 0 10 0은 0.5가 됩니다.

이렇게 부동소수점을 직접 계산할 수 있습니다.

만약 지수부가 모두 1이면 어떻게 될까요?

그러면 가수부가 0이냐 0이 아니냐에 따라서 무한대(Inf) 혹은 표현할 수 없는 숫자값(NaN)으로 나오게 됩니다.

 

그런데 만약 지수부가 1비트가 아니라면 어떻게 계산될까요?

부호 비트 1비트, 가수부 2비트, 지수부 2비트이고 부호 비트는 0으로 고정한다고 가정합니다.

아래 제가 일일히 계산한 표를 확인해주세요.

지수부의 비트가 모두 0이면 가수부만 신경 쓰면 되고, 모두 1이면 가수부가 0이냐 아니냐에 따라 Inf 혹은 NaN로 나왔죠?

그런데 지수부가 그 외의 경우이면 계산 방식이 좀 특이해집니다.

0.M이 아닌 1.M이 나오게 되며 Bias가 등장합니다.

전자공학과를 전공했다면 bias가 대략 회로 설계하는 과정에서 미리 걸어두는 전압 등이라는 것을 알 수 있으나

컴퓨터공학과에서는 bias가 부동소수점 계산하는 과정에서 좀 더 편리하게 계산하기 위한 변수입니다.

만약 지수부가 모두 0인 경우 혹은 모두 1인 경우가 아닌 경우이면 계산식은 다음과 같습니다.

$$ \begin{aligned} \text{Bias} &= 2^{E_{\text{total}} - 1} - 1 \\ \text{value} &= (1.M)_2 \times 2^{E - \text{Bias}} \end{aligned} $$

여기서 E_total은 지수부 총 비트수, E는 지수부를 10진수로 변환한 값입니다. M은 가수부를 2진수로 표현한 것입니다.

숨겨진 비트(hidden bit)를 넣어서 좀 더 다양한 실수를 표현할 수 있습니다.

 

2진수 -> 10진수로 표현하는 방법이 있다면 10진수 -> 2진수가 있겠죠?

그런데 이 과정은 정말 어려운 편에 속하므로 그냥 사진만 보고 흐름만 대략 파악하는 정도로 넘기겠습니다.

부호 비트 1비트, 가수부 10비트, 지수부 5비트이고 +0.3을 2진수로 변환하는 과정입니다.

좀 많이 어려워 보이죠?

그리고 2진수로 변환 후 다시 10진수로 복원할려고 하면 오차가 약 0.002 정도 차이가 납니다.

이것은 데이터 변환 과정에서 약간의 손실이 발생했기 때문입니다.

자매품으로 0.1과 0.2, 0.3을 각각 부호 비트 1비트, 가수부 23비트, 지수부 8비트인 2진수로 변환하면 다음과 같습니다.

이 때까지 쉽게 설명하기 위해 제가 일부러 부호 비트, 가수부, 지수부 순서로 했지만 실제 데이터는 부호 비트, 지수부, 가수부 순서로 표현합니다.

0.1 -> 0 01111011 10011001100110011001101

0.2 -> 0 01111100 10011001100110011001101

0.3 -> 0 01111101 00110011001100110011010

 

자, 이제 본격적으로 왜 어째서 0.1 + 0.2와 0.3이 컴퓨터에서는 다른 값으로 판단하는지 0.1 + 0.2를 직접 계산해보겠습니다.

이 과정도 매우 복잡하므로 사진으로 눈팅만 해주세요.

이론상으로 확인해본 결과 float에서는 우연히 0.1 + 0.2와 0.3이 일치하는 결과가 나왔습니다.

하지만 만약 float(부호 1, 지수 8, 가수 23)가 아닌 double(부호 1, 지수 11, 가수 52)이면 어떻게 될까요?

0.1 -> 0x3FB999999999999A

0.2 -> 0x3FC999999999999A

0.3 -> 0x3FD3333333333333

0.1 + 0.2 -> 0x3FD3333333333334

여기서 마지막 자리에 0.3은 3으로 나오나 0.1 + 0.2에서는 4로 나오게 됩니다.

여기서 오차가 정확하게 2^(-54)만큼 차이나게 되어 0.1 + 0.2 == 0.3이 성립하지 않게 됩니다.

제가 온라인 C++ 컴파일 사이트에서 직접 소스 코드를 작성해서 확인해본 결과 다음과 같이 나옵니다.

[float]

[double]

이렇게 해서 이론으로 분석한 것을 직접 두 눈으로 확인할 수 있습니다.

아 맞다. 주의사항이 있는데 해당 사이트는 64비트 컴파일러(SSE 등) 환경이므로 딱 32비트 정도만 계산하고 나머지 비트는 칼같이 자르며 여기서 우연히 모든 비트가 일치해서 "yes"로 출력됩니다.

하지만 만약 제가 32비트 컴파일러(FPU 등) 환경이면 다음과 같은 결과가 나옵니다.

맨 아래에 "no"라고 출력하게 됩니다.

그 이유는 FPU 컴파일러에서는 내부적으로 80비트 공간에서 작업하므로 나머지 48비트를 모두 0으로 채우고 연산합니다.

그 결과 0.1 + 0.2과 0.3의 값이 불일치하므로 "no"로 출력된 것입니다.

 

이렇게 해서 0.1 + 0.2와 0.3이 왜 서로 다른지 알 수 있습니다.

고성능을 추구할 때 두 실수끼리 연산해서 속도를 더 올릴 수 있으나 설계 단계에서 매우 어렵고 오차로 인해 정확한 연산이 어렵습니다.

이제 백준 문제를 해결하도록 하겠습니다.

 

 

문제 : 평균은 넘겠지(4344번)(Bronze I)

문제 링크 : https://www.acmicpc.net/problem/4344

출처 : Baekjoon Online Judge

 

우선 제가 수식을 만들어서 문제를 해결하도록 하겠습니다.

$$ \begin{aligned} \text{average} &= \sum_{i=1}^{N} \frac{L_i}{N} \\ \text{result} &= \sum_{L_i > \text{average}} \frac{100}{N} \end{aligned} $$

일일히 다 나누고 다 더해서 결과값이 일일히 다 더합니다.

이 공식은 수학적으로 문제가 없습니다.

아래는 위 공식을 C++ 소스 코드로 표현한 것입니다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int C;
    cin >> C;

    while (C--) {
        int N;
        cin >> N;

        vector<float> scores(N); 
        float average = 0.0f;

        for (int i = 0; i < N; ++i) {
            cin >> scores[i];
            average += scores[i] / N; 
        }

        float result_percentage = 0.0f;
        float percent_per_person = 100.0f / N; 

        for (int i = 0; i < N; ++i) {
            if (scores[i] > average) {
                result_percentage += percent_per_person; 
            }
        }
        
        cout << fixed << setprecision(3) << result_percentage << "%\n";
    }
 
    return 0;
}

수학적으로 문제가 없으니 제출할까요?

저런! 오답이네요.

분명히 수학적으로 맞는데 왜 이런 현상이 발생했을까요?

크게 3가지로 나옵니다.

1. L_i / N을 일일히 계산하고 하나씩 다 더한 것에서 나온 오차

2. score[i] > average에서 일부 테스트 케이스에서 예외 발생

3. 결과값을 구할 때 일일히 다 더해서 더 큰 오차를 불러일으킴

이로 인해 16% 채점 구간에서 바로 "틀렸습니다"가 됩니다.

 

이러면 어떻게 해야 할까요?

실수 연산을 "단 한 번만" 연산하면 오차를 최소화할 수 있습니다.

아래의 공식으로 수정합니다.

$$ \begin{aligned} \text{total} &= \sum_{i=1}^{N} L_i \\ \text{pass_count} &= \sum_{i=1}^{N} \begin{cases} 1 & \text{if } L_i \times N > \text{total} \\ 0 & \text{otherwise} \end{cases} \\ \text{result} &= \frac{\text{pass_count}}{N} \times 100 \end{aligned} $$

해당 공식을 C++로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int C;
    cin >> C;

    while (C--) {
        int N;
        cin >> N;
        
        vector<int> scores(N);
        int total = 0;

        for (int i = 0; i < N; ++i) {
            cin >> scores[i];
            total += scores[i];
        }

        int average_pass = 0;

        for (int i = 0; i < N; ++i) {
            if (scores[i] * N > total) {
                average_pass++;
            }
        }

        double result = (double)average_pass / N * 100.0;

        cout << fixed << setprecision(3) << result << "%\n";
    }
 
    return 0;
}

실수 연산을 딱 한 번만 했습니다.

오차를 최소화한 상태에서 제출해볼까요?

달콤한 "맞았습니다!!"를 받았습니다.

 

마지막으로 Python 소스 코드를 보여드리겠습니다.

import sys

input = sys.stdin.readline

C:int = int(input().rstrip())

for _ in range(C) :
    L:list = list(map(int, input().split()))
    N:int = L[0]
    
    total:int = 0
    for i in range(1, len(L), 1) :
        total += L[i]
        
    average_pass:int = 0
    
    for i in range(1, len(L), 1) :
        if N * L[i] > total :
            average_pass += 1
    
    result:float = 100 * average_pass / N
    print(f"{result:.3f}%")

 

[결론]

$$ \frac{L_1 + L_2 + \dots + L_N}{N} = \frac{L_1}{N} + \frac{L_2}{N} + \dots + \frac{L_N}{N} $$

수학적으로 볼 때 분배법칙으로 인해 두 식은 같습니다.

하지만 컴퓨터는 이 두 식을 다르게 연산해서 좌변에 있는 식을 사용하는 것이 중요합니다.

이렇게 오늘은 실수에 대해 깊이 공부하여 이것을 소스 코드로 구현하는 것까지 마무리했습니다.