History: 자주 하는 실수 모음
이 페이지에는 문제를 풀면서 자주 일어나는 실수들에 대해 정리합시다.
이 페이지는 이 스레드에서 파생되었습니다.
변수 범위 오버플로우
int의 표현 범위는 대부분의 환경에서 -231 ~ 231-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발생 // 입력 데이터의 크기를 유추할 때 사용
실수 출력
실수값 출력을 요구하는 문제들의 경우, 대개 10-7 이하의 상대/절대 오차는 허용하도록 되어 있습니다. 하지만 printf류의 함수에 충분한 자릿수를 명시하지 않을 경우 이들은 충분히 많은 자릿수를 출력하지 않기 때문에, 정답도 오답 처리될 수 있다는 점을 명심하세요.
예를 들어 답이 1/3 = 0.33333333333.. 인 경우, "%f"로 출력하면 0.333333이 출력됩니다. 오류가 10-7 이상이므로 오답처리되지요.
따라서 printf("%.10lf\n", ret); 와 같이 소숫점 밑으로 많은 수를 찍어주는 것이 좋습니다.
char배열을 정확히 L만큼 잡는다 (C/C++)
입력되는 문자열의 길이가 L이라고 하면 C string은 null-terminated인 것이 원칙이므로, 마지막에 '\0' 바이트가 붙습니다. 따라서 문자열의 용도로 char[]를 선언하는 경우 그 길이가 최소 L+1만큼은 되어야 합니다. 그렇지 않으면 표준 라이브러리에서 제공하는 입력과 출력을 포함하여(e.g. scanf(), printf(), std::istream/cin, std::ostream/cout) 문자열 지원을 대부분 사용할 수 없습니다.
//문제 : 입력되는 문자열의 길이는 최대 50
char str[50]; // 잘못된 경우의 예
char str[51]; // 이렇게 하셔야합니다
char str[50+1]; // 자주 헷갈린다면 이렇게 표시하는 것도 한 방법
중첩 루프에서 변수 순서(i, j, k) 바꿔 쓰기
(채워주세요)
배열 인덱스 오버플로우
(채워주세요)
테스트 케이스 여러 개 있을 때 전역변수 초기화 문제
(채워주세요)
binary search 의 최대/최소 범위 틀림
(채워주세요)
for(A; B; C)의 B에서 strlen 사용하기
(채워주세요)
STL에서 size()-1
(채워주세요)
그래프에서의 duplicate edge
(채워주세요)
대소문자 변환
(채워주세요)
인덱스와 값 사이의 혼동
(채워주세요)