알고리즘은 맞았다 싶은데 WA나 TLE가 뜨는 분들, 난감하시죠? 근데 막상 알고보면 어이없는 조그마한 실수로 문제를 놓치게 되는 경우도 왕왕 있는데, 곧 있을 ICPC Regional을 대비하여 몇가지 중요하다 싶은 체크리스트를 끄적거려보겠습니다.
1. 범위 Overflow
int의 표현 범위는 -2^31 ~ 2^31-1 사이이므로, 이 범위를 벗어나는 값을 계산하는 경우가 되면 예상과는 다른 이상한 값이 들어가게 됩니다. 이런 경우에는 64비트 정수 형태인 long long을 활용하거나 BigInteger를 구현해서 해결해야겠죠. BigInteger 클래스는 java만 쓰는 팀이 아닌 이상, 언제나 팀 노트에 들어가게 되는 약방의 감초와도 같은 라이브러리가 되겠습니다.
부동소수점 소수표현은 언제나 제한된 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);stringstr;getline(cin,str);->charstr[1024];if(fgets(str,1024,stdin)==1024)강제RE발생// 입력 데이터의 크기를 유추할 때 사용
제 오답 노트에 정리되어 있는 코딩 미스는 대략 저 세 가지 분류에 포함되는 게 대부분입니다. 추가할 거 있는분 환영...
제 경우는
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에 대해서만 적었네요.
전 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]);뭐 이런거라고나 할까요 ㅠ주어지는 예제케이스에서는 이런 걸 잡을수가 없는 경우가 종종 있더라구요 ㅋㅋㅋ
Neon
알고리즘은 맞았다 싶은데 WA나 TLE가 뜨는 분들, 난감하시죠? 근데 막상 알고보면 어이없는 조그마한 실수로 문제를 놓치게 되는 경우도 왕왕 있는데, 곧 있을 ICPC Regional을 대비하여 몇가지 중요하다 싶은 체크리스트를 끄적거려보겠습니다.
1. 범위 Overflow
int의 표현 범위는 -2^31 ~ 2^31-1 사이이므로, 이 범위를 벗어나는 값을 계산하는 경우가 되면 예상과는 다른 이상한 값이 들어가게 됩니다. 이런 경우에는 64비트 정수 형태인 long long을 활용하거나 BigInteger를 구현해서 해결해야겠죠. BigInteger 클래스는 java만 쓰는 팀이 아닌 이상, 언제나 팀 노트에 들어가게 되는 약방의 감초와도 같은 라이브러리가 되겠습니다.
2. 소수 처리
부동소수점 소수표현은 언제나 제한된 precision을 갖게 됩니다. float < double < long double 순서로 precision이 증가하게 되는데요, 문제는 이러한 부동소수점 값들이 정확한 값은 아니라는 데 있습니다. 변수에다 1827361621525123.128371263을 넣으면 실제 들어가는 값은 제한된 precision으로 표현할 수 있는 범위 내의 값만 저장되게 된다는 것이지요. 그렇기 때문에, 부동소수점 값들을 가지고는 == 등의 연산을 사용하는 것을 자제해야 합니다. 부득이하게 == 연산을 사용해야 할 경우 1e-12 등 작은 epsilon 값을 더하거나 뺀 값을 가지고 비교하는 방법을 활용하도록 합시다.
예제>
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 등)
예제>
제 오답 노트에 정리되어 있는 코딩 미스는 대략 저 세 가지 분류에 포함되는 게 대부분입니다. 추가할 거 있는분 환영...
수정> 문서 포맷이 이상해서 format만 약간 수정했습니다.
14년 전