FESTIVAL 문제에서[멘붕]

  • wayway
    wayway 
    #include <stdio.h>

float Result[100], Min=9999;
int Input[1100];
int T, N, L;        

void f() {
    int i, j, k, sum=0;
    float avg;
    Min=9999;

    for(i=L; i<=N; i++) { 
        for(j=0; j<=N-i; j++) {         

//문제가 되는부분.(오답)
            for(sum=0,k=0; k<i; k++) { sum += Input[k+j]; } 


//문제가 되는부분.(정답)
            for(sum=0,k=j; k<i+j; k++) { sum += Input[k]; }  

            avg = (float)sum/i;

            if(Min>avg) {
                Min=avg;
            }
        }
    }
    Result[T]=Min;
}

int main() {
    int t, i;

    scanf("%d", &t);
    for(T=0; T<t; T++) {
        scanf("%d %d%*c", &N, &L);

        for(i=0; i<N; i++) {
            scanf("%d%*c", &Input[i]);          
        }   

        f();

        printf("%.11f\n", Result[T]);
    }   
    return 0;
}

    문제를 해결하긴 했지만 이해안되는 부분이 있어서 질문올립니다 ㅠ

    알고리즘은 세개의 for문으로 구성되는데 첫번째 for문은 묶음단위로써 L, L+1, L+2, ... , N 으로 값이 변합니다. 두번째 for문은 각 묶음의 시작인덱스를 의미합니다(인덱스j부터 묶음단위i개를 읽어들이려는 방식). 세번째 for문은 j부터 i개를 읽기 위해 k를 i가 될때 까지 반복하는 역할입니다. 이때 질문은,

    for(sum=0,k=0; k<i; k++) { sum += Input[k+j]; }

    으로 하면 오답인데 이 부분을

    for(sum=0,k=j; k<i+j; k++) { sum += Input[k]; } 으로 하면 정답...

    다른건 다 그대로고 위의 문장만 바꿨을 뿐인데 정답/오답이 갈리게 되는데요,
    위 두 문장은 같은 의미 아닌가요?


    10년 전
6개의 댓글이 있습니다.
  • wayway
    wayway

    메리 크리스마스용


    10년 전 link
  • wookayin
    wookayin

    안녕하세요, 헬게이트에 오신것을 환영합니다(?) 위 두 개의 문장은 논리적으로는 같은 의미이지만, 실제 컴퓨터의 세계에서는 우리가 예상하지 못한 수많은 일들이 일어날 수 있습니다.

    근본적인 문제는 실수형 자료형(float / double)의 정밀도 문제에 있는데요, 아시다시피 이들은 소수를 정확하게 담을 수 없기 때문에 소수점 오차로 인해 여러가지 조건에 따라 다른 동작을 할 수가 있습니다. 영향을 줄 수 있는 요인으로는

    • 시스템 아키텍쳐 (x86? x64? intel? ARM?)
    • 최적화 옵션 (no opitimization, -O2, -O3 등 레벨)
    • 컴파일러 버전 (옛날 컴파일러라면 버그일수도?)
    • 기분탓

    등이 있습니다.

    무엇이 문제인가?

    일단 코드에서 잘못된 점은, 충분히 정밀하지 못한 float 을 사용했다는 것입니다. float 은 소수점 7자리를 정확하게 담기에는 너무 작은 자료형이라서, 프로그래밍 대회 등에서는 특별한 이유가 없다면 정밀한 double 을 쓰는 것이 좋습니다. double을 쓰면 (보통) 문제가 안 생깁니다. double 써도 일부러 정밀도 때문에 틀리게 하는 악의적인 문제를 낸게 아니라면

    그래도 같은 코드 같은데, 왜 문제가 되는가?

    논리적으로는 같은 코드이지만, C++ 컴파일러가 최적화를 할 때에는 실제로 생성되는 바이너리나 어셈블리 코드는 달라질 수 있습니다.

    일단 위와 같은 현상은, 32비트 머신에서 g++ -O3 컴파일 옵션을 사용한 경우 재현할 수 있었습니다 (AOJ 채점머신이 32비트 g++ 이고 -O3 을 사용합니다).

    g++ 4.6 기준으로 -O3 일때 활성화되는 최적화 옵션 중 하나에, 실수형 데이터(float double)를 레지스터에 저장하는 기능이 있습니다. 변수를 메모리에서 계속 store, load 하면 느리니까 store/load 하지 않고 register만 사용해서 연산하는 최적화 정도로 이해하시면 됩니다.

    그런데, x86 아키텍쳐에서는 내부적으로 실수형 변수를 담는 레지스터를 80-bit 짜리로 사용합니다. 일반적으로 double 이 64-bit 인데, 이 보다도 더 큰 width이지요. 따라서,

    1. 최적화 되지 않은 경우 : float 변수를 메모리에 store 할 때마다 float이 표현할 수 있는 가장 가까운 값으로 표현되어 저장됩니다. (메모리에는 정확히 4byte만 저장해야겠죠) 따라서 이 과정에서 정밀도의 손실이 있을 수 있습니다.

    2. 최적화 된 경우 : float 변수를 스택 메모리에 담지 않고, 그냥 레지스터로만 들고 다니는 최적화가 일어났습니다. Min에다가 avg을 저장할 때 정밀도의 손실이 일어났을 것으로 생각됩니다. (저장된 것을 다시 load 하면, 손실된 값이 얻어집니다)

    그러면 (정밀도 문제가 없다면) 논리적으로는 같은 두 코드가 왜 다른 동작을 보이는 것일까요? 사실 여기서부터는 컴파일러 마음입니다. 내부 코드가 사소하게만 바뀌어도 최적화 과정에서 변수-레지스터 할당 결과는 바뀔 수 있고, 생성되는 바이너리도 달라지기 때문에 다르게 동작할 수 있습니다. 자세한건 컴파일러가 내뱉는 어셈블리 코드를 까보면 알 수 있을텐데 (맞은 코드 쪽에 Min/avg 변수 관련해서 float store, load 인스트럭션이 없을 것 같습니다) 이건 복잡하니 생략..ㄷㄷ

    참고로 위 최적화는 항상 정밀도가 좋은 쪽으로만 동작하기 때문에, -O2 이하의 최적화를 사용하거나 다른 아키텍쳐에서는 충분히 틀릴 수 있는 코드입니다. 정답이 된 것은 아키텍쳐와 컴파일러 옵션에 따라 최적화가 잘 되어, 정밀도가 좋아져서 우연히 맞은 거라고 생각되네요. 제가 간단히 몇 군데 다른 환경에서 테스트해보니 아래와 같이 나오네요.

    • Intel x86, g++ 4.6, optimization -O2 : wrong
    • Intel x86, g++ 4.6, optimization -O3 : correct
    • Intel x86, g++ 4.6, optimization -O3, -ffloat-store : correct (플래그 -ffloat-store은 위의 최적화를 비활성시킵니다)
    • Intel x86-64, g++ 4.6, optimization -O2 : wrong
    • Intel x86-64, g++ 4.6, optimization -O3 : wrong

    좋은 경험(?) 한 셈 치고 앞으로는 float을 싫어해 주세요..ㅎㅎ


    10년 전 link
  • wookayin
    wookayin

    알고스팟 댓글 수정이 안되네요ㅠㅠ (심지어 raw markdown도 볼수없음)

    위 결과에서 Intel x86, g++ 4.6, optimization -O3, -ffloat-store : correct wrong 이 맞습니다. (최적화를 안했으니 틀려야 정상)


    10년 전 link
  • Being
    Being

    오 완벽한 설명이네요 멋집니다~


    10년 전 link
  • wayway
    wayway

    와.. 크리스마스의 기적... 감사합니다. 다섯시간동안 헤매던 문제였는데ㅠ 갈아엎고 딴 방법으로 해볼까하다가도 틀린게없어보여서 끝까지 매달렸는데ㅎㅎ.. 이렇게 자세히 답변해주시다니 정말 감사합니다. 일단 제가 가진게 미천하여 바로 이해는 안되지만 감은 오네요.

    제가 문제를 빨리 해결하는 편이 아니라 코드최적화나 정리하는 등의 과정은 제쳐두고 일단 논리의 완성을 중시하는 편인데, 앞으로는 이 사건을(!) 기억하며 단순논리구현 이전에 좀더 세부적인 부분에 대해서도 알아두고 구현가능성을 따져봐야하겠네요. 결국은 좀더 효율적이고 좋은 방법을 찾아서 구현해려고 했다면 이 문제를 못만났을지 모르지만, 어쨋든 큰 공부했다고 생각합니다.감사합니다.


    10년 전 link
  • wayway
    wayway

    ps. 말씀대로 코드부분의 float 를 double로 바꾸니 두 문장 모두 정답처리 되었습니다(처리시간은 매우 다르게 나왔지만). 또 float 타입일때 volatile 키워드를 처음으로 여기저기 사용해봣지만 아쉽게도 모두 오답. 이제 홀가분하게 다음 문제로 넘어가도록 하겠습니다. 감사합니다.


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.