코딩과 디버깅

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음.

 

목차 (클릭 시 이동)

 

1.  알고리즘 대회를 위한 코딩 원칙.

간결한 코드 작성

전역 변수를 사용하면 코드가 간결하다. 보통은 안 좋은 습관이지만, 대회 문제는 변수의 사용처가 명확해 대부분 문제가 없다. 또한, 자주 사용되는 코드를 매크로로 작성하면 편하다.

코드 재사용

반복되는 코드는 함수로 분리해 재사용한다.

표준 라이브러리 활용

알고리즘, 자료 구조를 직접 구현하는 것은 시간 낭비다. 표준 라이브러리를 적극 활용하자.

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

반복적으로 작성되는 코드(이분검색, 너비 우선 탐색 등 유명한 알고리즘) 는 같은 형태로 작성하자. 다만, 처음에는 자신이 알아보기 쉬운 코드를 알기 위해 다양한 방식으로 작성해보는 것도 좋다. 이후 스스로 검증된 코드를 작성하고 이를 꾸준히 사용한다.

일관적, 명료한 명명법 사용

변수명, 함수명을 보면 역할을 즉시 파악하도록 명료하게 작성하기.

정규화된 자료를 저장

동일한 자료가 여러 형태로 저장되지 않기 위해 정규화하기. 입력 받은 유리수는 항상 기약분수로, 각도 표현 (-30 = 330 = 690), 시간은 항상 UTC, 문자열 인코딩 통일 등. 정규화 작업은 자료를 입력받거나 계산하는 즉시 수행하는 것으로 통일한다.

코드와 데이터를 분리

일일이 하드코딩 하는 것이 아니라 배열 등의 변수로 분리하는 것이 코드의 양을 줄이고

오자 등의 실수를 방지한다. 월(Months), 각 달의 총 날짜, 체스 말의 움직임 등.

2. 자주 하는 실수

배열의 범위를 넘어간 접근

int array[10], t;  와 같이 선언된 경우 array와 t가 메모리 상에 연속되어 있다면 array[10] 에 값을 대입할 때 t에 값이 덮어씌워지고 아무런 런타임 에러도 내지 않는 찾기 어려운 버그가 된다.

 

월(Months)을 배열로 사용하는 등의 경우는 실제 데이터 (1,2,3... 월) 보다 1 만큼 작음을 염두해야 한다. (인덱스는 0 부터 시작하므로.)

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

같은 프로그램 내에서 여러 범위 표현 방식을 섞어 쓰는 경우가 있는데 이는 배열의 잘못된 위치를 참조하게 되기 쉽다.

 

닫힌 구간을 사용할 경우 공집합을 잘 표현할 방법이 없다. a>b 인 범위 [a,b] 를 사용할 순 있지만, 직관적이지 않다.

 

열린 구간을 사용하면 배열의 첫 원소부터 시작하는 범위를 표현할 때 첫 원소 이전에 있는 가상의 원소를 사용해야 한다. (대부분 배열 인덱스는 0에서 시작하므로 열린 구간 표현 시 음수를 사용, 부자연스럽다.)

 

반 열린구간은 많은 언어에서 사용하는 범위 표현 방식이다. [2,2) 와 같은 형태로 공집합 표현이 쉽고, 구간의 크기가 직관적이며( [a,b)구간의 자연수 개수는 b-a개.), 두 구간이 연속한지 확인이 쉽다. ( [a,b), [c,d) 에서 b=c 이거나 a=d이면 연속한 구간.)

 

프로그램 내에서는 한가지 방법으로만 범위를 표현하는 것이 좋고, 해당 언어가 지원하는 범위 표현 방식을 따르는 것이 효율적이다.

Off-by-one 오류

하나가 모자라거나 많아서 틀리는 오류.

 

100미터 길이 담장에 10미터 간격의 울타리 기둥은 10개가 아닌 11개가 필요하다.

배열 A[i] 부터 A[j]까지 평균은 j-i+1로 나누어야 한다.

 

부등호 <, >, ≤, ≥ 를 혼동하거나 반 열린 구간과 닫힌 구간을 혼용해 쓰는 경우에 주의하자. 최소 입력에 대한 코드 동작 방식을 생각하며 프로그래밍 하는 것도 좋은 방법이다. (담장이 0미터라면 기둥은 1개 필요, A[1] 부터 A[1]까지 평균을 구할 때 0이 아닌 1로 나눈다.)

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

변수명, 함수명과 달리 상수 오타는 컴파일러가 잡을 수 없다. 대회에서도 출력할 문자열 상수를 잘못 입력해 틀리는 경우가 많다.

 

64비트 정수형에 들어갈 상수 선언 시 64비트라고 명시해야 하는 경우도 있다. C++에서 상수 뒤에 LL이 없으면 32비트 상수로 가정돼 오버플로가 발생할 수 있다. 

스택 오버플로

런타임 중 콜 스택의 오버플로로 프로그램이 종료할 수 있다. 대부분 재귀 호출이 너무 깊어 발생한다. C++은 지역 변수 배열이나 클래스 인스턴스가 스택 메모리를 사용하므로 스택 오버플로가 쉽다. STL 컨테이너를 사용해 힙에 할당되게 하거나 전역 변수를 사용하자.

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

다차원 배열을 사용하는 경우 인덱스 순서를 혼동하기 쉽다. 유용한 방법 중 하나는 특정 인덱스 접근을 참조 변수로  통일하기. (메모이제이션 기법에서 활용된다.)

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

소수를 판별하는 함수의 경우 작은 입력 (1, 2) 에 대해 따로 고려하지 않으면 실수하기 쉽다.

연산자 우선순위 실수

if(b &  1 == 0) 의 경우 & 가 == 보다 우선순위가 낮아 if(b & (1 == 0)) 으로 해석된다. 우선순위가  헷갈리는 경우 괄호를 적절히 사용하자.

너무 느린 입출력 방식 선택

C++에서 gets(), cin등의 고수준 입력 방식을 사용하면 코드가 간단하지만 속도가 저하될 수 있다. cin의 경우 <cstdio>의 표준 입출력 함수와 동기화를 끄면 훨씬 빨리진다. 또한, 보통 출력 변수가 1만 개를 넘기면 속도 저하에 주의하는 것이 좋다.

 

int main() {
	// 표준 입출력 함수와 동기화 끄기.
	cin.sync_with_stdio(false);
	...
	return 0;
}

변수 초기화 문제

대회에서 한 번의 프로그램 실행으로 여러 test case에 대한 답 처리를 요구하는 경우가 많다. 이 경우 이전 입력에서 사용한 전역 변수 값을 꼭 초기화해야 한다. 같은 예제의 입력을 두 번 반복하면 우연히 정답이 되는 경우를 방지할 수 있다.

3. 디버깅과 테스팅

디버깅

대회에서는 디버거를 사용하는 것 보다 눈으로 디버깅 하는 것이 빠를 때가 많다. 애초에 가독성 있게 짜여진 코드는 눈검증이 쉽다.

 

단정문(assertion)을 사용하거나 프로그램 계산 중간 결과를 출력해 가며 오류의 범위를 좁히는 것이 도움이 된다. 런타임 오류의 경우는 디버거를 사용하는 편이 낫다.

테스트

예제 입력을 만들어 가능한 많이 테스트하는 것이 좋다. 주어진 예제 입력을 약간 바꾸고, 가장 작거나 큰 입력을 통해 검사하자.

4. 변수 범위의 이해

산술 오버플로우

컴퓨팅 시스템의 모든 변수는 담을 수 있는 크기가 제한되어 있다. 산술 오버플로는 계산값이 자료형의 표현 가능 범위를 벗어나는 경우이다.(값이 크거나 작아서 벗어나는 모든 경우를 오버플로우라 한다.)

대부분 언어들은 사칙연산 과정의 오버플로우를 경고하지 않는다. 프로그램의 논리 정확성에만 집중하면 산술 오버플로가 발생하기 쉽다.

너무 큰 결과

출력 결과가 32비트를 넘어가는데 64비트 정수를 사용하지 않는 경우 혹은 최종 결과가 64비트인데 중간 계산 값을 32비트 정수로 전달하는 경우.

너무 큰 중간 값

출력 값의 범위는 작지만 중간 과정에서 큰 값을 일시적으로 계산해야 하는 경우. 예를 들어 두 개의 32비트 부호 있는 정수 입력으로 최소공배수를 반환하는 함수는 다음과 같이 작성.

 

// lcm: 최소공배수, gcd: 최대공약수
// lcm(a, b) = a x b / gcd(a, b)
int lcm(int a, int b){
	return (a * b) / gcd(a, b);
}

 

a * b 는 32비트 정수형의 최대치를 넘길 가능성이 크다. 이 경우 c++는 경고 없이 32비트값 까지만을 취해서 연산을 진행한다.

너무 큰 '무한대' 값

임의로 '무한대'에 해당하는 값을 정의하는 경우가 있다. 32비트 부호있는 정수에서 2^31-1 이 최대 범위인데, 여기에 더해지는 값이 있다면 오버 플로우가 발생한다. 무한대 값을 선택할 때는 이 값들이 서로 더해지거나 곱해지는 경우가 없는지 확인해야 한다.

 

다음의 '무한대' 값을 사용하면 실수를 방지할 수 있다.

 

// 2^30에 가까운 큰 값이고 두 배해도 오버 플로우가 아님.
// 자릿수에 맞게 입력했는지 눈으로 확인이 쉽다.
const int inf = 987654321;

// 역시 충분히 크며 두 배해도 오버 플로우가 아니다.
// 반복 형태이므로 c++ 의 memset 으로 초기화가 용이.
const int inf = 0x3f3f3f3f;

오버플로 피해가기

기본적으로 더 큰 자료형 사용하면 오버 플로를 피할 수 있다.

 

int lcm(int a, int b){
	return (a * (long long)b) / gcd(a, b);
}

 

위의 최소공배수 함수에서 a 혹은 b 를 type casting 하면 a * b 의 결과가 프로모션되어 64비트 정수형으로 처리된다.

 

연산의 순서를 바꾸면 피해갈 수 있는 상황도 있다.

 

int lcm(int a, int b){
	return a * (b / gcd(a, b));
}

 

gcd(a, b) 는 a 와 b 모두의 약수이므로 둘 중 하나와 미리 나누어 오버 플로우 없이 연산되도록 한다.

 

문제에 따라 오버플로를 피해가는 계산 방법이 있을 수도 있는데, 이항 계수를 예로 들어 확인해보자. 다음은 이항 계수의 정의이다.

 

 

계산의 결과가 32비트 정수에 저장 가능하더라도 n! 이 너무 큰 수이기 때문에 계산 과정에서 오버플로가 일어나는 경우가 있다.

 

 

하지만 위와 같은 점화식을 사용하면 점화식에서의 중간 값은 항상 최종 결과와 같거나 작으므로 32 비트 정수형만을 가지고 계산 가능하다.

자료형의 프로모션

두 개의 피연산자를 사용하는 연산에서 피연산자들의 자료형이 다르거나 자료형 범위가 너무 작은 경우 컴파일러가 같은 자료형으로 변환한다.

 

c++ 의 자료형 프로모션은 다음과 같다.

 

 1. 정수와 실수 → 실수형으로 통일.

 2. 둘 다 정수형 or 둘 다 실수형 → 더 넓은 범위를 갖는 자료형으로 변환.

 3. 둘 다 int형보다 작은 정수형 → 양쪽 다 int형으로 변환.

 4. unsigned 정수와 signed 정수 → unsigned 정수형으로 변환. 많은

     프로모션 관련 오류들이 이로 인해 일어난다.

  

c++ 의 STL 에서 모든 컨테이너의 size()가 부호 없는 정수형 size_t 를 반환하는데, 만약 size()를 호출하는 배열 arr 가 비어있다면 arr.size()-1 은 오버플로로 2^32-1 이 된다.

5. 실수 자료형의 이해

실수 연산의 어려움

컴퓨터는 모든 정수를 정확히 표현하지만 실수는 무한히 이어지는 경우가 많아 정확한 표현이 힘들다. 메모리는 유한하고, 무한한 실수값을 정확히 담을 수 없으므로 적절히 근사된 값을 사용한다. 실제로 컴퓨터의 실수 변수는 정확도가 제한된 근사값을 저장한다.

IEEE 754 표준

가장 널리 사용되는 실수 표기 방식이고 이진수의 실수 표기, 부동 소수점 표기, 무한대, 비정규 수, NaN 등 특수한 값이 존재한다.

실수의 이진법 표기

소수점 밑 i 번째 자리의 크기는 (1/2)^i , 예를 들어 1011.101 = 11 + 1/2 + 1/8 = 11.625

부동 소수점 표기

실수를 이진법으로 표기할 때 사용 가능한 비트들을 정수부와 소수부에 어떻게 배분할 것인가? 이 문제를 위해 대부분 실수 표준에서는 소수점을 옮길 수 있도록 했다.

 

소수점 위에 한 자리만 남도록 하고 최상위 비트에서부터 표현 가능한 만큼 표시한 뒤 나머지는 반올림 처리. 소수점을 몇 칸 옮겼는지 기록하면 원래 값을 재구성 할 수 있다.

 

11.625 = 1011.101 → 1.011101 소수점 위 숫자는 항상 1 이므로 생략하여 1 비트를 절약한 뒤 남는 비트로 나머지를 표현한다. 예를 들어 5 비트가 사용 가능한 경우 01110 이 된다.

 

이때 실수 변수는 부호 비트(sign bit, 양수 음수 여부), 지수(exponent, 소수점을 몇 칸 옮겼는지), 가수(mantissa, 소수점을 옮긴 실수의 최상위 X비트) 정보를 저장한다.

 

32 비트 실수 → 부호 1, 지수 8, 가수 23

64 비트 실수 → 부호 1, 지수 11, 가수 52

 

지수보다 가수에 많은 비트가 부여된다. 지수는 소수점을 얼만큼 이동했는지 이므로 작은 지수로도 실생활의 숫자들을 표현하기에 무리가 없기 때문이다. 11비트의 지수로 최소 -1024, 최대 1023의 값을 표현할 수 있다.

 

실수 비교하기

실수는 근사적으로 표현되기 때문에 실수끼리의 비교는 부정확하다. 따라서 실수 값의 비교는 어느 정도의 오차를 염두에 두어야 한다. 실제 실수 값이 비교되는 방식은 두 값의 차이가 매우 작은 경우 두 값이 같다고 판단한다.

 

bool absoluteEqual(double a, double b){
	// 미리 정한 오차한도 1/10^10 보다 작게 차이나면 같다고 판단한다.
	// 이보다 미세한 차이가 필요한 프로그램에서는 당연히 사용할 수 없다.
	return fabs(a - b) < 1e-10; 
}

 

더 미세한 오차의 실수를 비교하려면 다음의 방법을 사용한다.

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

같다고 판단해야 할 큰 값 두 개를 비교하는 경우, |a - b| 의 최대치를 구한 뒤 더 큰 오차 한도 값을 사용한다. |a - b| 의 상한은 이 변수들의 최대 값의 1/10^10 ~ 1/10^12 정도.

 

64비트 실수는 최대 15자리가 저장된다. 어떤 값을 저장할 때 1/10^15 정도는 버려지고 이것이 누적되면 결과의 1/10^10 정도는 오차가 될 수 있다.

 

다르게 판단해야 하는 작은 값 두 개를 비교하는 경우, 다른 값으로 처리돼야할 두 값이 오차 때문에 가까워질 수 있다. 

 

원래의 오차는 |x - y| 인데 오차로 인해 더 작은 오차인 |a - b| 가 나왔다면 오차 한도가 |a - b| 보다 작아야 한다.  두 수가 얼마나 떨어져 있어야 다른 값인지에 대한 객관적 기준은 없다. 주어지는 입력에 대해 적당한 최대치와 최소치를 예측하여 오차 한도의 상한과 하한을 이끌어내 적당한 값을 취해야 한다.

 

적당한 오차 한도를 선택하는 것은 많은 경험이 필요하다. 이런 방법이 쉽지 않을 때는 일반적으로 다음의 방법을 사용한다.

상대 오차를 이용하기

두 숫자의 크기에 비해 그 차이가 작다면 두 수가 같다고 판정한다. 실질적인 오차 허용 범위는 a와 b가 커질수록 커진다. (19999와 20000의 상대 오차와 1.9999와 2의 상대 오차는 같다.)

 

bool relativeEqual(double a, double b){
	// a, b의 오차가 더 큰 수의 0.000001% 이하이면 true.
	return fabs(a - b) <= 1e-8 * max(fabs(a), fabs(b)); 
}

 

아주 작은 숫자들을 비교하려 할 때는 문제가 될 수 있다. x가 0이어야 하는데 오차로 0.000000000001이 된다면 relativeError(0,x) = x/x = 1 이 된다. 따라서, 두 수의 절대 차이가 매우 작은 경우 참을 반환하는 조건문을 추가한다.

 

bool 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 인 두 수가 오차로 인해 a가 약간 더 작은 값으로 계산되면 a<b는 참, a≤b는 거짓을 반환한다. 위 코드에서처럼 오차 한도를 설정해 두 값이 아주 가까운 경우를 먼저 처리한다.

정확한 사칙연산

실수 변수도 정확하게 저장할 수 있는 값은 항상 정확하게 저장된다. 가수부 안에 들어가는 정수(|±2^52| 보다 작은 모든 정수)는 실수 변수로 정확하게 표현 가능하다. 분모가 2의 거듭제곱인 유리수도 정확히 표현 가능하다. (e.g. 3.5, 43783/16384)

실수 연산 하지 않기

실수 연산을 하지 않으면 이 모든 고민을 할 필요가 없다! 많은 경우 문제를 적절히 변형해 실수 연산을 소거할 수 있다.

 

곱셈과 나눗셈 순서를 바꾸자. a / b * c 의 결과가 항상 정수라면 (a * c) / b 형태로 실수 연산을 피할 수 있다.(단, a * c에서 오버플로에 유의해야 한다.)

 

양변을 제곱하자. 정수 좌표의 두 점 (x1, y1), (x2, y2) 사이의 거리가 r 인지 확인할 때 r = sqrt(pow(x1 - x2)) + pow(y1 - y2)로 직접 r을 구하지 않고 양변을 제곱하여 r^2 이 나오는지 확인하면 실수 연산을 하지 않는다.

 

실수 좌표를 사용하는 기하 문제에서 좌표계를 가로 세로로 정수배 늘리면 정수만을 이용해 해결할 수 있다.