이 페이지에는 문제를 풀면서 자주 일어나는 실수들에 대해 언급합니다.

이 페이지는 이 스레드에서 파생되었습니다.

잘못된 알고리즘의 사용

슬프게도, 초심자일수록 자주, 알고리즘 자체가 잘못된 경우가 많습니다.
알고리즘을 전산학적으로 다루는 경우 크게 두 가지에 대해 배웁니다. 바로 알고리즘의 정당성(correctness) 증명과 시간/공간복잡도(efficiency) 분석이지요. 알고리즘이 잘못되었거나 답이 나오는 데 너무 오랜 시간이 걸리는 경우 오답이 됩니다.

위에서 설명했듯 크게 두 가지로 나뉩니다.

1. 틀린 알고리즘
   • 알고리즘이 왜 맞는지 논리적으로 설명할 자신이 있는지 잘 생각해 보세요. 그 자체로 좋은 공부가 됩니다.
   • 특히 특별한 경우, 최대값이나 최소값, 또는 경계 조건 같은 것들을 깊이 검토해 보세요.
   • 알고리즘이 맞는지 틀린지 자신이 없다면, 데이터를 좀 더 넣어보면 도움이 됩니다. 이 때, 다음 두 가지를 준비해서 비교해보는 것이 좋습니다. 작은 데이터에서 맞다면, 많은 경우 큰 데이터에서도 맞게 마련이지요.
     • 랜덤한 데이터를 만드는 프로그램
     • 느려서 작은 데이터만 풀 수 있지만, 확실히 틀리지 않을 알고리즘
2. 절대 시간 안에 답이 나오지 않는 알고리즘
   • 때로는 우주가 끝날 때까지 답이 나오지 않을 수도 있습니다. 채점자 입장에서는 알 수 없기 때문에, 일정 시간이 지나면 오답처리하고 종료하는 수밖에는 없습니다.
   • 얼마만큼의 시간이 걸릴지 어림잡아 보세요. 예를 들어, C/C++의 경우 조건문이나 덧셈 같은 연산이 1억번 정도 되면 1초 정도 걸린다고 어림할 수 있습니다. (다른 언어는 훨씬 복잡하지요)
   • 아슬하게 시간에 걸리는 경우는 보통 없습니다. 구현의 방법에 따라서 같은 알고리즘도 두세 배씩은 느릴 수 있습니다. 아예 방법이 잘못된 경우, 시간 제한이 1초인 문제에 대해 10초, 1시간, 1년, 혹은 그 이상이 걸리게 됩니다.

테스트 케이스 여러 개가 한번에 입력될 때, 적절히 초기화하지 않는 문제

테스트 케이스가 새로이 입력되는 것은 많은 경우 대부분의 변수에 대한 초기화가 다시 이루어져야한다는 것을 뜻합니다. 안타깝게도, 이 이유로 많은 분들이 오답을 받고 계십니다.

할 수 있는 것들:

• C++을 기준으로, 만약 문제를 해결하기 위해 사용하는 변수(객체)들의 생애 주기가 각 테스트케이스마다 끝나게끔 합니다. 이 경우 코드의 여러 부분에서 객체를 공유하려면 인자 등으로 전달해야 하기 때문에 복잡해지는 단점이 있습니다.
• 변수를 하나 새로 선언할 때마다 항상 초기화하는 습관을 들입니다. 종종, 원래 변수를 선언했을 당시의 생각으로는 굳이 초기화가 필요없었으나 구현을 하는 도중에 필요해지는 경우도 있습니다. 자신이 없다면 모든 내용을 항상 초기화하는 것이 현명합니다.
• 예제 입력을 넣을 경우에 같은 입력을 반복해서 한 차례 더 넣습니다. 예를 들어 예제가 3개의 테스트 케이스로 구성되어 있다면 대신 6개의 케이스를 넣고 ABCABC와 같이 반복되도록 하는 것입니다. 이러한 예제 입력들은 아래로 갈수록 어려운/복잡한/답이 커지는 것인 경향이 있습니다. 다시 작은 케이스를 입력하는것만으로도 많은 경우 잘못을 알아차릴 수 있습니다.

C 스타일 문자열에서 종결 문자를 고려하지 않고 배열 크기를 지정 (C/C++)

입력되는 문자열의 길이가 L이라고 하면 C string은 null-terminated인 것이 원칙이므로, 마지막에 '\0'(=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]; // 자주 헷갈린다면 이렇게 표시하는 것도 한 방법

개행 문자 처리: 테스트 데이터 마지막줄에 '\n'가 없는 경우

테스트 데이터 마지막에 개행 문자가 존재한다는 보장은 없습니다. 구현과 환경에 따라 이 부분이 문제를 일으키기도 합니다.
구체적으로 예를 들어 Node.js 사용 시 on('line')에 이벤트를 걸다보면, 맨 마지막 줄이 잘려나가는 경우가 생길 수 있습니다.

var input = [];
require('readline').createInterface(process.stdin, {})
.on('line', function(line) {
    input.push(line.trim());
}).on('close', function(a) {
    // '\n'가 없어 line이 호출되지 않았기 때문에,
    // input[input.length-1]에 마지막 줄이 들어있지 않음
}

그 경우, 아래와 같이 라인버퍼를 input 배열에 추가합니다.

var input = [];
require('readline').createInterface(process.stdin, {})
.on('line', function(line) {
    input.push(line.trim());
}).on('close', function(a) {
    if(this._line_buffer!='')
    {
        input.push(this._line_buffer);
        this._line_buffer = '';
    }
}

변수 범위 오버플로우

int의 표현 범위는 대부분의 환경에서 -2³¹ ~ 2³¹-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;

cin/cout과 integer overflow

위와 관련된 사례로, 입력을 받을 때 integer overflow가 나는 경우도 흔히 하는 실수입니다. signed 32-bit integer의 범위를 넘어가는 정수를 scanf("%d") 로 받거나 int x; cin >> x 처럼 받지 않도록 주의합니다.

• scanf와 64-bit integer (long long)을 사용하는 경우, "%I64d" 또는 "%lld" 의 포맷을 사용하면 됩니다 (이는 컴파일러/플랫폼마다 다를 수 있으니, 주의해야 합니다). 출력 시에도, 64-bit 정수를 printf("%d")로 출력하지 않도록 주의해주세요.
• C++의 경우, cin은 이 코드에서처럼 한번 잘못된 입력(overflow 등)이 발생한 이후에는 완전히 오동작할 수 있어 주의해야 합니다.

소수 처리

부동소수점 소수표현은 언제나 제한된 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++) ... 과 같은 식으로요.

더 알아보기

• What Every Computer Scientist Should Know About Floating-Point Arithmetic - kcm1700님의 추천
• x86 아키텍처에서 32비트, 64비트, 80비트의 차이에 관한 wookayin님의 리플

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발생 // 입력 데이터의 크기를 유추할 때 사용

bupjae님이 여러 언어로 입출력 성능을 실험한 자유게시판 글도 참고하세요.

실수 출력

실수값 출력을 요구하는 문제들의 경우, 대개 10^-7 이하의 상대/절대 오차는 허용하도록 되어 있습니다. 하지만 printf류의 함수에 충분한 자릿수를 명시하지 않을 경우 이들은 충분히 많은 자릿수를 출력하지 않기 때문에, 정답도 오답 처리될 수 있다는 점을 명심하세요.

예를 들어 답이 1/3 = 0.33333333333.. 인 경우, "%f"로 출력하면 0.333333이 출력됩니다. 오류가 10^-7 이상이므로 오답처리되지요.

따라서 printf("%.10f\n", ret); 와 같이 소숫점 밑으로 많은 수를 찍어주는 것이 좋습니다.

C90 기준으로 printf로 실수를 출력할 때는 float과 double 모두 "%f"를 사용합니다. 반면 scanf를 쓸 때는 float은 "%f" double은 "%lf"로 받습니다. C99부터는 %lf로 printf를 해도 괜찮습니다. C++에서는 C++11이 완전히 지원되어야 합니다. 아직은 %f를 쓰는 것이 안전합니다.

중첩 루프에서 변수 순서(i, j, k) 바꿔 쓰기

(채워주세요)

배열 인덱스 오버플로우

(채워주세요)

binary search 의 최대/최소 범위 틀림

(채워주세요)

for(A; B; C)의 B에서 strlen 사용하기

배열이나 문자열에 대해 처리를 할 경우 이에 대한 크기/길이를 알기위한 함수나 메소드를 사용하는 경우가 많습니다. 이 때, 해당 함수나 메소드가 시간복잡도가 O(1)$O(1)$가 아닌 경우가 발생합니다. 만약 이러한 함수를 이용하여 대상의 모든 원소를 순회할 경우, 예상했던 실행시간 이상의 시간이 소요되게 됩니다.

대표적인 예로, C언어의 strlen(const char*)함수가 있는데, 이 함수는 다음과 같이 구현이 되어있습니다.

size_t strlen( const char *s ) {
    size_t i;
    for( i = 0 ; s[i] != '\0' ; ++i );
    return i;
}

주의: 위의 구현은 strlen함수의 동작과정을 보이기 위한 임의적인 구현이며, 실제 string.h에서 제공되는 strlen함수의 구현과 다를 수 있습니다.

실제로 위의 함수는 문자열의 길이만큼 비교연산을 수행하여 동작하는 구조로 작성되어 있으며, 따라서 strlen함수의 시간복잡도는 O(N)$O(N)$입니다.

만약에 위의 함수를 이용해 문자열을 다음의 코드와 같이 모든 문자를 소문자로 바꿔 출력하는 코드를 작성하였다고 합시다.

#include <cstdio>
#include <cstring>
#include <cctype>

int main() {
    const int MAX_SIZE = (int)1e6; // 1e6 == 10^6
    char somewhat[MAX_SIZE];
    scanf("%s", somewhat);
    for( int i = 0 ; i < strlen(somewhat) ; ++i ) {
        somewhat[i] = tolower(somewhat[i]);
    }
    printf("%s\n", somewhat);
    return 0;
}

위의 코드는 scanf로 입력한 문자열의 길이가 적을 경우 정상적으로 동작하는데, 문자열의 길이가 10^4$10^4$ 정도만 되어도 생각보다 느린 실행속도를 보입니다.

아래는 실제로 위의 코드를 문자열 길이가 10^4$10^4$일 때 수행한 결과입니다.

./a.out < input.txt  0.86s user 0.00s system 94% cpu 0.918 total

위의 코드의 경우, 당초 우리가 기대한 수행시간은 O(N)$O(N)$에 비례할 것이고, 따라서 해당 입력에 대해 기대하는 실행 시간은 \frac{1}{1000}$\frac{1}{1000}$초 단위정도가 될 것입니다. 하지만 위와 같이 느린 수행 속도를 보이는 이유는, strlen함수가 매번 현재 처리할 문자열내의 문자의 위치가 끝에 도달하였는지 처리하는 부분에서 추가적으로 O(N)$O(N)$의 수행시간을 보이기 때문에, 실제 위의 코드는 O(N^2)$O(N^2)$의 시간복잡도에 비례하는 수행 시간을 보이게 됩니다.

하지만, 잘 생각해보면 위의 코드에서는 문자열의 길이는 변하지 않기 때문에, 다음과 같이 반복문을 처리하기 전에 임의의 변수에 문자열의 길이를 저장할 경우 시간복잡도 O(N)$O(N)$을 보장하게 구현을 할 수 있습니다.

#include <cstdio>
#include <cstring>
#include <cctype>

int main() {
    const int MAX_SIZE = (int)1e5; 
    char somewhat[MAX_SIZE];
    scanf("%s", somewhat);
    int len = strlen(somewhat);
    for( int i = 0 ; i < len ; ++i ) {
        somewhat[i] = tolower(somewhat[i]);
    }
    printf("%s\n", somewhat);
    return 0;
}

실제 실행한 결과는 다음과 같습니다.

./a.out < input.txt > output.txt  0.00s user 0.01s system 73% cpu 0.010 total

비단 strlen뿐만 아니라, 크기나 길이를 반환하는 함수의 구현체는 O(1)$O(1)$을 보장하지 않는 경우가 존재하기 때문에, 항상 이를 유의하여 구현을 하도록 습관을 들이는 것을 권장합니다.

참고할만한 링크

STL에서 size()-1

아래와 같은 코드는, 무한루프를 발생시킬 수 있습니다. (언제일까요?)

vector<int> a;
int s = 0;
for(int i = 0; i < a.size() - 1; ++ i) {
   // ...
}

바로 a가 비어있을 때, 즉 a.size() == 0 입니다. STL에서 모든 size(), count()와 같은 메소드의 리턴 타입은 signed int가 아닌 size_t, unsigned int입니다. 음수가 없는 타입이죠. unsigned 0에서 1을 빼면, integer underflow가 나서 '-1'이 아닌 '4294967295' 가 얻어집니다. 위 코드에서 i는 절대 42억..에 이를 수 없으므로 무한루프가 발생하거나 내부적으로 잘못된 index를 참조할 수 있겠죠.

따라서 size() - 1, count() - 1 과 같은 코드를 쓸 때에는 주의를 기울여 줘야 정신건강에 이롭습니다. 굳이 하겠다면..

for(int i = 0; i < (int)a.size() - 1; ++ i) { /* ... */ }

이렇게 명시적으로 타입 캐스팅을 해주면 됩니다. 타입캐스팅이 없으면 (i < a.size() 등) 컴파일러가 warning C4018: '<' : signed/unsigned mismatch 와 같은 경고를 해주는데, 이를 무시하지 맙시다 :)

그래프에서의 duplicate edge

(채워주세요)

대소문자 변환

(채워주세요)

인덱스와 값 사이의 혼동

(채워주세요)

리턴하지 않는 함수

(채워주세요)

C/C++ 에서 #define에 대한 잘못된 이해

(채워주세요)