[BOJ 17357, 무난함] 자동차가 차주 김표준의 차를 들면? (C++)

solved.ac 마라톤 뛰다가 튀어나왔는데 부동소수점 오차때문에 피똥싼 문제다

나같은 사람이 또 있나 궁금해서 구글링해 봤는데 없길래 내가 글을 쓴다

https://www.acmicpc.net/problem/17357

 

이 문제를 풀려면 세가지를 알아야 한다.

1. 분산에 대한 지식 (제곱의 평균 - 평균의 제곱)으로 분산을 빠르게 구할 수 있다
2. 평균을 빠르게 구하기 위해 누적합을 사용하는 방법
3. 부동소수점 오차 줄이기

---

1. 표준편차(분산) 빠르게 구하기

표준편차의 제곱은 분산이고, 이 문제에서는 표준편차의 대소비교를 요구하는데

표준편차a <= 표준편차b 이면,
표준편차a의제곱 <= 표준편차b의제곱

그러니까 표준편차끼리 비교할 필요 없이 분산끼리 비교해도 충분하다.

분산의 = 제곱의 평균 - 평균의 제곱 이라는 공식을 활용하면 그나마 빠르게 계산이 가능하다.

---

2. 평균 빠르게 구하기 위해 누적합 활용하기

그런데 평균을 구할려니깐 시간복잡도가 마음에 걸린다.

알다시피 평균은 (원소들의 합)/원소들의 개수 로 구할 수 있는데, N개 원소들의 합을 구하기 위해 루프를 N번 돌면 비효율적이다(이 문제에서는 N이 1000이라서 상관없긴 하다)

그래서 누적합을 활용하고, a번 원소부터 b번 원소까지의 합을 구하기 위해 [b번까지의 누적합]-[a-1번까지의 누적합]으로 계산하면 O(N)의 시간이 걸리는 연산을 O(1)만에 할 수 있다.

---

3. 부동소수점 오차

CS(콤퓨타사이언스) 기본 지식이다. 컴퓨터에서 실수를 표현하는 방법에는 고정 소수점 방법과 부동 소수점 방법이 있는데, 부동 소수점 방식이 더 많은 범위의 수를 표현할 수 있기에 대부분 IEEE754 표준에 맞는 부동 소수점 방법을 채택한다.

IEEE754의 부동 소수점 방식은 어떤 수를 1.xxxxxx * 2^yyyyyyyyyyyyyy -127 이런식으로 근삿값을 구한 뒤
(부호)(xxxxxxx)(yyyyyyyyyyyyyy) 이렇게 메모리상에서 관리하는 방법임.

이런 근삿값을 구하는 방법은 채찍피티한테 물어보면 아주 잘 설명해준다.

0.765625를 부동 소수점 방식으로 나타내는 방법을 설명하겠습니다. 여기서는 IEEE 754 표준 32비트 단정도(float) 부동소수점 방식으로 나타내는 방법을 다루겠습니다.

1단계: 0.765625를 이진수로 변환

0.765625를 이진수로 변환하는 방법은 다음과 같습니다:

1. 0.765625 × 2 = 1.53125 → 정수 부분 1
2. 0.53125 × 2 = 1.0625 → 정수 부분 1
3. 0.0625 × 2 = 0.125 → 정수 부분 0
4. 0.125 × 2 = 0.25 → 정수 부분 0
5. 0.25 × 2 = 0.5 → 정수 부분 0
6. 0.5 × 2 = 1.0 → 정수 부분 1

따라서, 0.765625는 이진수로 0.110001입니다.

2단계: 0.765625의 이진수 표기 (Scientific Notation)

이제 이진수를 과학적 표기법으로 나타냅니다. 이진수 0.110001을 1.xxxx 형태로 나타내려면 소수점을 오른쪽으로 1번 이동해야 합니다. 따라서:

0.110001=1.10001×2−10.110001 = 1.10001 \times 2^{-1}

3단계: 부동소수점 표현

IEEE 754 32비트 부동소수점 형식은 다음과 같은 구성을 가집니다:

• 부호 비트 (1 비트)
• 지수 (8 비트)
• 가수 (mantissa) (23 비트)

부호 비트

0.765625는 양수이므로 부호 비트는 0입니다.

지수

지수는 2의 거듭제곱을 나타내는데, 이 경우 **2^{-1}**입니다. IEEE 754에서 지수는 bias 127을 사용하여 저장합니다. 따라서, 지수는:

지수=−1+127=126\text{지수} = -1 + 127 = 126

126을 이진수로 나타내면 01111110입니다.

가수 (Mantissa)

가수는 소수점 오른쪽에 있는 비트들을 나타냅니다. 이때 1.10001에서 1은 가수에 포함되지 않고, 나머지 10001000000000000000000만 저장됩니다.

4단계: 최종 부동소수점 표현

따라서, 0.765625를 IEEE 754 부동소수점 형식으로 표현하면:

• 부호 비트: 0
• 지수: 01111110
• 가수: 10001000000000000000000

전체적으로 0 01111110 10001000000000000000000가 됩니다.

최종 결과:

0.765625의 IEEE 754 32비트 단정도 부동소수점 표현은:

0 01111110 10001000000000000000000

이 값은 32비트로, 부호 비트 1비트 + 지수 8비트 + 가수 23비트로 구성됩니다.

이러한 부동 소수점 방식에는 꼭 알아야 할 문제점이 있는데. (사실 이것도 채찍피티한테 물어보면 잘 알려준다.)

부동 소수점 방식은 숫자를 근삿값으로 표현한다는 특성 때문에  필연적으로 오차가 발생하고, 코드에서 부동 소수점 연산을 많이 하면 할수록 이러한 오차가 누적되면서 틀렸습니다!! 를 받게 된다.

아래는 부동소수점 오차가 누적되는 예시 코드이다.

#include <bits/stdc++.h>
using namespace std;
int main(void) {
    float n01 = 0.1;
    float n03 = 0.3;
    float c01 = 0;
    float c03 = 0;
    for (int i = 0; i < 10000; i++)
    {
        c01+=n01;
        c03+=n03;
    }
    cout<<fixed<<setprecision(9)<<c01<<", "<<c03<<"\n";
    //출력 결과>> 999.902893066, 3000.292236328
	return 0;
}

그래서 부동소수점 오차를 어떻게 줄일 수 있을까??

실수를 이용한 연산을 최소화하고 최대한 정수를 이용해 계산하면 된다.

1. 소수의 분자와 분모를 정수만 이용해 따로 계산한 뒤 마지막에 분자/분모로 계산한다.
2. 계산 중간에 발생하는 소수에 적절한 값을 곱해 정수로 바꿀 수 있다면 그렇게 한 뒤 마지막에 딱 한번만 나눗셈을 한다.
3. float를 쓰고 있다면 float보다 오차가 적은 double을 사용한다

나는 2 방법을 활용해 정답의 오차를 줄일 수 있었다. 문제가 어려운 문제가 아니라서 1의 방법도 되긴 할거임.

---

코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;

ll arr[1001];
ll csum[1001];//arr의 누적합
ll ccsum[1001];//arr의 제곱의 누적합

int main(void){
    fastio;
    int N;cin>>N;
    for (int i = 1; i <= N; i++)
    {
        cin>>arr[i];
        csum[i]=csum[i-1]+arr[i];
        ccsum[i]=ccsum[i-1]+arr[i]*arr[i];
    }
    for (int k = 1; k <= N; k++)
    {
        ll ans = 1;
        ll mm = 0;
        for (int i = 1; i+k-1 <= N; i++)
        {
            ll av1,av2;
            av1=csum[i+k-1]-csum[i-1];//i번부터 i+k-1번 원소까지의 합
            av2=ccsum[i+k-1]-ccsum[i-1];//i번부터 i+k-1번 원소까지 제곱의 합
            ll tmp = av2*k-av1*av1; //분산끼리 비교하는 대신 k*분산끼리 비교(실수끼리 비교하는 대신 정수끼리 비교)
            if(tmp>mm){
                ans=i;mm=tmp;
            }
        }
        cout<<ans<<"\n";
    }
    
    return 0;
}