History: 자주 하는 실수 모음
이 페이지에는 문제를 풀면서 자주 일어나는 실수들에 대해 정리합시다.
이 페이지는 이 스레드에서 파생되었습니다.
변수 범위 오버플로우
int의 표현 범위는 -2^31 ~ 2^31-1 사이이므로, 이 범위를 벗어나는 값을 계산하는 경우가 되면 예상과는 다른 이상한 값이 들어가게 됩니다. 이런 경우에는 64비트 정수 형태인 long long을 활용하거나 BigInteger를 구현해서 해결해야겠죠. BigInteger 클래스는 java만 쓰는 팀이 아닌 이상, 언제나 팀 노트에 들어가게 되는 약방의 감초와도 같은 라이브러리가 되겠습니다.
// 틀린 예
int a = 1000000 * 1024;
int b = 1<<50;
// 옳은 예
long long a = 1000000LL * 1024;
long long b = 1LL << 50;
소수 처리
부동소수점 소수표현은 언제나 제한된 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++) ... 과 같은 식으로요.
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발생 // 입력 데이터의 크기를 유추할 때 사용
중첩 루프에서 변수 순서(i, j, k) 바꿔 쓰기
(채워주세요)
배열 인덱스 오버플로우
(채워주세요)
테스트 케이스 여러 개 있을 때 전역변수 초기화 문제
(채워주세요)
binary search 의 최대/최소 범위 틀림
(채워주세요)
for(A; B; C)의 B에서 strlen 사용하기
(채워주세요)
STL에서 size()-1
(채워주세요)
그래프에서의 duplicate edge
(채워주세요)
대소문자 변환
(채워주세요)
인덱스와 값 사이의 혼동
(채워주세요)