자주하는 실수 정리

실수를 안할 수 없지만 내가하거나 남이하는 실수에서 배움을 얻어 유사한 실수를 저지르지 않는 것이 중요합니다. 

프로그래밍 대회에서 흔히 저지르는 실수들을 정리해보면서 저에게도 각인시킬려고 합니다.

 

산술 오버플로

계산과정에서 변수의 표현 범위를 벗어나는 값을 사용하는 산술 오버플로

 

 

배열 범위 밖 원소 접근

C/C++은 배열의 원소에 접근 시 인덱스가 배열 범위 안에있는지 확인을 따로 안합니다.

따라서 버그를 찾기에 매우 힘든 오류입니다. 그나마 런타임 스택 등을 통해 프로그램이 런타임 오류를 내며 종료하는 경우에는 배열 범위 밖에 접근했다는 사실을 알 수도 있지만, 오류가 나지 않으면서 오답을 내는 경우도 있습니다.

int array[10], t;

이때 변수 array와 t가 메모리 상에 연속해서 위치하고 있어, 실수로 array[10]에 값을 넣어버리면 t에 있던 값이 덮어씌워집니다. 이런 접근은 어떤 런타임 에러도 내지 않고, 매우 찾기 어려운 버그로 남습니다.

이런 실수를 안하기 위해서는 배열 크기를 정할 때 크기를 신중히 해야합니다. 

하지만 0을 시작하는 범위와 1을 시작하는 범위를 혼동할 수 있어 항상 배열 사용시에는 조심 해야합니다.

 

 

일관되지 않은 범위 표현 방식 사용

대부분 프로그래밍 언어는 반 열린 구간(half-open interval)을 사용합니다. 첫번째 값은 집합 안에 포함시키고, 다른 하나는 집합 안에 포함시키지 않는 [lo, hi) 로 lo, lo+1, ... hi-2, hi-1을 포함합니다. 

이런 범위를 사용하는 프로그래밍언어의 예는 다음과 같습니다.

• n개의 원소를 가지는 배열 a의 첫 번째 원소는 a[0], 마지막 원소는 a[n-1]
• C++ STL에서는 반복자로 범위를 표현할 때 첫 원소를 가리키는 반복자와 마지막 원소 다음 위치를 가리키는 반복자를 사용합니다. STL구조에서 begin(), end()범위를 사용하는데 begin()은 첫 번째 원소를 가리키지만 end()는 마지막 원소가 아니라 마지막 원소의 다음 가상의 원소를 가리킵니다.
• 파이썬에서 배열의 일부를 a[4:8]과 같은 문법으로 잘라내는데 이렇게 잘라내면 a[4] ~ a[7]까지 포함하는 부분배열을 얻을 수 있습니다.

이러면 [3,3)같이 처음 인덱스와 마지막 인덱스가 같을 경우처럼 빈 공간을 쉽게 표현할 수 있습니다.

또한 서로다른 두 구간 [a,b),[c,d)와 같이 있을 때 b=c 혹은 a=d를 확인한다면 연속인지 확인 할 수 있습니다.

하지만 이런 선택은 자연어에서 사용하는 범위와 다르다는 이유로 문제가 생기기도 합니다.

 

이 문제를 피하기 위해서는 프로그램 내에서는 한 가지 방법으로만 범위를 표현할 필요가 있습니다.

 

 

Off-by-one 오류

계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 남아서 틀리는 코드의 오류들을 가리킵니다. 

ex) 길이가 100m인 담장에 10m간격으로 울타리 기둥을 세운다고 할 때 기둥이 필요한 갯수는?

답은 10개가 아니라 11개입니다. 

이와 같은 오류는 반복문에서 <,> 연산자 아니면 <=,>= 연산자를 혼동하여 원소를 하나 더 적게, 혹은 많이 순회하는 경우나 반 열린 구간과 닫힌 구간을 서로 혼용해 쓴 경우 많이 발생합니다.

이를 대비해서라도 코드를 짤 때 어떻게 동작할지 되새겨 보면서 짜는 것이 중요합니다.

 

 

컴파일러가 잡아주지 못하는 상수 오타

변수명이나 함수명에서 낸 오타는 컴파일러가 잡아줍니다. 하지만 각종 상수를 잘못 입력하는 불상사가 발생할 경우 오답으로 처리되는 안타까운 일이 많이 일어나기도 합니다.

• 코드와 데이터를 분리하기 위해 데이터를 별도의 상수 배열에 저장하는 것은 좋은 버릇입니다.
• 문제에 따라 전부 대문자로 써야하는데 첫글자만 대문자를 쓰는 경우, 출력할 문자열 상수를 스펠링을 틀리는 경우
• 큰 상수에서 자리수를 잘못넣어서 0을 덜 집어넣거나 더 집어넣는 경우
• 64비트 정수형에 들어갈 상수를 쓰면서 해당 상수가 64비트라고 지정하지 않는 실수 등 입니다.

C++에서는 정수형 상수 뒤에 LL을 붙이지 않으면 해당 상수는 32비트로 가정되므로, 자료형이 정확하다고 해도 오버플로가 발생할 수 있습니다. 따라서 자신이 사용하는 언어에서 상수의 타입을 어떻게 지정하는지, 지정하지 않는 경우 어느 형태로 강제되는지에 대해 미리 알아 두는 것이 좋습니다.

 

 

스택 오버플로

프로그램의 실행 중 콜 스택(call stack)이 오버플로에서 프로그램이 강제종료 되는 것 또한 흔히 하는 실수입니다.

보통 재귀 호출 깊이가 너무 깊어져서 오는 경우가 많아 늘 유의하는게 좋습니다.

스택 최대 크기는 컴파일이나 실행시에 설정할 수 있고 기본 값이 언어나 아키텍처 등에 따라 매우 다르기 때문에 대회에서 사용하는 환경의 스택 허용량에 대해 알아 둘 필요가 있습니다.

 

C++의 경우에는 지역 변수로 선언한 배열이나 클래스 인스턴스가 기본적으로 스택 메모리를 사용하기 때문에 특히나 스택 오버플로를 조심해야합니다. 배열 등의 큰 지역 변수를 스택에 잡으면 재귀 호출이 몇 번 없어도 곧장 스택 오버플로가 나기 쉽기때문입니다. 때문에 대부분의 사람들은 힙에 메모리를 할당하는 STL 컨테이너를 사용하거나 전역 변수를 사용하곤 합니다.

 

 

잘못된 비교 함수 작성

정수의 집합들을 다루는 프로그램에 정수의 집합을 저장하는 IntegerSet 클래스가 있다고 가정하겠습니다. 이 프로그램이 하는 일은 vector<IntegerSet>에 담긴 집합들을 순서대로 처리하는 것입니다. 집합 A가 B의 진부분집합이라면 A는 항상 B보다 먼저 처리되어야 합니다. 이 문제를 해결하기 우해서 IntegerSet의 배열을 정리할려고 합니다.

IntegerSet처럼 사용자가 작성한 클래스를 정렬할 때는 정렬 함수에 비교 함수를 전달하거나, 연산자 오버로딩을 이용해 < 연산을 오버로딩해야합니다. 

// a가 b의 진부분집합이면 true, 아니면 false 반환
bool isProperSubset(const IntegerSet& a, const IntegerSet& b);

//a가 b의 진부분집합일때 a가 항상 앞에 오도록 집합들을 정렬
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;
    //a가 꼭 앞에 올 필요도 없고, b가 꼭 앞에 올 필요도 없다
    return false
}

앞서 본 비교함수는 제대로 동작하지 않습니다. 네 개의 정수 집합 {1},{3,4},{2},{3}이 순서대로 담긴 배열을 이 코드를 이용해 정렬해 보았더니 정렬하기 전 상태로 그대로 반환되는 것을 알 수 있습니다.

C++ 표준라이브러리가 예상하는 일관된 답을 앞의 코드에서 반환하지 않는 문제를 가지고 있습니다. C++ 표준 라이브러리는 비교 함수가 < 연산자의 성질 (strict weak ordering)은 다음과 같습니다.

 

1. a<a는 항상 거짓입니다. [irreflexivity : 비반사성]
2. a<b가 참이면 b<a는 거짓입니다 [asymmetry : 비대칭성]
3. a<b가 참이고 b<c가 참이면 a<c 입니다.[transitivity : 전이성]
4. a<b와 b<a가 모두 거짓이면 a와 b는 같은 값으로 간주합니다. 또한 a=b, b=c라면 a=c입니다. [transitivity of equivalence : 상등 관계의 전이성]

앞선 코드는 4번 성질을 만족하지 못하였습니다. {1},{2},{2,3}이 있다고 가정할 때 {2}<{2,3}만 참이고 나머지는 전부 거짓입니다. 하지만 표준 라이브러리는 a<b, b<a가 모두 거짓이라면 둘이 같다고 보기 때문에 {1}={2}이고 {1}={2,3}이라고 생각합니다. 하지만 a=b=c인데 a<c인 세 원소를 정렬할 수는 없어 정렬 함수가 혼란에 빠지게 된 것입니다.

 

따라서 이 성질을 만족시키는 비교 함수를 작성하기 위한 한 가지 방법은 a 집합과 b 집합이 완전히 같은 경우를 제외하고는 두 집합이 같다고 판단하지 않는다는 알고리즘을 추가해야합니다. 이를 위해서는 우리가 원하는 조건이 성립하지 않는 두 집합에 대해서도 어떤 별도의 순서를 끼워넣어줘야합니다.

 

당연히 이 별도의 순서는 우리가 원래 정하려 했던 순서와 모순이어서는 안됩니다. 따라서 포함 관계와 서로 모순이 되지 않기 위해서 크기가 같은 집합일 때만 사전순으로 비교를 하면 됩니다.

//a가 b의 진부분집합일 때 a가 항상 앞에 오도록 집합들을 정렬
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;
    //a와 b의 크기가 다르다면 작은쪽이 앞에 와야한다
    if(a.size() != b.size()) return a.size() < b.size();
    //a와 b를 사전순으로 비교해 반환한다
    return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}

위의 코드는 이렇게 고친 비교함수의 구현을 보여주게 됩니다.

 

 

최소, 최대 예외 잘못 다루기

말 그대로 예상한 입력의 규칙에 들어맞지 않은 모든 입력입니다. 가능한 입력 중에서 최소 값과 최대 값이 예외가 되는 문제들이 생각보다 있으므로, 코드를 짤 때 작은 입력과 가장 큰 입력에 대해 제대로 동작할지 유추해보면 오류를 잡을거라 예상합니다.

 

예를들어 자연수를 입력받아 소수(prime number)를 판정하는 함수를 예로 들어봅시다.

가장 무식한 구현법으로는 다음과 같습니다.

bool isPrime(int n){
	if(n%2 == 0) return false;
    for(int i=2; i<n; i++)
    	if(n%i == 0)
        	return false; //2이상 , n미만의 약수가 있으면 소수가 아님
    return true; //통과하면 소수
}

위에서 보이는 가장 큰 오류는 2입니다. 2는 짝수이지만 소수이므로 거짓을 반환하면 안됩니다.

또 하나는 1을 넣을 때 입니다. 1은 소수가 아니지만 위의 코드를 보았을 때 조건문에 맞지 않으므로 참을 반환하게 됩니다.

이렇듯 예외처리는 꼼꼼하게 처리하기 쉽지 않은 것을 확인할 수 있습니다.