좋은 코드를 짜기 위한 원칙

좋은 코드를 짜기 위한 원칙

간결한 코드를 작성하기

• 코드가 짧으면 짧을수록 오타나 단순한 버그가 생길 우려가 줄어들고, 디버깅도 쉬워진다.
• 프로그래밍 대회에서만 전역 변수의 광범위한 사용
  전역 변수를 많이 사용하면 프로그램의 흐름을 파악하기 어려워지기 때문에 대개 사용하지 않는 것이 좋다.
• 프로그래밍 대회에서만 이용하는 C/C++ 매크로를 사용해 간결한 코드를 작성
  반복문처럼 자주 타이핑하게 되는 코드의 일부를 C++ 매크로로 표현한다.

적극적으로 코드 재사용하기

• 코드를 모듈화
• 같은 코드가 세 번 이상 등장한다면 항상 해당 코드를 함수로 분리해 재사용한다는 기본 원칙을 만들면 좋다.

표준 라이브러리 공부하기

• 표준 라이브러리 사용
• 시간 제한이 있는 프로그래밍 대회에서 모든 코드를 직접 작성하는 것은 대표적인 시간 낭비이다.
• 메모리 관리나 정당성 증명에 신경 쓸 필요 없이 편하게 사용할 수 있다.
• 언어의 문자열, 동적 배열, 스택, 큐, 리스트, 사전 등의 자료 구조, 그리고 정렬 등의 표준적인 알고리즘 구현 사용법을 반드시 잘 알아 두어야 한다.

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

• 같은 코드를 작성하는 더 좋은 방법에 대해 꾸준히 고민할 필요는 있지만, 자주 작성하는 알고리즘이나 코드 등에 대해서는 한 번 검증된 코드를 작성하고 이것만을 꾸준히 사용하는 것이 좋다. 그래야 문제에 집중할 수 있다.

일관적이고 명료한 명명법 사용하기

• 모호하지 않은 변수명과 함수명을 사용하는 버릇을 들이고, 사용하는 언어의 표준 라이브러리에서 사용하는 명명 규약을 익혀라

bool isInsideCircle(int y, int x, int cy, int cx, int cr);

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

• 같은 자료를 두 가지 형태로 저장하지 않는 것이 있다.
  예를 들어 유리수를 표현하는 클래스 Fraction을 작성한다고 하자. 이때 입력받는 유리수를 항상 약분해 기약 분수로 표현하는 것이 좋다. 그렇지 않으면 9/6을 표현하는 변수와 3/2을 표현하는 변수가 따로 존재하게 된다. 이런 식으로 같은 자료가 두 개 이상의 표현을 가지게 되면 미묘한 버그들을 만들기 쉽다. 각각의 문자열 표현이 달라지고, 해시 값이 달라지는 등의 문제가 있기 때문이다.
  정규화가 꼭 필요한 다른 예로, 2차원 평면 상에서 x축의 양의 방향과 주어진 점(x, y) 사이의 각도를 계산하는 것이 있다. 예를 들어 x축의 양의 방향과 점(√3, -1)사이의 각도는 -30도나, 330도 690도라고도 쓸 수 있다. 이럴 때 각도를 표현하는 방법을 한 가지로 정의해 두지 않으면 각도를 다루는 함수들을 작성하기 아주 힘들어 진다.
  이런 일들은 실무에서도 흔하게 겪게 된다. 프로그램이 시간을 표현할 경우 이것이 어ㅏ떤 시간대로 저장되었는지, 그리고 당시에 일광 절약 시간을 사용했는 지 등이 서로 섞이기 일 쑤다. 가장 좋은 방법은 항상 협정 세계시로 표시한 시간과 시간대의 조합으로 시간을 저장하는 것이다.

코드와 데이터를 분리하기

날짜를 다루는 프로그램을 작성하는데, 날짜를 출력할 때 월을 숫자가 아니라 영문 이름으로 출력해야 한다고 하자. 프로그래밍을 처음 배운 사람들이 하는 큰 실수는 다음과 같은 열두 줄짜리 함수를 짜는 것이다.

string getMonthName(int month) {
	if(month == 1) return "January";
    	if(month == 2) return "February";
        ...
        return ("December");
}

코드의 논리와 상관 없는 데이터는 가능한 한 분리하는 것이 좋다. 예를 들어 각 월의 영어 이름을 다음과 같은 테이블로 만들 수 있다.

const string monthName[] = {"January", "Fabrurary", "March", "April", "May", "June", "July", "August", "September", "October", "Nobember", "December"};

이런 방식은 항상 코드의 양을 줄여서 실수를 하지 않게 도와준다. 같은 프로그램에서 각 달에 포함된 날의 수를 사용하고 싶다면 다음과 같은 정수 배열을 선언하면 된다.

// 윤년을 별도 처리하지 않을 경우
int daysIn[12] = {31, 28, 31, 31, 31, 30, 31, 31, 30, 31, 30, 31};

이 기법의 또 다른 좋은 예로 체스 같은 보드 게임이 있다. 체스판 상에서 말들의 움직임을 다루는 문제를 풀 경우 각 말이 움직일 수 있는 위치를 프로그램으로 작성하는 대신 움직일 수 있는 상대 좌표를 배열에 저장해 두면 좋다. 예를 들면 knight가 움직일 수 있는 상대 좌표는 총 여덟 가지인데, 이를 직접 코드에 저장하기보다 다음과 같이 배열로 선언하고 배열을 순회하면서 각 위치를 검사하는 쪽이 훨씬 쉽다.

const int knightDx[8] = {2, 2, -2, -2, 1, 1, -1, -1};
const int knightDy[8] = {1, -1, 1, -1, 2, 2, 2, -2};

자주 하는 실수

산술 오버플로

배열 범위 밖 원소에 접근

C/C++는 배열의 원소에 접근할 때 해당 인덱스가 배열 범위 안에 있는지를 별도로 확인해 주지 않는다. 이 특성은 속도가 중요한 프로그램을 짤 떄는 좋지만, 덕분에 배열 범위를 벗아난 위치의 값에 접근하는 버그는 아주 찾기 힘들다. 그나마 이 과정에서 런타임 스택 등을 건드려서 프로그램이 런타임 오류를 내고 종료하는 경우에는 배열 범위 밖에 접근했다는 사실을 깨달을 수 있지만, 오류도 나지 않으면서 틀린 답만을 내놓는 경우도 더러 있다.

int array[10], t;

이때 변수 array와 t가 메모리 상에 연속해서 위치하게 되었다고 하자. 이때 실수로 array[10] 위치에 값을 대입하면 어떻게 될까? 엉뚱하게도 t에 있던 값이 덮어씌워진다. 이 접근은 어떤 런타임 에러도 내지 않으며, 매우 찾기 어려운 버그가 된다.
이런 실수를 예방하는 가장 좋은 방법은 당연하게도 배열 크기를 정할 때 계산을 신중히 하는 것이다. 하지만 다른 경우에도 이런 버그가 생길 수 있는데, 그중 흔한 것은 0을 시작으로 하는 범위와 1을 시작으로 하는 범위를 혼동하는 것이다. 한 가지 예로 1년에 포함된 각 달의 날짜 수를 저장하는 상수 배열을 사용하는 경우를 들 수 있다. 일년엔 열두 개의 달이 있으니 배열 크기도 12가 되어야 한다. 하지만 아무 생각 없이 입력으로 받은 값을 곧장 배열 인덱스로 사용한다면 엉뚱한 위치의 값에 접근할 수도 있고, 결국 배열 밖의 값을 읽어오게 된다.

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

배열의 잘못된 위치를 참조하는 오류가 발생하는 큰 원인 중 하나로, 프로그램 내에서 여러 가지의 범위 표현 방식을 섞어 쓰는 경우가 있다.
어떤 자연수 범위 [2, 3, 4, ..., 12]를 프로그램 내에서 표현하고 싶다고 하자. 이를 표현하는 자연스러운 방법은 범위 내의 첫 번째 값과 마지막 값으로 해당 범위를 표현하는 것이다. 이런 집합을 닫힌 구간(closed interval)이라고 부른다. 닫힌 구간 [2, 12]는 2 <= i <= 12인 자연수를 모두 포함한다. 이에 반대되는 개념으로 열린 구간(open interval)이 있다. 열린 구간은 양 끝의 경계를 포함하지 않는 집합으로, 열린 구간 (2, 12)는 [3, 4, ..., 11]을 나타낸다. 열린 구간으로 원래 구간을 표현하려면 (1, 13)을 써야 한다.
이 두 가지 방법에는 모두 나름의 단점이 있다. 닫힌 구간의 문제는 공집합을 우아하게 표현할 수 있는 방법이 없다는 것이다. 정 공집합을 표현하고 싶으면 a > b인 범위 [a,b]를 쓰는 수밖에 없는데, 이것은 직관적이지 않다. 반면 열린 구간의 경우에는 배열의 첫 번째 원소부터 시작하는 범위를 표현하고 싶을 경우 첫 번째 원소 이전에 존재하는 가상의 원소를 사용해야 한다는 문제가 잇다. 많은 프로그래밍 언어에서는 배열 인덱스가 0에서 시작하기 때문에, 첫 원소에서 시작하는 열린 구간을 표기하기 위해서는 음수를 써야 한다. 이것은 자연스럽지 않다.
그래서 대부분의 프로그래밍 언어는 이 둘 사이의 절충안인 반 열린 구간(half-open interval)을 사용한다. 반 열린 구간은 첫 번째 값은 집합 안에 포함하고, 다른 하나는 집합 안에 포함하지 않는다. 예를 들어 [1, 10)는 1, 2, ..., 8, 9를 포함한다. 프로그래밍 언어가 이런 범위를 사용하는 예로 다음과 같은 경우가 있다.

• 대부분의 프로그래밍 언어에서 n개의 원소를 갖는 배열 a의 첫 번째 원소는 a[0]이고, 마지막 원소는 a[n-1]이다. 따라서 a의 인덱스 i의 범위는 0 <= i < n이다.
• C++ STL에서는 반복자로 범위를 표현할 때 첫 원소를 가리키는 반복자와 마지막 원소 다음 위치를 가리키는 반복자를 사용한다. 예를 들어 STL 자료구조에서 모든 원소를 갖는 범위는 begin(), end()로 표현하는데, begin()은 첫 번째 원소를 가리키지만 end()는 마지막 원소가 아니라 마지막 원소 다음에 있는 가상의 우너소를 가리킨다.
• 자바의 SortedSet 인터페이스는 범위를 fromElement와 toElement로 전달받는데, fromElement는 범위에 포함되지만 toElement는 포함되지 않는다.
• 파이썬에서는 배열의 일부를 a[4:8]과 같은 문법으로 잘라낼 수 있는데, 이렇게 잘라내면 a[4]부터 a[7]까지를 포함하는 부분 배열을 얻을 수 있다.

이러한 선택에는 장점들이 있다.

• 첫 번째 값과 마지막 값이 같은 구간을 이용하면 텅 빈 구간을 쉽게 표현할 수 있다. [2,2)로 표현된 반 열린 구간은 2 <= i < 2인 모든 i를 포함하므로 공집합이 된다.
• 두 구간이 연속해 있는지를 쉽게 알 수 있다. 두 구간 [a,b)와 [c,d)가 연속해 있는지를 보려면 b=c 혹은 a=d인지만 확인하면 된다.
• 구간의 크기를 쉽게 알 수 있다. [a,b)로 표현된 구간에 포함된 자연수의 수는 b-a가 된다.

Off-by-one 오류

계싼의 큰 줄기는 맞지만 하나가모자라거나 하나가 많아서 틀리는 코드의 오류들을 모두 가리킨다. 예를 들어 길이가 100미터인 담장에 10미터 간격으로 울타리 기둥을 세운다고 하자. 기둥이 몇개 필요할까? 정답은 10개가 아니라 11개이다.
Off-by-one 오류는 반복문에서 < 혹은 > 연산자와 <= 혹은 >= 연산자를 혼동하여 원소를 하나 더 적게, 혹은 많이 순회하는 경우나 반 열린 구간과 닫힌 구간을 서로 혼용해 쓴 경우 흔하게 발생한다. 이런 오류를 방지할 수 있는 좋은 방법은 최소 입력이 주어졌을 때 이 코드가 어떻게 동작할지를 되새겨 보면서 프로그램을 짜는 것이다.

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

변수명이나 함수명에서 낸 오타는 컴파일러가 잡아 주기 때문에 프로그램을 짤 때 오타에 대해서는 걱정하지 않는 경우가 많다. 하지만 각종 상수를 잘못 입력해서 문제를 잘 풀어 놓고도 오답 처리되는 경우를 종종 볼 수 있다. 흔히 실수하는 것으로 다음과 같은 것들이 있다.

• 코드와 데이터를 분리하기 위해 데이터를 별도의 상수 배열에 저장하는 것은 좋은 버릇이다. 그러나 여기에 오타가 발생하면 멀쩡한 코드만 한참 디버깅할 수도 있다.
• 출력할 문자열 상수를 잘못 쓰는 것도 종종 있는 실수이다.
• 계산해야 할 값이 아주 큰 경우 큰 수 M으로 나눈 나머지를 대신 계산하는 문제들이 있다. 이때 M은 100000007 같이 큰 상수들로 지정되는데 0의 개수를 틀리게 쓰거나 하는 것도 흔한 실수이다.
• 64비트 정수형에 들어갈 상수를 쓰면서 해당 상수가 64비트라고 지정하지 않는 실수 또한 종종 볼 수 있다. C++의 경우 정수형 상수 뒤에 LL을 붙이지 않으면 해당 상수는 32비트로 가정되므로, 자료형이 정확하다고 해도 오버플로가 발생할 수 있다. 자신이 사용하는 언어에서 상수의 타입을 어떻게 지정하는지, 지정하지 않는 경우 어느 형태로 강제되는지에 대해 미리 알아 두는 것이 좋다.

스택 오버플로

프로그램의 실행 중 콜 스택(call stack)이 오버플로해서 프로그램이 강제종료 되는 것 또한 흔히 하는 실수이다. 스택 오버플로는 대개 재귀 호출의 깊이가 너무 깊어져서 오는데, 프로그래밍 대회를 공부하면서 재귀 호출을 사용할 일이 굉장히 많기 때문에 이런 점은 늘 유의하는 것이 좋다. 스택 최대 크기는 컴파일이나 실행시에 설정할 수 있고 기본 값이 언어나 아키텍처 등에 따라 매우 다르기 때문에 대회에서 사용하는 환경의 스택 허용량에 대해 알아 둘 필요가 있다.

다차원 배열 인데스 순서 바꿔 쓰기

평소에는 2차원 이상의 다차원 배열을 사용할 일이 많지 않지만, 프로그래밍 대회에서는 심심찮게 4,5 차원 이상의 고차원 배열을 쓰게 된다. 이 배열을 이곳저곳에서 접근하다 보면 한군데쯤에서 인덱스의 순서를 헷갈려서 잘못 쓰는 일이 흔히 있다. 이런 경우에는 가능한 한 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋다.

잘못된 비교 함수 작성

정수의 집합들을 다루는 프로그램에 정수의 집합을 저장하는 IntegerSet 클래스가 있다고 하자. 이 프로그램이 하는 일 중 하나는 vector<Integer>에 담긴 집합들을 순서대로 처리하는 것인데, 집합 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;
}

이 코드는 문제가 있다. 위 코드는 C++ 표준 라이브러리가 예상하는 일관된 답을 코드가 반환하지 않는다는 문제가 있다.
< 연산자의 성질을 요약하면 다음과 같다.
1. a < a는 항상 거짓이다. 이 성질을 비반사성이라고 한다.
2. a < b가 참이면 b < a는 거짓이다. 이 성질을 비대칭성이라고 한다.
3. a < b가 참이고 b < c가 참이면 a < c이다. 이 성질을 전이성이라고 한다.
4. a < b와 b < a가 모두 거짓이면 a와 b는 같은 값으로 간주한다. a와 b가 같고, b와 c가 같다면 a와 c도 같아야 한다. 이 성질을 상등 관계의 전이성이라고 한다.
위의 코드는 4번 성질을 만족시키지 못함을 다음 예제를 통해 알 수 있다.
세 정수 집합 {1}, {2}, {2, 3}이 있다고 하자. 우리가 만든 비교 함수에 의하면 {2} < {2, 3}만 참이고 나머지는 전부 거짓이다. 그런데 표준 라이브러리는 a < b와 b < a가 모두 거짓이라면 a와 b가 같다고 가정하기 때문에 {1} = {2}이고 {1} = {2, 3}이라고 생각한다. a = b = c인데 a < c인 세 원소를 정렬할 수는 없으므로, 정렬 함수가 작동하지 않는다.
이 성질을 만족시키는 비교 함수를 작성하기 위한 한 가지 방법은 a와 b가 완전히 같은 경루를 제외하고는 어느 때도 두 집합이 같다고 판단하지 않는 것이다. 이를 위해서 우리가 원하는 조건(포함 관계)이 성립하지 않는 두 집합에 대해서도 어떤 별도의 순서를 정해 줘야 한다.
이 별도의 순서는 우리가 원래 정하려 했던 순서와 모순이어서는 안된다. 예를 들어 포함 관계가 성립하지 않는 두 집합의 경우 사전순으로 먼저 오는 쪽이 앞에 오기로 했다고 하자. 그러나 a = {3}, b = {1, 3}, c = {2}라고 하면 a는 b 앞에 와야 하고 (포함 관계), b는 c 앞에 와야 하고(사전 순), c는 a 앞에 와야 하기 때문에(사전 순), 세 집합의 순서가 명확히 정의되지 않는다는 문제점이 있다. 이것은 사전순서가 포함 관계와 서로 모순되기 때문이다. 이러한 비교관계를 잘 알아야 한다.
또 하나 실수하기 쉬운 부분은 자바의 표준 라이브러리가 < 연산대신에 <= 연산을 비교 함수의 모델로 쓴다는 것이다. C++와 자바를 번갈아 쓰는 사람이 실수하기 아주 좋은 차이점이다.

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

예외란 말 그대로 우리가 예상한 입력의 규칙에 들어맞지 않는 모든 입력이다. 가능한 입력 중 최소 값과 최대 값이 예외가 되는 문제들은 생각 외로 많다. 그러므로 코드를 짤 때 가장 작은 입력과 가장 큰 입력에 대해 제대로 동작할지를 생각해 보면 오류를 잡을 수 있는 경우가 꽤 있다.

연산자 우선순위 잘못 쓰기

연산자 우선순위는 종종 잡기 힘든 버그를 만든다. 사칙연산의 우선순위는 모두 잘 알고 있기 때문에 혼동하는 일이 적지만, 시프트 연산자나 비트 단위 연산자들의 우선순위는 종종 헷갈린다. 따라서 연산자의 우선순위들을 잘 기억해 두거나, 헷갈릴 경우에는 괄호로 적절히 감싸는 것을 잊지 말자.

너무 느린 입출력 방식 선택

대부분의 프로그래밍 언어에서는 텍스트를 입출력할 수 있는 다양한 방법을 제공한다. 예를 들어 C++에서는 gets()를 이용해 모든 입력을 문자열 하나로 읽어들인 뒤 파싱할 수도 있고, cin 등의 고수준 입력 방식을 사용할 수도 있다. 대개의 경우 고수준 입출력 방식을 이용하면 코드가 간단해지지만, 이에 따른 속도 저하 또한 클 수 있따. cin같은 고수준 입출력 방식이 저수준 방식보다 두 배 이상 느린 경우도 심심찮게 볼 수 있다. 따라서 입출력의 양이 많다면 어떤 입출력 방식을 선택하는지가 프로그램의 정답 여부를 충분히 바꿔 놓을 만한 요소가 된다. 입력으로 받거나 출력해야 할 변수의 수가 1만 개를 넘어가면 고민하는 것이 좋다.

변수 초기화 문제

많은 프로그래밍 대회에서는 프로그램을 한 번만 실행하고, 한 번에 여러 개의 입력에 대해 답을 처리하라고 요구한다. 이때 흔한 실수는 이전 입력에서 사용한 전역 변수 값을 초기화하지 않고 그대로 사용하는 것이다. C/C++의 전역 변수나 다른언어들에서의 멤버 변수들은 생성시에 모두 기본값으로 초기화되는데, 별도의 초기화를 직접 하지 않고 이 행동에 의존했을 경우 두 번째 입력부터는 답이 잘못 나올 수 있다.
완전하지는 않지만 이런 실수를 예방하기 위한 팁 하나는 예제 입력 파일을 두 번 반복해 쓰는 것이다.

4	// 입력 예제의 수
1234	// 첫 번째 입력 예제
321	// 두 번째 입력 예제

4	// 입력 예제의 수
1234	// 첫 번째 입력 예제
321	// 두 번째 입력 예제
1234	// 첫 번째 입력 예제(반복)
321	// 두 번째 입력 예제(반복)

이렇게 하면 예제 간의 의존 관계 때문에 우연히 답이 나오는 경우를 방지할 수 있다. 물론 가장 좋은 방법은 새 테스트 케이스를 처리할 때마다 변수들을 적절히 초기화하도록 신경 써서 코딩하는 것이다.

출처

• 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략