제 3장 : 코딩과 디버깅에 관하여

본격적인 알고리즘 설명에 들어가기에 앞서, 이 책에서는 문제풀이와 뗄래야 뗄 수 없는 코딩과 디버깅에 관한 팁 또한 소개하고 있고, 이 또한 문제풀이 공부와, 넓게 보면 개발을 위한 공부에도 도움을 줄 수 있는 내용을 소개하고 있습니다. 뒤에서 배울 문제풀이 전략이 효용 있게 적용되기 위해서 반드시 숙지해야 할 내용이라고 생각합니다.

1. 코딩(구현)의 중요성을 간과하지 말라

사실 공부를 하다 보면, 알고리즘의 작동 원리를 아는데에 치중해서, 구체적인 구현에 관해서는 알아서 되겠거니 하고 넘기는 경우가 생각보다 됩니다. 하지만, 대회의 성격에 따라서 다르겠지만, 구현이 까다로운 문제 또한 시험 등에서 나오지 말라는 이유는 없지요. 문제 풀이를 위한 멋진 알고리즘을 머리속에서 고안해 낼지라도, 그것을 실제 돌아가는 코드로 옮길 수 없다면 의미가 없습니다. 후술하는 내용들을 잘 반영한 코드를 작성하는 것은, 디버깅 할 일을 줄임으로써, 여러분의 멋진 생각을 멋진 맞았습니다 로 만들어 주는데 많은 도움을 줄 것 입니다.

간결한 코드를 작성하기

간결한 코드를 짜는것은 중요하다 라는것을 문제를 풀기 위해서 100줄 이상의 코드를 짜본 분이라면 대부분 공감할 내용일 것입니다.

이 책에서는 간결한 코드를 작성하는 방법을 소개하면서, "흑마법인" 매크로로 작성한 FOR를 소개하고 있습니다.

#define FOR(i,n) for(int i = 0 ; i < (n) ; ++i)

책에서 서술된 것처럼 모범답안은 결코 아니며, 사실 이런 코드는 볼 때, 좀 그렇습니다.
우리가 보고있는 이 종만북은 C++ 03 으로 쓰여져있어, 요즘 C++ 11 이상을 지원 안하는 대회가 그렇게 많지는 않을겁니다. 그런 의미에서 C++ 11에서 지원하는 범위 기반 for문을 간략하게 다루고 넘어가고 싶어서, 정말 간략하게만 다루어 보겠습니다.

범위 기반 for문 (C++ 11이상)

C++ 11에서부터 지원하기 시작한 범위 기반 for 문은 배열의 원소를 순회하면서 반복문 안에 있는 내용을 실행합니다. 아래와 같은 형태로 사용할 수 있습니다.

for (element_declaration : array) statement;

arr 배열의 모든 원소를 출력하게 하려면 아래와 같이 할 수 있습니다.

for(int a : arr)
    cout << a;

덤으로 한가지만 더 붙이자면, 이런 범위 기반 for문에는 element_delcaration의 자료형과 array안에 들어있는 원소의 자료형이 동일해야 하기 때문에, auto 키워드를 쓰는것이 이래저래 도움이 될 것입니다.

표준 라이브러리 공부하기

C로 코딩공부를 쭉 하다가, C++을 만났을때 가장 크게 와닿은 것이 C++ 의 표준 라이브러리인 STL이었습니다. 정렬하는것도 일일히 손으로 짜다가 그냥

#include<algorithm>
std::sort(arr.begin(),arr.end());

하면 뚝딱 하고 정렬이 되는것은 정말로 많은 시간을 절약하게 해준 고마운 친구였습니다. 왠만한 언어에는 구현상의 편의를 위해 많은 프로그래머들이 공들여 최적화 해놓은 알고리즘들과 자료구조들을 수록한 표준 라이브러리들이 있습니다.

문자열 처리, 배열, 스택, 큐, 리스트, 딕셔너리, 수학 알고리즘 등 다양한 쓸 구석 많은 친구들이 있으므로, 척척 꺼내어 쓸 수 있도록 숙지를 하는 편이 도움이 될것이라고 생각합니다. 1분1초가 아까운 시험장에서 뻔한 자료구조나 알고리즘을 본인 손으로 짜고 있으면 시간이 아깝잖아요.

항상 같은 형태로 프로그램을 작성하기

프로그램을 작성할때, 많이 쓰는 반복적인 형태의 코드들이 있을 것입니다. 이차원 평면을 이차원 배열로 나타낼 때, x,y좌표 순으로 나타낼지, 행,열 순서로 나타낼지 등등....

하나의 형태를 고수하지 않는다면, 스스로 작성한 코드를 보고도, 그 코드의 예상 결과를 잘못 예측하거나 하는 말도 안되는 불상사가 발생할 수 있습니다. 처음에는 여러가지 형태를 시도해 보다가, 자신에게 맞는 형태를 찾으면, 한가지의 형태로 쭉 써보도록 해 봅시다.

직관적인 함수, 변수 명명법 사용하기

문제 풀이를 작성할 때, 생각보다 이 문제 때문에 문제를 겪을 수 있습니다. 매개변수들을 입력했을때 특정한 조건을 만족하는지 판별하는 함수를 작성한다고 합시다. 이를테면, 두개의 수를 입력했을 때, 두 수가 서로소인지 판별하는 함수를 작성해 봅시다.

bool judge(int a1, int a2);

이런 형태로 작성하고, 두 매개변수가 서로소일때 true를 반환한다고 합시다. 하지만, 실제 코드를 짜면서, 이러한 결과물을 잊고서 결과를 반대로 예측하고 코드를 작성하는 경우가 생길수도 있습니다. 두 수의 1 이외의 공약수가 있는지 판별하고 싶을때, 아까 선언한 함수를 쓸 때 그런 상황이 생길수도 있겠죠. 그런 상황을 예방하기 위해서 아래와 같은 명명법을 사용하는것이 도움이 될 것입니다.

bool isCoprime(int a1,int a2);

자료를 정규화 해서 저장하기

이 내용은 기하 문제 같은 같은 값인데 여러 형태로 표현해야 하는 자료를 사용해야하는 문제를 풀 때 특히 중요하게 생각해야 하는 부분입니다. 0°, 360°, 720°는 모두 같은 각이고, $\frac{1}{2}$ , $\frac{2}{4}$, $\frac{3}{6}$ 은 모두 같은 값이거든요. 이러한 같은 값인데 형태가 다른 값들이 혼재하는 상황을 방지하려면, 분수의 경우에는 약분을 하여 넣을 수 있겠고, 각도의 경우에는 각의 범위를 $-180° \le x \le 180°$ 같은 형식으로 제한해서, 그러한 일들을 일어나지 않게 하는것이 꼭 필요할 것입니다.

코드와 자료를 분리해서 저장하기

날짜를 정수로 입력받아서, 해당하는 숫자의 달을 영문으로 반환하는 간단한 함수를 짜봅시다.

string getMonthName(int month){
    switch(month){
        case 1 : return "january";
        case 2 : return "february";
        case 3 : return "march";
        .....
    }
}

이렇게 코드를 짜는것은 권장되지 않습니다. 코드의 양이 방대해 지다보면, 놓칠 수 있는 실수들이 생기고, 또, 자료가 코드에 종속적으로 되면, 이 자료를 다른데서 써먹기에도 좀 불편해 지죠. 그러므로 이렇게 자료와 코드를 분리해서 저장합시다.

string monthName[] = {"january", "february", "march" ....};

string getMonthName(int month){
    return monthName[month - 1];
}

배열 범위 외 원소에 접근

C/C++은 배열에 접근할 때, 접근하는 영역이 배열에 할당된 영역인지 아닌지에 대한 별도의 검사를 수행하지 않습니다. 따라서 위의 정수를 달을 나타내는 문자열로 반환하는 코드에서 return monthName[month]라고 작성해도, month에 12를 넣었을때 다른 변수가 monthName[12]자리에 있다면 그 변수의 값을 반환하는 등, 찾기 어려운 기묘한 에러가 발생 할 수 있습니다.
그리고, 조그마한 공간 만큼만 필요하다 생각해서 배열 크기를 상대적으로 작게 잡았는데, 알고리즘이 잡은 배열보다 더 많은 영역에 접근할때도 이러한 문제가 생길 수 있겠죠.

이러한 실수를 예방하는 가장 좋은 방법은, 범위를 정할 때 신중하게 결정하는 것입니다. C/C++에서 크기가 N인 배열은 0부터 시작해서 N-1 까지의 인덱스를 가짐을 기억함과, 최대로 필요한 배열 크기를 잘 계산해서, 이상한 메모리의 위치를 참조하지 못하게 해야겠죠.

산술 오버플로를 조심하기

생각보다 많이 하는 실수입니다. 32비트 정수를 특정한 계산을 통해서 32비트 정수로 표현 가능한 결과가 나오는 식을 작성하였는데, 오버플로 때문에 이상한 값을 받아 낼 수도 있습니다.

이 내용을 이 장에서 모두 설명하려면, 포스팅의 길이가 너무 길어지므로, 다른 포스팅으로 분리해서 설명하도록 하겠습니다.

일관적으로 범위를 표현하기

구간을 나타내는 방법은 크게 열린구간과, 닫힌구간, 반 열린구간 이 있습니다. 각 방법을 간략히 설명하면 이렇습니다.

• 열린구간 (a,b)
  • $a<x<b$
• 닫힌구간 [a,b]
  • $a\le x\le b$
• 반 열린구간 [a,b)
  • $a<x\le b$

이 중에서 프로그램 언어에서 가장 흔하게 볼 수 있는 방식은 반열린 구간입니다. 우리가 배열을 순회하는 for문을 아래와 같이 작성 할 때

for(int i = 0; i < n;++i)

와 같이 작성하는것은 반열린 구간을 이용하여 배열을 순회하는 것이고, STL에서 사용하는 .begin()과 .end()도 이와 같은 방법을 사용해서 .begin()은 제일 앞 원소를, .end()는 배열 뒤의 존재하지 않는 원소를 가리키고 있거든요. 이러한 컴퓨터 언어에서 많이 사용하는 방식을 따르는것이 의도치 않은 에러를 예방하는데 도움이 될 것입니다. 함수 안과 함수 밖의 범위 표현법이 다르다면, 이건 잠재적인 에러나 다름 없지요.

Off-by-one 오류

계산의 큰 줄기는 맞지만, 세세한 부분 하나를 놓쳐서, 생기는 오류를 모두 통칭하는 말이라고 합니다. $\le$ 를 $<$ 대신 쓰는 경우, 여러 원소를 순회할 때, 한개를 더 또는 덜 순회하는 경우가 있겠네요.

흔히 겪을 수 있는 오류임을 직접 보여주기 위해서 문제 하나를 내보겠습니다.

길이가 100m인 담장에 10m 간격으로 기둥을 세울 때, 필요한 기둥의 개수는?

정답은 10/100을 한 10이 아닌, 11입니다. 0m 위치에서도 기둥은 하나 세워야 하니까요.
그 외에도, A[n] 부터 A[m] 까지의 평균을 구할 때는 m-n이 아니라, m-n+1 로 나누어야 하는것 등이 있겠네요.

스택 오버플로

스택 오버플로란, 콜 스택이 오버플로해서 프로그램이 비정상적으로 종료되는 일을 말합니다. 이걸 보게되는 가장 잦은 경우는, 지나치게 깊은 재귀 호출입니다. 재귀호출은 이래저래 많이 쓰이는 패턴이기 때문에 잦게 볼 수 있는 에러 사항이기도 하지요.

또한 C/C++ 에서는 지역변수를 일반적으로 스택 메모리에 저장하므로, 스택 오버플로를 조금이라도 피하기 위해서 힙 메모리에 공간을 잡아주는 STL 구현체들을 잘 사용하는것도 도움을 줄 수 있습니다.

잘못된 비교함수 작성

STL의 <algorithm> 헤더에 있는 std::sort를 사용할 때를 포함한 비교를 통한 정렬을 사용할 때, 본인이 직접 구현한 개체들을 정렬할 때 겪을 수 있는 문제입니다.

이산수학 과목을 수강한 독자분이시라면 strick weak ordering 이라는것을 공부했던 기억이 나실수도 있겠습니다. 비교 연산자 <는 strick weak ordering이며, 아래의 4가지 성질을 만족합니다.

• a < a는 항상 거짓 : 비반사성(Irreflexivity)
• a < b가 참이면, b < a는 거짓 : 비대칭성(asymmetry)
• a < b가 참이고, b < c가 참이면, a < c 이다 : 전이성(transitivity)
• a < b와 b < a가 모두 거짓이면, a와 b는 같다 : 상등 관계의 전이성(transitivity of equivalence)

std::sort는 위의 성질이 만족함을 가정하고, 불필요한 연산을 줄이는 최적화를 택했습니다. 그래서, 얼핏 보기에 맞아 보여도 정렬 함수가 올바르게 작동하지 않는 경우가 있을 수 있는데, 두 집합 a,b에 대해서 a가 b의 진부분 집합인지 판별하는 함수를 통해서 예를 한번 들어보겠습니다.

//a 가 b의 진부분 집합이면 true, 아니면 false를 반환한다.
bool isProperSubset(const IntegerSet& a, const IntegerSet& b);
bool operator < (const IntegerSet &a, const IntegerSet &b) {
    //a가 b의 진부분 집합이면 a가 앞에 와야한다
    if(isProperSubset(a,b)) return true;
    //b가 a의 진부분 집합이면 b가 앞에 와야한다
    if(isProperSubset(b,a)) return false;
    //둘다 아니라면 별 상관 없다.
    return false;
}

이 코드는 별 문제없어 보이지만, 위의 4번째 성질을 만족하지 않고 있습니다.

정수 집합 {1},{2},{2,3}을 생각해 봅시다. 위의 비교함수에 의하면 {2} < {2,3} 만 참이고, 나머지는 거짓입니다. 여기서 표준 라이브러리는 a < b && b < a 이면 a == b 로 판별하기 때문에, {1} == {2}, {1} == {2,3} 이라고 판별합니다. 하지만 {2} < {2,3} 이라는 위의 법칙에 어긋나는 결과가 나오므로, 정렬 함수에 문제가 생길 가능성이 존재합니다.

이러한 상황을 방지하는 방법은 a와 b가 완전히 같은 경우를 제하고는 같다고 판별이 되지 않게 함수를 짜는 일입니다. 이런 함수를 만드는 가장 간단한 방법은 사전순 비교와 크기 비교를 이용해서 짜는 일입니다. 생각보다 이 둘만 이용해서 함수를 작성해도, 비교 함수의 목적을 달성할 수 있기 때문에, 복잡한 비교함수를 작성하지 않고 코드를 작성할 수 있습니다. 아래는 부분집합을 정렬하는데 필요한 비교함수의 예 입니다.

bool operator < (const IntegerSet& a, const IntegerSet& b){
    //a가 b의 진부분 집합이면 a가 앞에 와야한다
    if(isProperSubset(a,b)) return true;
    //b가 a의 진부분 집합이면 b가 앞에 와야한다
    if(isProperSubset(b,a)) return false;
    //둘다 아니라면 사전순으로 정렬해서
    return lexicographical_compare(a.begin(),a.end(),b.begin(),b.end());
    

여기서 쓰인 lexicographical_compare는 보이는 대로 a의 처음을 가리키는 변수, a 의 끝원소 바로 뒤를 가리키는 변수, b의 처음을 가리키는 변수, b의 끝원소 바로 뒤를 가리키는 변수를 넣어서 작동하는 함수입니다. a가 b보다 사전순으로 앞에 있을 때, true를 반환하는 함수입니다.

연산자 우선순위 잘못 쓰기

특히 비트 연산을 할 때, 많이 생기는 실수입니다. 비트 연산의 우선순위는 왠만한 연산자의 순위보다 낮은 편이거든요. (비트 &,|,^ 연산자보다 우선순위가 낮은건 논리 && || 연산자와, 할당 연산자, 그리고 콤마가 끝입니다). 아래의 짧은 if 문을 살펴봅시다.

if(b & 1 == 0)

변수 b의 최하위 비트가 0인지 체크하는 문장처럼 보이지만, 실제로는 b가 어떻게 생겼든 간에 if 안에 있는 조건문은 언제나 거짓입니다.

위 코드는

if(b & (1 == 0))

와 동치거든요. 1==0은 언제나 거짓이므로 0이고 bb&0은 언제나 0이니까요.

느린 입출력 방식 선택

C++ 에서 std::cin이나 std::cout을 통해서 입출력 하는 방식은 너무나 매력적 입니다. printf와 다르게, 온갖 입력을 >>,<<연산자 오버라이딩만 올바르게 만들어 놨다면 뚝딱 하고 입출력을 뚝딱 해주니까요.

하지만 이 방식은 느리다 라는 문제점이 있습니다. 좀 많아보인다 싶은 입력들을 처리하는 문제는 입출력 방식을 쓰면 시간초과를 받는 경우가 있습니다.

이러한 상황에는 대충 2가지 해결책이 있습니다.

1. cin,cout의 표준 입출력 함수와의 동기화를 끈다.

std::cin.sync_with_stdio(false);
std::cout.sync_with_stdio(false);

단 이 방식을 사용하면, printf와 같은 표준 입출력과 스트림 입출력을 같은 코드 내에서 쓰면 안됩니다. 입출력의 순서를 보장할 수 없거든요

2. gets() scanf() 와 같은 저수준 입출력 방식을 택한다.

가장 확실한 방법입니다. 위의 1번 방법을 사용한다 해도, 저수준 입출력 방식의 속도를 따라잡을 수는 없거든요.

변수 초기화 문제

많은 프로그래밍 문제에서, 프로그램을 한번만 실행하고 여러개의 테스트 케이스를 넣어서 돌려보는 형식의 코드를 작성하는 경우가 많습니다. 이때 생길 수 있는 문제는, 이전 입력에서 사용했던 변수들을 초기화 하지 않아서, 틀렸습니다 를 받는 경우입니다. 변수를 초기화 하는 습관을 가지고, 예제 입력을 여러번 반복하는 예제를 만들어서 테스트 해보는 방법이 도움이 꽤 될 것 입니다.

2. 디버깅과 테스팅

간단한 디버깅 방법에 대한 소개

디버깅이라고 하면, 프로그램 중간 중간에 printf("aa\n"); 이런걸 넣어두고 어디까지 제대로 되고, 어디서부터 안되는지 체크하는 그런 무식한 방법을 사용하는 경우가 상당히 잦습니다. 사실 저도 그 방법으로 이것저것 만들기도 했고요....

그렇다고 해서, 디버거를 사용해라는 말을 하고 싶은것은 아닙니다. 물론 디버거가 제 역할을 분명히 합니다만, 재귀 호출이나 중복 반복문이 많이 나오는 코드를 디버거로 디버깅 하는것은 상당히 힘든 일이거든요.

다음의 간단한 작업을 하는 것만으로 디버깅을 생각보다 할 수 있는 방법이 있습니다.

• 작은 입력에 대해서 제대로 실행되나 확인
  • 입력이 크면 프로그램의 실행과정을 눈으로 따라잡기 힘듭니다. 오동작 하는 작은 입력을 통해서 코드의 문제점을 파악할 수 있습니다.
• 단정문(assertion)을 쓴다.
  • C++에는 assert()라는 것이 존재합니다. <assert.h>를 include 하면 쓸 수 있는데요, assert 문안에 있는 조건문이 거짓이면, 런타임 에러를 내는 함수입니다. 값들이 제대로 들어 가있는지 검증하기에 유용합니다.
• 프로그램의 계산 중간 결과를 출력한다.
  • 그 중간 값들이 자신의 예상결과와 맞아 떨어지는지 확인하면서 코드가 올바른지 확인해 봅시다.

간단한 테스팅 방법에 대한 소개 : 스캐폴딩

정답을 제출하기 전에, 간단한 입력 여러개로 테스팅 하고 결과를 제출하는 것은 오답률을 줄여주는데 당연히 도움이 됩니다. 간단한 입력들을 만들 수 있는 스캐폴딩 이라는 방법을 소개합니다.

스캐폴딩(Scaffolding)이란 원래 건물을 짓기 위해서 임시로 설치하는 가건물을 의미하는 말이라고 합니다. 프로그래밍 에서는 다른 코드의 뼈대를 잡기 위해서 임시로 만들어 놓은 코드를 뜻합니다.

작은 입력을 자동으로 생산해서, 시간 복잡도가 열등하지만, 확실히 답을 계산하는 코드를 하나 작성해 본인이 적은 코드가 내는 답과 일치하는지 확인할 수 있습니다.

물론 이 방법이 만능은 아닙니다. 큰 입력에서만 발생하는 오버플로 문제의 경우에는 잡기가 힘듭니다. 그래도 스캐폴딩으로 정답률을 높이는것은 결코 의미 없는 일만은 아닙니다.

3. 마무리

이번 포스팅에는 코딩을 함에 있어서 쉽게 저지를 수 있는 실수들의 유형과, 그러한 실수를 쉽게 찾아 낼 수 있는 디버깅과 테스팅 방법에 대해서 알아 보았습니다.

다음 포스팅에서는 내용이 좀 많아서 다루지 못했던 산술 오버플로에 대해서 자세히 다루어 보겠습니다.