[openlecture] 심심해서 끄적거려보는, 코딩실수

  • Neon
    Neon

    알고리즘은 맞았다 싶은데 WA나 TLE가 뜨는 분들, 난감하시죠? 근데 막상 알고보면 어이없는 조그마한 실수로 문제를 놓치게 되는 경우도 왕왕 있는데, 곧 있을 ICPC Regional을 대비하여 몇가지 중요하다 싶은 체크리스트를 끄적거려보겠습니다.

    1. 범위 Overflow

    int의 표현 범위는 -2^31 ~ 2^31-1 사이이므로, 이 범위를 벗어나는 값을 계산하는 경우가 되면 예상과는 다른 이상한 값이 들어가게 됩니다. 이런 경우에는 64비트 정수 형태인 long long을 활용하거나 BigInteger를 구현해서 해결해야겠죠. BigInteger 클래스는 java만 쓰는 팀이 아닌 이상, 언제나 팀 노트에 들어가게 되는 약방의 감초와도 같은 라이브러리가 되겠습니다.

    int a = 1000000 * 1024; -> long long a = 1000000LL * 1024;
    int b = 1<<50; -> long long b = 1LL << 50;
    

    2. 소수 처리

    부동소수점 소수표현은 언제나 제한된 precision을 갖게 됩니다. float < double < long double 순서로 precision이 증가하게 되는데요, 문제는 이러한 부동소수점 값들이 정확한 값은 아니라는 데 있습니다. 변수에다 1827361621525123.128371263을 넣으면 실제 들어가는 값은 제한된 precision으로 표현할 수 있는 범위 내의 값만 저장되게 된다는 것이지요. 그렇기 때문에, 부동소수점 값들을 가지고는 == 등의 연산을 사용하는 것을 자제해야 합니다. 부득이하게 == 연산을 사용해야 할 경우 1e-12 등 작은 epsilon 값을 더하거나 뺀 값을 가지고 비교하는 방법을 활용하도록 합시다.

    예제>

    if(a==b) ... -> if(fabs(a-b) < 1e-9) ...
    

    while(e-s < 1e-6) ... - 이런 건 보통 결정 알고리즘에서 많이 활용하는 방식인데, 여러 모로 좋지 않으니(e나 s의 값이 각각 너무 큰 경우, 그리고 1e-6보다 더 작은 값을 epsilon으로 잡아야 하는 경우 등) 그냥 적당한 수를 매직 넘버로 넣어서 그 수만큼 iteration을 돌도록 하는게 좋습니다. for(int i=0;i<200;i++) ... 과 같은 식으로요.

    3. I/O 처리속도

    저는 사실 cin, cout, istringstream 등의 C++ I/O를 매우 많이 쓰는 편입니다. getline(cin,str) 등의 함수를 활용하면 입력의 크기에 관계없이 입력을 받을 수 있어서 많이 선호하는 편인데, 사실 이게 입력데이터가 큰 문제에서는 종종 TLE의 원인이 되기도 합니다. 3M 정도 되는 입력 데이터를 cin으로 처리하면 데이터 읽어들이는 데에만 1초 이상 소모하게 되는 경우도 종종 있습니다. 반면 fgets 등의 함수를 활용하면 엄청난 속도차이를 경험할 수 있지요. 다만 C 함수의 몇가지 제약조건은 주의하셔야 할 때도 있습니다.(fgets의 argument 등)

    예제>

    cin >> a; -> scanf("%d",&a);
    string str; getline(cin,str); -> char str[1024]; 
    if(fgets(str,1024,stdin) == 1024) 강제RE발생 // 입력 데이터의 크기를 유추할 때 사용
    

    제 오답 노트에 정리되어 있는 코딩 미스는 대략 저 세 가지 분류에 포함되는 게 대부분입니다. 추가할 거 있는분 환영...

    수정> 문서 포맷이 이상해서 format만 약간 수정했습니다.


    9년 전
11개의 댓글이 있습니다.
  • JongMan
    JongMan

    음 저도 몇가지 추가하자면
    1. 배열 인덱스 오버플로
    2. 테스트 케이스 여러 개 있는 문제 (안 그런 문제 없지만...) 에서 전역변수 초기화 문제
    3. binary search 의 상하 boundary 값 틀림
    정도가 떠오르는군요. 다른 것 뭐 없을까요?


    9년 전 link
  • hyunhwan
    hyunhwan

    제 경우는
    1. nested loop상에서 i, j, k를 혼동하여 사용하는 경우
    2. for(A;B;C) 라고 할 때 B의 부분에 strlen과 같은 함수를 사용해서 쓸데 없는 시간을 잡아먹는 경우
    3. STL에서 container의 size() 함수를 사용할 경우 for(int i=0;i<x.size()-1;++i) 를 했을때, x.size()가 0일 경우
    적어 놓고 보니까 for loop에 대해서만 적었네요.


    9년 전 link
  • MiNu
    MiNu

    전 Copy & Paste 하다가 실수를 하죠 ㅠ for ( int i=0 ; i<v1.size() ; ++i ) v1[i] = foo(v1[i]);똑같은거 카피한답시고 붙여넣다가.... for ( int i=0 ; i<v1.size() ; ++i ) v2[i] = bar(v2[i]);뭐 이런거라고나 할까요 ㅠ주어지는 예제케이스에서는 이런 걸 잡을수가 없는 경우가 종종 있더라구요 ㅋㅋㅋ


    9년 전 link
  • Yongrok
    Yongrok

    3번 제가 쓰고 싶었는데! ㅋㅋㅋ 역시 다들 하는 실수는 비슷한가 봐요 ㅋㅋ


    9년 전 link
  • 김우현
    김우현

    특이한 상황에서 duplicated edge
    Directed Graph를 Undirected Graph로 변환하여 해결하는 문제에서
    a->b와 b->a 와 같은 입력


    8년 전 link
  • Kureyo
    Kureyo

    STL의 컨테이너들에서 size()가 unsigned임을 잊고 size() - 1 해서 루프 돌릴때...


    8년 전 link
  • A.I
    A.I

    올해 예선 C번 문제에서 대소문자 구분이 없다는 것을 보고 if (A[i]-32 == B[i] || A[i]+32 == B[i] || A[i] == B[i]) 로 처리한 후배들의 코드를 보았습니다. 그런데 입력엔 숫자도 있었지요 :D


    8년 전 link
  • JongMan
    JongMan

    으핫 -_-;;;; 돋네요...
    tolower() toupper() 를 씁시다 ㅠ


    8년 전 link
  • 빛나는별
    빛나는별

    저는 배열크기때문에 문제 많이 틀리더라고요 ..
    배열을 좀 넉넉히 잡는게 좋을듯 싶네요 ㅠㅠ


    8년 전 link
  • 히노히에
    히노히에

    음...저는 path[] 배열에 "인덱스 값"을 집어넣고
    나중에 계산할 때 "값"으로 처리하는 실수를 가끔 하더라고요..
    저만그런가요? 뀨잉규잉


    7년 전 link
  • kcm1700
    kcm1700

    그래프 문제에서 multi edge, loop 등을 고려하지 않은 경우도 흔한 실수 중 하나겠군요.


    6년 전 link
  • 댓글을 남기시려면 로그인하세요.