맞왜틀 피하기 (자주 하는 실수 모음)

 여기서 맞왜틀이란, "맞았는 데 왜 틀렸지?"에 줄임말입니다.

이 글은 알고리즘 문제 풀이(Problem Solving)를 하면서 종종 마주하는 "맞왜틀?"을 피하는 방법들을, 제가 아는 지식과 겪어본 경험을 토대로 정리해볼까 합니다.

코드의 구현과 관련한 깊은 내용들은 C/C++을 기준으로 이야기합니다.

문제를 푸는 환경

이제는 많은 문제 풀이 플랫폼과 온라인 저지 사이트들이 있습니다. 역사 깊은 UVa Online Judge부터 Algospot(알고스팟), Baekjoon Online Jubge, 프로그래머스까지 굉장히 다양하고 많아졌습니다.

각 사이트마다 채점 방식이나 결과가 다를 수 있으니, 이것을 먼저 찾아보고 이해하는 것이 좋습니다.

어떤 컴파일러로 채점하나요?

대부분의 사이트에서 C, C++ 언어는 gcc로 채점합니다. 간혹 알고스팟처럼 MSVC 컴파일러를 지원하는 곳도 있습니다.

이게 문제가 될까요?

네, 문제가 "될 수도" 있습니다.

로컬에서 Visual studio로 실행한 결과는 MSVC 컴파일러가 해석한 코드를 실행한 결과입니다. 하지만 채점할때는 같은 코드를 gcc 컴파일러를 사용하여 실행했다면 결과가 다른 경우가 종종 있습니다.

이것은 조금 다른 이야기지만, Visual Studio의 경우 SDL 검사(보안) 때문에 scanf 가 아닌 scanf_s 등 조금은 다른 함수를 사용하는 경우가 있습니다. 이것은 gcc에는 없는 함수들입니다. 이대로 제출한다면 당연히 컴파일 에러이지요.

우리의 맞왜틀은 이렇게 티가 나지 않습니다.

 

사실 위의 모든 이야기는 해당 언어의 표준을 지키면 해결됩니다.

void main()은 비표준이고, int main()과 return 0은 표준인것이죠. 0이 아닌 다른 값을 반환한다면, 프로그램이 정상 종료 되지 않았다고 판단하여 런타임 에러(Runtime Error)를 받을 수 있습니다!

정수를 문자열로 바꾸는 itoa(), 표준 입력 버퍼를 비우는 fflush(stdin)은 비표준입니다. (근데 fflush(stdout)은 표준이고.. 흠..)

내가 사용하는 코드와 함수가 표준인지는 알고 있는 것이 좋습니다.

UB를 피하라

위와 이어지는 내용입니다.

Undefined Behavior(UB)는 표준에서 정의되지 않은 행동을 말하는 데, 다시 말하면 컴파일러마다 다른 결과를 낼 수 있다는 뜻이죠. (자세히)

가장 유명한 것은, 0으로 나누는 행동도 UB입니다. 이건 너무 유명해서 이제는 컴파일 에러가 납니다!

그 외에도 많이 있는 데, 대부분 증감 연산자에서 많이 혼란을 겪더군요.

i = i++ + 1;
i = ++i + i++;

이런 코드를 두고, 결과값을 맞히라는 것은 동전을 던지고 앞뒤를 맞히라는 문제랑 똑같습니다. 해석의 여지가 많아서 컴파일러마다 다르거든요!

가변 인자는 뒤에서부터 해석한다고 들었지만, 아래 코드도 UB에 속한다고 합니다.

printf("%d %d\n", ++n, func(n));

연산자 우선순위

UB는 아니지만 의도치 않은 결과가 나오는 경우가 종종 있죠.

printf("%d\n", 1 << 1 + 1);

이 코드의 출력 결과는 4입니다. 어떻게 된 일일까요?

1을 왼쪽으로 1만큼 shift하고, 그 값에 1을 더한 결과인 3을 기대하셨다면, 아쉽게도 결과는 그렇지 않습니다.

C++ 연산자 우선순위(https://ko.cppreference.com/w/cpp/language/operator_precedence)에 의하면, 더하기(+)연산은 쉬프트(<<)연산보다 먼저 계산됩니다.

우선순위를 모두 외울 필요는 없습니다! 다만, 값이 기대와 다르게 나왔거나 스스로 헷갈린다면, 괄호를 사용하여 모호하지 않도록 합시다.

자료형 casting

의도하지 않은 결과값으로 고생하는 경우 중 하나로, 배열의 범위를 넘기는 오버플로우는 (오류 메시지 등으로) 티가 납니다.

하지만 자료형 casting에서 발생하는 오버플로우는 눈에 보이지 않아 찾기가 힘듭니다.

아래는 에라토스테네스의 체를 구현한 (위험한) 코드입니다.

for(int i=2; i<=N; ++i){
    if (era[i]) continue;
    for(long long j=i*i; j<=N; ++j){
        era[j] = true;
    }
    printf("%d\n", i);
}

자료형 변환은 우선순위에 따라 작은 자료형이 더 큰 자료형으로 변환됩니다.

위의 예시에서 N이 커진다면, j에는 (int)i * (int)i 가 계산되어 오버플로우 된 int 값이 대입될 것입니다.

j = (long long)i * i; 로도 적을 수 있고, j = (i + 0LL) * i; 와 같이도 적을 수 있습니다.
0LL은 long long 자료형 0을 나타내는 상수입니다. 실수형은 앞의 0을 생략하고 .0 으로도 적을 수 있죠.

최대, 최소, 그리고 오버플로우

프로그램의 설계와 문제에서 요구하는 명세에 따라 천차만별입니다.

최대값과 최소값을 저장할 때, 중간 과정에서 오버플로우가 발생하지 않는 지 조심해야합니다. 아래의 예를 봅시다.

signed int val = INT_MAX;
// ...
ret = min(ret, 2 * val);

어쩌다보니 val에 INT_MAX가 들어갔다고 합시다. 그럼 여기에 1을 더하기만 해도 오버플로우가 일어납니다.

최소값이나 최대값을 INT_MIN이나 INT_MAX로 사용하는 것은 너무 타이트할 수 있습니다. 물론 잘 사용하면 좋습니다.

계산 과정에서 2배가 되어도 문제가 없을 정도의 수를 정하는 것이 좋은데, 기억하기 좋은 수가 987654321입니다. 2배를 하여도 INT_MAX인 21억을 넘지 않기 때문이죠.

다만, 답이 10억이 될 수 있는 경우에는 문제가 될 수 있기 때문에 문제 조건에 따라 적절히 수정하면 됩니다. 저는 아래의 수를 사용합니다.

const int INF = 0x3f3f3f3f;  // ‭1,061,109,567‬
const long long LINF = 0x3f3f3f3f3f3f3f3f; // ‭4,557,430,888,798,830,399‬

비트(bit)

위 두 내용이 섞여서 일어납니다.

아래 코드는 변수 a에 어떤 결과가 저장될 지 맞춰보세요.

long long a = 1 << 35;

a에는 2의 35제곱인 34,359,738,368가 아닌 다른 수가 대입됩니다..! 그 이유는 쉬프트 되는 값인 1이 long long형이 아니기 때문입니다.

올바른 게산을 위해서는 아래와 같이 수정해야 합니다.

long long a = 1LL << 35;
long long a = (long long)1 << 35;

쉬프트(shift) 연산은 단순히 2의 제곱수만큼 곱하고 나누는 연산이 아닙니다.

이런 경우도 있습니다.

int a = -1;
int b = a >> 1;

이 코드에서 변수 b에는 -1이 들어있습니다. 왜일까요?

부호 있는 자료형의 경우, 음수는 가장 앞 부호비트가 1이죠. 오른쪽으로 쉬프트 연산을 할 때 부호비트때문에 빈 자리에 1을 채우더군요.

아래 코드를 실행하면 재밌는 결과가 나옵니다.

#include <iostream>
using namespace std;
int main(){
    int a = -1;
    int b = a >> 1;
    unsigned int c = a >> 1;
    unsigned int d = (unsigned int)a >> 1;
    cout << "b is " << b << endl;  // b is -1
    cout << "c is " << c << endl;  // c is 4294967295
    cout << "d is " << d << endl;  // d is 2147483647
    return 0;
}

숨어있는 시간 복잡도

어떤 객체에 size()라는 메소드가 있고 항상 K를 반환한다고 했을 때, 다음 코드는 시간복잡도가 어떻게 될까요?

void f(const Object& obj){
    for(int i=0; i < N; ++i){
        for(int k=0; k < obj.size(); ++k){}
    }
}

위 코드는 O(N * K)이 아닌, obj.size() 메소드의 시간복잡도에 달려있습니다.

두 번째 for문의 종료 조건에서 obj.size()는 매번 호출되죠.

만약 obj.size() 가 매번 M 만큼 걸린다면, 복잡도는 O(N * K * M)이 될 겁니다. 하지만 다음 코드는 어떨까요?

void f(const Object& obj){
    int size = obj.size();
    for(int i=0; i < N; ++i){
        for(int k=0; k < size; ++k){}
    }
}

같은 값을 반환하던 size 함수는 더 이상 중복으로 호출되지 않겠죠.

클린 코드(Clean Code)

결국 클린 코드 이야기까지 나옵니다.

코딩 실수의 대부분은 오타입니다. 말도 안되는 오타가 사람을 속이고 컴파일러까지 속이는 경우가 많죠.

int n = 0;
for(int i=0; i<10; ++i){
    for(int j=0; i<20; ++j) n += 10;
}

이 코드는 어디가 문제일까요?

정답은 i<20 이었습니다.i와 j, 1, l, I, | 가 잘 구분되는 폰트를 고르는 것은 정말 중요한 일입니다. 읽기 힘든 코드가 과연 고치기는 쉬울까요?

아래에도 오타가 있습니다.

if ( a = 0 ) return false;

조건문을 해석하기 위해 a에 0을 대입하고, a의 값인 0은 거짓이므로 해당 분기(branch)는 영원히 실행되지 않습니다.

상수값을 왼쪽에 두어서, 실수로 대입이 되더라도 컴파일 에러로 확인할 수 있게 하는 것도 좋습니다.

if ( 0 = a ) return false;  // Compile Error

 

생각나는 대로 적었는데, 이 외에도 굉장히 많습니다.

마무리는 어떻게 할 지 모르겠는데, 잘못 적은 부분이 있다면 댓글로 남겨주세요.

환영하고 감사합니다. 다들 행복하세요