[알고리즘 문제 해결 전략 #1] 3장 코딩과 디버깅에 관하여

이번장에서는 실용적인 코딩방법과 쉽게 디버깅 되지않는 예외에 관해서 다룬다.

 

3.1 도입 : 코딩의 중요성을 간과하지 말라

 

프로그래밍 대회에서 좋은 성적을 얻기위한 비결과 프로그래밍 대회에서 얻을 수 있는 가장 큰 소득은 간결하고 효율적인 프로그램을 작성하여 읽기 쉬운 코드를 짜는 것이다.

코드의 길이가 간결하고 명료할수록 디버깅이 편리하고 시간 또한 줄어들게 된다.

 

3.2 좋은코드를 짜기 위한 원칙

 

    1. 간결한 코드 작성하기

코드가 짧을 수록 오타나 단순한 버그가 생길 우려가 줄고, 디버깅도 쉬워진다.

대회특성상 전역변수를 잘 활용하면 간결한 코드작성이 가능해진다.

당연하지만 노력이 필요하다고 생각함.

 

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

간결한 코드작성의 가장 직접적인 방법은 반복되는 코드를 모듈화하여 재사용하는 것이다.문제를 풀다가 코드를 개선할 여유가 없더라도, 개선을 반복하다보면 간결한 코드에 익숙해지기 때문에 다음에 비슷한 코드를 작성할때 좀더 간결하게 코딩이 가능하다.

대회에서는 비슷한 유형의 문제가 빈번하게 출제되고 그에따른 접근 방법이 비슷하다. 이에따라 각 접근방법에 대한 코드 작성을 최적화 시켜두면 도움이 될 것.

 

    3. 표준 라이브러리 공부하기

자료구조를 직접 작성하는 실수를 자제하자. 표준라이브러리는 수없이 많이 검증되고 사용되기 때문에, 메모리나 정당성측면에서 편하게 사용가능하다.

언어의 문자열, 동적배열, 스택, 큐, 리스트, 사전 등의 자료구조, 표준 알고리즘 등 사용법을 익혀두자.

 

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

프로그래밍 특성상 여러종류의 코드를 반복적으로 작성하게 된다. 유명한 알고리즘들

처음에는 코드를 간결하고 효율적이게 개선하는 것도 좋지만, 매번 코드를 검증한다는 것은 쉬운 일이 아니기 때문에 한번 검증이 된 코드를 작성하고 이것을 꾸준히 사용할 필요가 있다.

이러한 알고리즘들은 문제를 풀기위한 도구일 뿐이기 때문이다.

 

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

a , i , j , k 이러한 변수 명명법은 모호해서 디버깅에 치명적인 영향을 준다.

언어의 표준라이브러리에서 사용하는 명명규약을 지키면서 변수, 함수명을 사용하는 버릇을 들이자.

bool judge() -> bool isInsideCircle()

 

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

좋은 코드는 같은 자료를 두가지 형태로 저장하지 않는다. 예를들어 유리수 클래스를 작성할 때  9 / 6 과 3 / 2 는 같은 자료이므로 이를 정규화하여 저장하는 것이 혼란을 겪지 않는다.

정규화는 클래스 내부에서 자료를 입력받거나 계산하자마자 곧장 이루어지는 것이 이상적이다.

 

    7. 코드와 데이터를 분리하기

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

이런식의 코드의 논리와 상관없는 데이터는 가능한 한 분리하는 것이 좋다. 

const string monthName[12] = {"January", ... , "December"};

또다른 예로 체스판의 말이 움직일 수 있는 위치를 배열로 저장해두는 것도 좋은 예이다.

 

3.3 자주 하는 실수

    1. 산술 오버플로

3.5절에서 별도로 다룬다.

 

    2. 배열 범위 밖 원소에 접근

배열과 변수가 메모리 상에 연속해서 위치할 때, 배열 범위 밖 데이터를 가져올 때 어떤 런타임에러도 발생하지 않고 엉뚱한 값을 가져오게 된다.

 

    3. 일관되지 않는 범위 표현 방식 사용하기

범위를 표현할 때 많은 언어에서 [x , y) 반 열린 구간을 사용한다.

범위 표현이 통일되지 않았을때,

average(A[],i,j)

이러한 함수를 작성하다고 했을때, 범위가 모호해질 가능성이 있다. i < n <= j 인지, i < n < j 인지 i <= n <= j 인지 등등

따라서 프로그래밍 언어가 지원하는 범위 표현방식을 따르는 것이 가장 효율적이다.

 

    4. Off-by-one 오류

계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 오류들을 가르키고,

이는 최소 입력이 주어졌을 때 코드의 동작을 되새기면 쉽게 해결이 가능하다.

 

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

변수명이나 함수명의 오타는 컴파일러가 잡아주지만, 상수 및 상수값을 잘못 입력해서 오답 처리되는 경우를 종종 볼 수 있다.

흔히 실수하는 예 : 문자열오타, 0의 개수, 64비트 정수형 자료형에 상수가 64비트라고 지정하지 않는 경우

 

    6. 스택 오버플로

프로그래밍 환경의 스택 허용량은 언어나, 아키텍쳐 등에 따라 매우 다르기 때문에

재귀 호출을 과도하게 호출 한다거나, c++의 경우 지역변수나 클래스 인스턴스가 스택 메모리를 사용하므로 큰 지역변수를 할당할 경우 쉽게 스택 오버플로가 발생할 수 있다.

따라서 전역변수를 사용하거나, 힙에 메모리를 할당하는 STL 컨테이너를 사용한다.

 

   7. 다차원 배열 인덱스 순서 바꿔 쓰기

높은 차원의 배열을 인덱싱할때, 순서를 혼동하는 일이 발생한다. 따라서 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋다. c++에서는 참조 변수를 사용한다.

 

    8. 잘못된 비교 함수 작성

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

 

    10. 연산자 우선순위 잘못 쓰기

if(b & 1 == 0)

위의 연산은 1 == 0 이 수행 된 후, b & 0 이 수행되어 결과가 의도와 달라질 수 있다.

shift 연산자, 비트 연산자 등 우선순위가 헷갈리는 경우에는 적절히 괄호로 묶어주는 것을 잊지말자.

 

    11. 너무 느린 입출력 방식 선택

수천 수만줄의 입력 및 출력을 요구하는 문제는 고수준 입출력 방식을 사용하는 것보다 저수준 방식이 2배 더 빠른 경우도 심심찮게 볼 수 있다.

따라서 c++에서는 gets() , python에서는 sys.stdin.readline 과 같은 입출력 방식을 알아두도록하자.

 

    12. 변수 초기화 문제

보통 문제가 발생하지만, 우연히 그렇지 않을경우에 예제입력을 2배로 하여 테스트하는 경우 오류를 검출 가능하다.

 

 

3.4 디버깅과 테스팅

 

    1. 디버깅에 관하여

프로그래밍 대회의 소스의 경우 길지 않기 때문에, 눈으로 디버깅하는 쪽이 훨씬 빠른 경우가 적지 않다.

또한 잘 분리된 기능적인 코드는 디버거 없이 눈만으로도 검증하기가 비교적 쉽다.

그래도 디버거를 사용해야 한다면, 우선적으로 다음과 같은 단계를 밟는 것을 추천한다.

 - 작은 입력에 대해 제대로 실행되나 확인하기

 - 단정문(Assertion)을 이용하여 값들의 유효성을 점검하기

 - 프로그램 계산 중간 결과를 출력하기

 

    2. 테스트에 관하여

예제 입력외에 간단한 예제 입력을 만들어 테스트하여 값이 잘나오는 지 확인하는 것이 좋다.

스캐폴딩(scaffolding)이라는 기법을 사용하여 테스트입력값을 자동으로 생성해 프로그램을 돌려보고, 답안을 검증하는 프로그램을 생성하면 큰 도움이된다.

하지만 모든 문제를 찾아낼 수 없기 때문에, 소중한 코딩 시간을 잡아먹지 않도록 필요한 경우에만 사용하도록 한다.

 

3.5 변수 범위의 이해

    1. 산술 오버플로

숫자는 무한하지만 메모리는 유한하기 때문에, 어쩔 수 없이 표현할 수 있는 숫자는 제한된다.

대부분의 언어들은 오버플로를 경고를 해주지않고, 프로그램의 논리의 정확성에만 집중하면 산술 오버플로의 존재를 잊기 쉬워 발생하는 가장 흔한 실수이다.

 

- 너무 큰 결과

결과값이 32비트 정수 범위에 포함되지 않을 경우, 64비트 정수 결과를 계산할때 32비트 정수를 사용하는 경우

- 너무 큰 중간 값

32비트 부호 정수를 계산할 때, 중간 과정에서 큰 값을 일시적으로 계산해야 하는경우

- 너무 큰 '무한대' 값

무한대로 지정한 값들의 곱이나 덧샘이 발생하는 경우, 한계범위에 너무가까운 무한대 값을 지정하여 계산 후 오버플로우로 음수가 되는경우

무한대는 32비트 부호 정수의 경우 987654321을 자주 이용한다.

 

    2. 오버플로 피해가기

- 연산의 순서를 바꾸기

- 이항계수와 같은 경우 점화식을 이용하기

 

    3. 자료형의 프로모션

다른 자료형들의 계산이나, 자료형의 범위가 너무 작은 경우 컴파일러는 이를 같은 자료형으로 변화하여 계산하는데, 이때 알기 어려운  버그를 만드는 경우가 있다.

 

c++ 프로모션 규칙 : 

1. 정수 , 실수 => 실수 , 실수

2. 모두 정수 혹은 모두 실수 => 더 넓은 범위를 갖는 자료형

3. 양쪽다 int 형보다 작은 정수형 : 양쪽 다 int 형

4. 부호 없는 정수 , 부호 있는 정수 => 부호 없는 정수형으로 변환

unsigned char a = 17;
short b = -18;
int c = 2;
unsigned int d = 0;
cout << (a + b) * c + d << endl;

위와 같은경우 int와 unsigned int 의 계산 값이 -2 이지만 unsigned int 로 담을 수 없어 오버플로우가 일어남

 

3.6 실수 자료형의 이해

    1. 실수 연산의 여려움

컴퓨터는 무한한 실수를 표현하기 위해 근사값을 이용한다.

보통의 컴퓨터는 IEEE 754표준을 사용한다.

이는 이진수로 실수를 표기, 부동 소수점 표기법, 무한대 비정규수 NaN(Not a Number) 등 특수 값이 존재한다.

자료형	부호 비트	지수 비트	가수 비트	지수 범위	유효 자리수
32비트 실수	1	8	23	-2^7+2~2^7-1	6
64비트 실수	1	11	52	-2^10+2~2^10-1	15
80비트 실수	1	15	64	-2^14+2~2^14-1	18

    2. 실수 비교하기

실수를 비교할때, 2의 거듭제곱으로 나누어 떨어지지 않는 수는 실수 변수에 정확하게 담을 수 없어 어느정도의 오차를 염두해 두어야 한다.

bool absoluteEqual(double a, double b){
    return fabs(a-b) < 1e-10;
}

임의로 1e-10을 오차값으로 지정하였지만 이는 안전하지 않다. 10^20 / 50 * 50 을 계산할 경우,  10^20 / 50 의 오차는 매우 크고, 그 값에 50을 곱한다면 오차는 더욱 커져 1e-10보다는 훨씬 클 것이다.

 

하나. 비교할 실수의 크기들에 비례한 오차 한도를 정한다

만일 입력의 최대치와 최소치를 예측할 수 있는 경우에, 오차 한도의 상한과 하한을 이끌어내어 이 안에서 적절한 값을 오차 한도로 선택하는 방법이 있다.

 

둘. 상대 오차를 이용한다.

//절대오차 : 1e-10
//상대오차 : a와 b의 오차가 더 큰 수의 0.000001% 이하이면 true를 반환한다.
//절대 오차와 상대오차를 모두 이용해서 두수 가 같은지 판정한다.
boll doubleEqual(double a, double b){
    double diff = fabs(a-b);
    if(diff < 1e-10) return true;
    return diff <= 1e-8 * max(fabs(a) , fabs(b));
}

위의 상대오차 계산식으로 실질적인 오차 허용범위가 a,b 에 따라서 달라지도록 판정한다. 19999와 20000의 상대오차와 1.9999 와 2의 상대오차가 같다는 사실을 통해 보여진다.

 

    3. 대소 비교

실수의 대소비교를 할때, 위에서 두 값이 아주 가까운 경우를 먼저 확인하고 처리 해주어야한다.

 

    4. 정확한 사칙연산

실수변수는 가수부에 해당하는 정수와 분모가 2의 거듭제곱인 유리수들도 정확하게 표현 가능하다.

또한 유리수의 클래스를 만들거나, 십진수 클래스를 사용하는 방법도 있다.

 

    5. 코드의 수치적 안정성 파악하기

실수의 오차들로 인해서 함수가 거짓을 반환할 때, 원래 답과 엄청나게 차이나는 결과를 반환할 때 수지척으로 불안정하다고 한다. 이는 알고리즘의 특징에 따라 좌우되고, 판단하는데 시행착오와 경험이 필요하다.

 

    6. 경고

이것으로 실수의 모든것을 알았다고 생각하면 큰 실수이다.

 

    7. 실수 연산 아예 하지 않기

- 결과가 정수인 것을 안다면 곱셈과 나눗셈 순서 바꾸기

- 양변 제곱하여 제곱근 없애기

- 실수 좌표를 쓰는 기하문제에서 좌표계를 가로 세로로 정수배 늘리기