구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.
📕 목차
1. 코딩의 중요성
2. 좋은 코드를 짜기 위한 원칙
3. 자주 하는 실수
4. 디버깅과 테스팅
5. 변수 범위의 이해
6. 실수 자료형의 이해

1. 코딩의 중요성

 

사람들을 가르치다보면, 본인이 코테를 못하는 이유가 알고리즘과 자료 구조에 대한 지식이 부족해서라고 잘못 생각하는 사람들이 많다.

물론, 많이 안다는 것은 유용하고 때론 중요하고 강력한 알고리즘이 존재하긴 하지만, 과연 그게 가장 큰 문제라고 묻느냐면 난 아니라고 생각한다.

 

제 아무리 로직을 머리에 꿰고 있다고 해도 그것을 구현하는 "구현력"은 별개다.

그리고 구현 과정에 있어서, 어떤 식으로 코드를 작성하는지도 천차만별이고

같은 로직을 구현했음에도 누구는 해독 과정을 거쳐야 간신히 읽을 수 있지만, 누구는 잘 전개되는 책처럼 술술 읽히기도 한다.

 

좋은 성적을 내기 위해서는 빠르게 코드를 작성하는 것이 아니라 읽기 쉬운 코드를 작성해야 한다.

  • 복잡하고 읽기 어려운 코드는 디버깅이 힘들다
  • 한 번에 정확하게 작성하기도 어렵다
  • 다음 코드를 작성하기 위해서는 이전 코드를 참조해야 하는데, 코드가 지저분하면 시간을 많이 빼앗긴다

따라서 반복적인 연습을 거쳐 자신의 코드 스타일을 간결하고 일관되게 다듬으려 노력해야 한다.

 

2. 좋은 코드를 짜기 위한 원칙

 

• 간결한 코드 작성하기
• 적극적으로 코드 재사용하기
• 표준 라이브러리 공부하기
• 항상 같은 형태로 프로그램 작성하기
• 일관적이고 명료한 명명법 사용하기
• 모든 자료를 정규화해서 저장하기
• 코드와 데이터를 분리하기
📌 간결한 코드 작성하기
  • 코드가 짧을 수록 오타나 단순한 버그가 생길 우려가 줄어든다.
  • 일반적인 프로그램에서는 권장하지 않는 '흑마법'을 사용하면 유용한 경우도 있다.
    • 전역 변수의 남발 : 딱히 잃을 게 없다
    • C/C++ 매크로를 사용한 간결한 코드 작성

예를 들어, 아래처럼 정렬되지 않은 정수 배열에 중복 원소 판별 함수가 있다고 생각해보자.

bool hashDuplicate(const vector<int>& array) {
    for (int i=0; i<array.size(); ++i)
        for (int j=0; j<i; ++j)
            if (array[i] == array[j])
                return true;
    return false;
}

매크로를 사용하면 다음과 같이 바꿀 수 있다.

#define FOR(i,n) for(int i=0; i<n; ++i)
bool hashDuplicateMacro(const vector<int>& array) {
    FOR(i,array.size())
        FOR(j,i)
            if (array[i] == array[j])
                return true;
    return false;
}

프로그래밍 설계 원칙 관점에서는 발작을 일으킬 정도의 문법이지만, 적어도 프로그래밍 대회에서 작성하는 코드에서는 코드가 훨씬 짧아지기 때문에 유용하게 쓰일 수 있다.

 

📌 적극적으로 코드 재사용하기
  • 코드를 모듈화해라 : 같은 코드가 반복된다면 함수나 클래스로 분리하라
  • 시간이 없다고 해서 코드를 더 알기 쉽게 고치는 데 주저하지 마라
  • 프로그래밍 대회에서는 단일 책임 원칙을 엄격하게 지키지는 못한다. (입력 읽는 함수, 파싱하는 함수, 문제를 푸는 함수를 모두 구분하는 데는 현실적인 문제가 있다.)

 

📌 표준 라이브러리 공부하기
  • 큐, 스택과 같은 자료 구조, 정렬 등의 기초적 알고리즘을 직접 작성하는 것은 시간 낭비다.
  • 표준 라이브러리는 검증된 자료이므로 메모리 관리, 정당성 증명에 신경 쓸 필요가 없다.
  • 팀으로 참가하는 대회에서는 다른 팀원이 이해하기 쉬워진다.

 

📌 항상 같은 형태로 프로그램 작성하기
  • 같은 코드를 작성하는 더 좋은 방법에 꾸준히 고민할 필요는 있지만 실수의 원인이 될 수 있다.
  • 자주 작성하는 알고리즘이나 코드 등에 대해서는 한 번 검증된 코드를 작성하고 이것만을 꾸준히 사용할 필요가 있다.
  • 그래야 도구가 아니라 문제에 집중할 수 있다.

 

📌 일관적이고 명료한 명명법 사용하기
int a[30][30], i, j, p[100], k=0, l=-1;
  • 위 코드는 실무 뿐만 아니라, 프로그래밍 대회에서도 낙제감이다.
  • 모호하지 않은 변수명과 함수명을 사용하는 버릇을 들여라
  • 사용하는 언어의 표준 라이브러리 명명 규약을 익혀라
bool judge(int y, int x, int cy, int cx, int cr);

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

같은 함수라도 함수 이름만 바꾸면 훨씬 명료해진다.

 

📌 모든 자료를 정규화해서 저장하기
  • 같은 자료를 두 가지 형태로 저장하지 마라
    • 유리수를 표현하는 클래스라면, 입력받는 유리수를 항상 약분해 기약 분수로 표현하는 것이 좋다.
    • x축 양의 방향과 주어진 점 (x,y) 사이 각도를 계산할 때, -30도, 330도, 690도 중 한 가지 기준을 정해라
  • 같은 자료가 두 개 이상의 표현을 가지게 되면, 문자열 표현이나 해시 값이 달라지는 등의 미묘한 버그를 만든다.
  • 정규화는 프로그램이 자료를 입력받거나 계산하자마자 곧장 수행되어야 한다.

 

📌 코드와 데이터를 분리하기

날짜를 다루는 프로그램을 다루기 위해, 월을 영문 이름으로 출력해야 하는 경우를 생각해보자.

// 비효율적
string getMonthName(int month) {
    if (month == 1) return "January";
    else if (month == 2) return "February";
    ...
    else return "Invalid month";
}

// 효율적
const string monthNmae[] = {
    "January", "February", "March", "April", "May", "June", "July", "August",
    "September", "October", "November","December"
};

이 기법의 좋은 예는 BFS 처럼 vector값으로 움직이는 경우가 있다.

const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};

 

3. 자주 하는 실수

 

• 산술 오버플로
• 배열 범위 밖 원소 접근
• 일관되지 않은 범위 표현 방식 사용하기
• Off-by-one 오류
• 컴파일러가 잡아주지 못하는 상수 오타
• 스택 오버플로
• 다차원 배열 인덱스 순서 바꿔 쓰기
• 잘못된 비교 함수 작성
• 최소, 최대 예외 잘못 다루기
• 연산자 우선 순위 잘못 쓰기
• 너무 느린 입출력 방식 선택
• 변수 초기화 문제
📌 산술 오버플로
  • 가장 자주 등장하는 실수다. 이후에 별도로 다룬다.

 

📌 배열 범위 밖 원소 접근 : Out of Index
  • C/C++는 배열의 원소에 접근할 때 해당 인덱스가 배열 범위 안에 있는지 별도로 확인해주지 않는다.
  • 속도는 빠르지만 디버깅이 힘들어지는 특성이 있다.
  • 런타임에서 걸리면 그나마 찾기 쉽지만, 오류도 나지 않으면서 잘못 동작하는 경우가 있다.
  • "int array[10], t"라고 선언했을 때 우연히 메모리 상 연속해서 위치하게 되면, array[10] 위치에 값을 대입하면 t에 덮어씌워질 수도 있다.
  • 배열의 크기는 신중하게 고려하자.

 

📌 일관되지 않은 범위 표현 방식 사용하기
  • 대부분의 프로그래밍 언어는 반 열린 구간 [lo, hi)를 사용한다.
    • [2, 12] : 공집합을 직관적으로 표현할 방법이 없다.
    • (1, 13) : 0번 인덱스부터 시작하려면 음수를 써야해서 자연스럽지 않다.
  • 반복문 (i=0; i<n; ), C++ STL의 begin()/end(), Java의 SortedSet 범위 지정용 fromElement/toElement, 파이썬의 슬라이싱 a[4:8] → 모두 시작 구간은 포함하고 종료 구간은 포함하지 않는다.
  • 웬만하면 자체적으로 만들 때도 프로그래밍 언어가 지원하는 범위 표현 방식을 따르는 것이 효율적이다.

 

📌 Off-by-one 오류
  • 계산의 큰 줄기는 맞지만, 하나가 모자라거나 많아서 틀리는 모든 오류
    • 길이가 100m인 담장에 10m 간격으로 울타리 기둥을 세울 때 필요한 울타리는 10개가 아니라 11개
    • 정수 배열 A[i]에서 A[j]까지 합은 j-i가 아니라 j-i+1
  • 최소 입력이 주어졌을 때 코드가 어떻게 동작할지를 되새겨 보는 것이 좋다.
    • 담장 길이가 0m라도 기둥은 하나 세워야 한다
    • A[1]부터 A[1]까지 평균을 구할 때는 0이 아니라 1로 나누어야 한다.

 

📌 컴파일러가 잡아주지 못하는 상수 오타
  • 변수명이나 함수명 오타는 컴파일러가 잡아준다.
  • 상수를 잘못 기입한 것은 컴파일러가 잡지 못한다.
    • 출력값에 오타를 냈거나, 상수값인 100000007에서 0의 개수를 틀리는 경우
    • 64 bit 정수형에 들어갈 상수에 64 bit 지정을 해주지 않아 오버플로가 발생하는 경우
  • 자신이 사용하는 언어에서 상수 타입을 어떻게 지정하는지, 지정하지 않으면 어느 형태로 강제되는지 알아둬라.

 

📌 스택 오버플로
  • 재귀 호출의 깊이가 깊어져 콜 스택(call stack) 오버플로가 나는 경우가 빈번하다.
  • 스택 최대 크기는 컴파일이나 실행시 설정 가능하고, 언어나 아키텍처에 따라 매우 다르므로 대회 환경의 스택 허용량을 알아두어야 한다.
  • C++은 지역 변수로 선언한 배열, 클래스 인스턴스가 기본적으로 스택 메모리를 사용하므로 특히나 StackOverflow에 조심해야 한다.
  • 배열 등의 지역 변수를 스택에 잡으면 재귀 호출이 몇 번 없어도 곧장 스택 오버플로가 나기 쉽다.
  • 보통은 힙에 메모리를 할당하는 STL 컨테이너나 전역변수를 사용한다.

 

📌 다차원 배열 인덱스 순서 바꿔 쓰기
  • 프로그래밍 대회에선 4, 5차원 배열을 만드는 경우도 있다.
  • 가능한 한 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋다.

 

📌 잘못된 비교 함수 작성
  • < 연산자의 성질(strict weak ordering)
    • 비반사성(irreflexivity) : a<a는 항상 거짓
    • 비대칭성(asymmetry) : a<b가 참이면 b<a는 거짓
    • 전이성(transitivity) : a<b가 참이고 b<c가 참이면 a<c는 참
    • 상등 관계의 전이성(transitivity of equivalence) : a<b, b<a 모두 거짓이면 a와 b는 같다. (혹은, a=b=c)
// 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;
}
  • vector<IntegerSet>을 정렬하기 위한 위 코드는 문제가 없어 보이지만 {1}, {3,4}, {2}, {3}이 들어오면 에러 발생
  • 상등 관계 전이성 성질을 만족시키지 못한다.
    • 실제로는 {3}<{3,4}만 참이고 나머지는 전부 거짓이다.
    • 표준 라이브러리 상으로는 a<b, b<a가 모두 거짓이면 a=b이므로, {1}={3,4}라는 논리가 성립한다.
  • 이 문제를 해결하기 위해서는 완전히 같은 경우를 제외하고는 두 집합이 같다고 판단하지 않는 것이다.
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());
}
  • 사실 따지자면 크기 비교를 위해 진부분집합 확인은 의미가 없다. a가 b의 진부분집합이면 a 크기는 언제나 b보다 작으므로 크기순 정렬만으로 원하는 조건을 달성할 수 있다.
  • 자바 표준 라이브러리는 < 대신 <= 연산을 비교 함수 모델로 사용한다는 차이가 있다.

 

📌 최소, 최대 예외 잘못 다루기
  • 가장 작은 입력과 가장 큰 입력에 대해 동작할지를 생각해보면 생각보다 많은 오류를 잡을 수 있다.

 

📌 연산자 우선순위 잘못 쓰기
  • 시프트 연산자나 비트 단위 연산자를 섞어쓰는 경우 혼란을 야기한다.
  • 헷갈리면 괄호를 적절히 감싸버려라.

 

📌 너무 느린 입출력 방식 선택
  • C++의 cin, Java의 Scanner, Python의 input 등의 고수준 입력 방식은 간단하지만 속도 저하가 크다.
  • 입출력 양이 많은 경우 프로그래밍 언어에 맞게 빠른 방식을 찾아야 한다.

 

📌 변수 초기화 문제
  • 테스트 케이스가 여러개인 경우, 이전 입력의 전역 변수 값을 초기화하지 않아서 문제가 발생할 수 있다.
  • C/C++의 전역 변수나 다른 언어들의 멤버 변수들의 생성시 기본값 초기화에 의존하는 경우 문제가 발생할 수 있다.
  • 가끔 테스트 케이스에서 검증하지 못하는 경우가 있는데, 예제 입력 파일을 두 번 반복해서 실행하면 검증되는 경우가 있다.

 

4. 디버깅과 테스팅

 

📌 디버깅에 관하여
  • 디버거는 유용한 도구지만, 프로그래밍 대회에서는 유용성이 제한된다.
    • 대체로 소스 코드가 길지 않으므로, 눈으로 디버깅하는 것이 빠른 경우가 많다.
    • 재귀 호출, 중복 반복문을 많이 사용하면 디버거를 사용하기에 적합하지 않다.
    • ACM-ICPC의 경우 한 사람이 디버거를 켜고 컴퓨터를 점유하면, 다른 두 사람은 아무것도 못 한다.
  • 코드가 복잡하면 눈으로 검증하지 못하긴 하지만, 그건 코드를 복잡하게 짰다는 것이 문제다.
  • 다음과 같은 단계를 밟는 것이 좋다.
    • 작은 입력에 대해 제대로 실행되나 확인하기
    • 단정문(assertion)을 쓴다. : 거짓일 때, 프로그램을 강제 종료
    • 프로그램 계산 중간 결과를 출력한다.
  • 디버거를 사용하면 좋은 예는 스택 기록을 출력해주지 않고 런타임 에러가 발생한 경우에 해당한다.

 

📌 테스트에 관하여 
  • 제출 전에 예제 입력을 만들어 가능한 한 많이 프로그램을 테스트하는 것이 좋다.
  • 예시 입력값을 바꾸거나, 가장 작은/큰 입력을 만들어 봐라.
✒️ 스캐폴딩(scaffolding)

건물을 짓거나 보수할 때 공사하는 사람들이 걸어다니기 위해 설치하는 임시 구조물.
프로그래밍에서는 개발할 때 뼈대를 잡기 위한 임시 코드를 말한다.

• 코드 정당성을 확인하고 반례를 찾는데 유용하다
• 예제 입력은 다 맞는데 틀리는 경우, 소스 코드 상 문제를 찾을 수 없을 때 사용하면 좋다.
• 임의의 작은 입력을 자동으로 생성해 프로그램을 돌려보고, 그 답안을 검증하는 프로그램
// 테스트하고 싶은 함수
void mySort(vector<int> &array);
// 주어진 배열을 문자열로 바꿈
string toString(const vector<int> &array);

int main() {
    while (true) {
        int n = rand() % 100 + 1; // 임의의 입력 생성
        vector<int> input(n);

        for (int i = 0; i < n; ++i) input[i] = rand();

        // 두 개의 복제를 만들어서 하나는 정렬 함수, 하나는 표준 라이브러리로 정렬
        vector<int> mySorted = input;
        mySort(mySorted);
        vector<int> stdSorted = input;
        sort(stdSorted.begin(), stdSorted.end());

        if (mySorted != stdSorted) {
            cout << "Wrong Answer: " << endl;
            cout << "Input: " << toString(input) << endl;
            cout << "My Answer: " << toString(mySorted) << endl;
            cout << "Standard Answer: " << toString(stdSorted) << endl;
            break;
        }
    }
}
실제로 코드를 비교할 대상이 없는 경우가 더 많다.
이럴 때는 작은 입력에서만 동작하는 더 느리지만, 단순한 알고리즘을 사용해 검증해라.
큰 입력을 빨리 해결할 수 없어 제출은 불가능하지만 답을 검증하는데 있어서는 유용할 것이다.
자칫하면 코딩 시간을 빼앗길 수도 있으니 꼭 필요한 경우에만 사용하는 것이 좋다.

 

5. 변수 범위의 이해

 

• 산술 오버플로
• 너무 큰 결과
• 너무 큰 중간 값
• 너무 큰 '무한대' 값
• 오버플로 피해가기
• 자료형의 프로모션
📌 산술 오버플로
  • 컴퓨터 연산의 가장 대표적인 제한은 유한성이다.
  • 수학적/논리적으로 완전히 정당하더라도 구현했을 때 예상과 다르게 동작할 수 있다.
  • 대부분 프로그래밍 언어들은 사칙연산 과정에서 오버플로가 발생해도 별다른 경고를 해주지 않는다. (비효율적이라)
  • 프로그램 논리 정확성만 집중하면 산술 오버플로가 뒷통수를 후려칠 수도 있다.

 

📌 너무 큰 결과
  • 32비트 자료형 범위를 넘어가면 64비트 정수를 사용하거나, 큰 정수 구현을 이용해라
  • 당연하지만 많이 실수하는 내용이다.

 

📌 너무 큰 중간 값
  • 입력/출력값의 범위는 작지만 중간 과정에 큰 값을 일시적으로 계산하는 경우
  • signed int type의 두 개 정수의 최소공배수 반환을 생각해보라.  \( lcm(a,b)=\frac{a*b}{gcd(a,b)} \)
int gcd(int a, int b); // 두 수의 최대공약수 반환

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
  • lcm(50000, 100000)를 실행하면 중간값이 32bit 정수 범위를 넘어가 잘못된 결과인 14,100을 리턴한다.

 

📌 너무 큰 '무한대' 값
  • 변수를 초기화 할 때, 종종 해당 타입의 최대값을 할당하는 경우가 있다.
  • 이 방식의 문제점은 무한대 값들이 서로 더해지거나 곱해지는 경우가 생기면 오버플로가 발생한다.
  • int의 경우 2,147,483,647보다 987,654,321을 할당하는 것이 여러모로 낫다.

 

📌 오버플로 피해가기
  • 가장 간단한 방법은 더 큰 자료형을 사용하는 것이다.
int lcm(int a, int b) {
    return (a * (long long)b) / gcd(a, b);
}
  • 오버플로가 발생하지 않도록 연산의 순서를 바꾼다.
int lcm(int a, int b) {
    return a * (b / gcd(a, b));
}
  • 계산 방법 바꾸기 (ex. 이항 계수)
    • \(  \begin{pmatrix} n \\ r \end{pmatrix} = \frac{n!}{(n-r)!r!} \) → 그대로는 사용 불가
    •  \( \begin{pmatrix} n \\ r \end{pmatrix} = \begin{pmatrix} n-1 \\ r-1 \end{pmatrix} + \begin{pmatrix} n-1 \\ r \end{pmatrix} \) → 점화식 사용
    • 이항 계수 계산에서 중간 값은 항상 최종 결과와 같거나 더 작으므로 32bit 정수형으로 계산 가능

 

📌 자료형의 프로모션
  • 프로모션 : 피연산자 자료형이 다르거나 너무 작은 경우, 자동 형변환해서 계산하는 것
  • 가끔 알기 어려운 버그의 주역이 된다.
  • 프로모션 과정은 언어마다 다르다. C++의 경우 다음과 같다.
    • 정수형, 실수형 → 정수형이 실수형으로 변환
    • 양쪽 다 정수형 혹은 실수형 → 보다 넓은 범위를 갖는 자료형으로 변환
    • 양쪽 다 int형보다 작은 정수형 → 양쪽 다 int형으로 변환
    • 부호 없는 정수형과 부호 있는 정수형이 섞인 경우 → 부호 없는 정수형으로 변환
  • 대개 부호 있는 정수와 부호 없는 정수형이 섞였을 때 자주 문제가 발생한다.
int main() {
    unsigned char a = 17;
    short b = -18;
    int c = 2;
    unsigned int d = 0;
    cout << (a + b) * c + d << endl; // -2가 출력이 안 된다!
}

노션으로 다이어그램 만드는데 [] 안에 () 안 되길래 ``로 대체..

가장 마지막에 d를 더하면서 전체 수식이 부호 없는 정수형으로 변환되어, -2가 담길 수 없으므로 언더 플로우가 발생한다.

bool isSorted(const vector<int> &seq) {
    for (int i=0; i<seq.size()-1; ++i)
        if (seq[i] > seq[i+1])
            return false;
    return true;
}

위의 예제도 에러가 발생한다.

STL에선 모든 컨테이너의 size()가 부호 없는 정수형인 size_t를 반환한다.

만약 seq가 비어있는 배열이라면 seq.size()-1은 언더플로로 인해 2^32-1이 되어 버린다.

따라서 seq[]가 비어 있는 경우를 처음부터 예외 처리하거나, seq.size()를 int형으로 변환하거나, seq[i-1]>seq[i]를 확인하도록 반복 초기값을 바꾸어야 한다.

 

6. 실수 자료형의 이해

 

• 실수 연산의 어려움
• 실수와 근사값
• IEEE 754 표준
• 실수의 이진법 표기
• 부동 소수점 표기
• 실수 비교하기
• 하나. 비교할 실수 크기들에 비례한 오차 한도를 정한다
• 둘. 상대 오차를 이용한다
• 대소비교
• 정확한 사칙연산
• 코드의 수치적 안정성 파악하기
• 실수 연산 아예 하지 않기
📌 실수 연산의 어려움
// [1, n] 범위의 자연수 x에 대해 x*1.0/x == 1인 x의 수를 센다
int countObvious(int n) {
    int same = 0;
    for(int x=1; x<=n; ++x) {
        double y = 1.0 / x;
        if (y * x == 1.0)
            ++same;
    }
    return same;
}
  • 항상 성립해야 할 식이 제대로 된 결과를 내놓지 않는다.
  • 이를 이해하려면 컴퓨터가 사용하는 실수 표현 방식을 알아야 한다.

 

📌 실수와 근사값
  • 컴퓨터는 무한대의 수를 셀 수 없다.
  • 따라서 컴퓨터의 모든 실수 변수는 정확도가 제한된 근사값을 저장한다.
  • 실수의 계산은 순서와, 컴파일러 최적화, 중간에 로그 메시지를 출력하는지에 따라 답이 달라질 수 있다.

 

📌 IEEE 754 표준
  • 이진수로 실수를 표기
  • 부동 소수점(floating-point) 표기법
  • 무한대, 비정규 수(subnormal number), NaN(Not a Number: 숫자 아님) 등의 특수한 값 존재

 

📌 실수의 이진법 표기
  • 소수점 밑 i번째 자리의 크기는 \( \frac{1}{2^{i}} \)가 된다.
  • 1011.101(2)의 경우
    • 정수부(1011): \( 2^{3} + 2^{1} + 2^{0} = 11 \) 
    • 실수부(101): \( 2^{-1} + 2^{-3} = 0.625 \)
    • 십진수 표기는 11.625(10)이 된다.

 

📌 부동(浮動) 소수점 표기

  • 고정 소수점 표기는 이해하기 쉽지만, 모두를 만족시킬 수 있는 분할이 존재하지 않는다.
  • 부동 소수점 정보
    • 부호 비트(sign bit) : 양수인지 음수인지
    • 지수(exponent) : 소수점을 몇 칸 옮겼는지
    • 가수(mantissa) : 소수점을 옮긴 실수의 최상위 X 비트

  • IEEE에서 sign, mantisa, exp bit 표준을 제시했다.
  • 정확도에 큰 의미가 없는 경우를 제외하면, 64비트 실수형 이상을 쓰는 것이 좋다.

 

📌 실수 비교하기

위의 예제를 다시 살펴보자.

// [1, n] 범위의 자연수 x에 대해 x*1.0/x == 1인 x의 수를 센다
int countObvious(int n) {
    int same = 0;
    for(int x=1; x<=n; ++x) {
        double y = 1.0 / x;
        if (y * x == 1.0)
            ++same;
    }
    return same;
}
  1. countObvious()가 \(\frac{1}{10}*3\)과 \(\frac{3}{10}\)을 비교하는 상황 가정
  2. IEEE에서는 \(\frac{3}{10}\)을 담은 실수 변수는 참 값보다 작은 값으로 근사된다.
  3. \(\frac{1}{10}\)은 참값보다 약간 큰 값으로 근사된다. 따라서 3을 곱하면 (2)결과보다 약간 커진다.
  4. 따라서 둘의 값에 오차가 발생하므로 비교에 실패한다.

 

차이가 매우 작은 두 수가 같은지 비교하는 함수는 아래처럼 구현할 수 있다.

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

적어도 countObvious()에서 두 수를 비교할 때 absoluteEqual()을 사용하면, 너무 작은 수치의 오차로 인해 false가 반환되어 틀리진 않을 수 있다.

하지만 여전히 안전하지는 않다.

  • \( \frac{10^{20}}{x}*x \)과 \( 10^{20} \)을 비교할 때, x가 50이하일 경우에 \(10^{20}\)은 x로 나눈 후에도 굉장히 크다.
  • 따라서 이 수에 x를 곱했을 때 얻어지는 오차는 \(\frac{1}{10^{10}}\)보다 크다.
  • absoluteEqual() 또한 안전하지 않다.

이 문제를 해결하기 위한 두 가지 방법이 존재한다.

 

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

대부분의 경우 코드가 다루는 값의 범위를 예측할 수 있다.

  1. 같다고 판단해야 할 큰 값 두 개를 비교할 경우
    • a와 b 값 모두 x라는 결과가 나와야 하는 경우, 오차 한도 값은 언제나 |a-b|보다 커야 한다.
    • |a-b| 상한을 가늠하는 방법은 해당 변수들이 가질 수 있는 최대값의 \(\frac{1}{10^{10}}~\frac{1}{10^{12}}\) 정도를 취한다
    • 64bit 실수형은 최대 15자리를 저장 가능하므로, 어떤 값을 저장할 때 \(\frac{1}{10^{15}}\) 정도는 버려진다.
    • 해당 오류가 누적된다면 결과는 \( \frac{1}{10^{10}} \) 정도는 오차가 될 수 있다.
  2. 다르게 판단해야 하는 작은 값 두 개를 비교하는 경우
    • x가 나와야 하는 수식과 y가 나와야 하는 수식에서 a, b가 나온 경우, |a-b|는 |x-y|보다 작을 수 있다.
    • 이를 다르다고 판정하려면 |a-b|보다 오차 한도가 항상 작아야 한다.
    • 여기엔 객관적인 기준이 없으므로, 상황에 따라 잘 판단해라

 

📌 둘. 상대 오차를 이용한다
// a와 b의 상대 오차가 1e-8 이하이면 같은 수로 취급한다
bool relativeEqual(double a, double b) {
    return fabs(a-b) <= 1e-8 * max(fabs(a), fabs(b));
}
  • 두 숫자의 크기에 비해 그 차이가 작다면 두 수가 같다고 판정하는 식: \(relativeError(a, b) = \frac{|a-b|}{max(|a|, |b|)}\)
  • 매우 작은 숫자들을 비교하려 할 때 문제가 발생할 수 있다.
bool doubleEqual(double a, double b) {
    double diff = fabs(a-b);
    // 절대 오차가 허용 범위 안일 경우 무조건 true, 아니라면 상대 오차를 검사한다
    return (diff < 1e-10) ? true : (diff <= 1e-8 * max(fabs(a), fabs(b)));
}

절대 오차 확인은 0에 매우 가까운 수들을 처리한 것이므로, 허용 오차를 좀 더 작게 잡을 필요가 있다.

 

📌 대소 비교
  • 같아야 하는 결과가 약간의 오차로 틀릴 수도 있다.
  • 항상 두 값이 아주 가까운 경우를 먼저 확인하고 처리해야 한다.

 

📌 정확한 사칙연산
  • 실수 변수라도 정확하게 표현할 수 있는 값은 항상 정확한 연산이 가능하다.

 

📌 코드의 수치적 안정성 파악하기
  • 수치적으로 안정적인 코드에서는 실수의 정확도 문제를 고려하지 않아도 된다.
  • 수치적 안정(numerically stable)이란 프로그램의 실행 과정에서 발생하는 오차가 더 커지지 않는 것이다.
  • 수치적 안정적인 프로그램은 중간에 작은 연산 오차가 발생하도, 최종 답은 아주 작은 오차만 갖는다.

 

📌 실수 연산 아예 하지 않기
  • 의외로 많은 경우에 적절한 변형을 가해 실수 연산을 없앨 수 있다.
    • ex1. 곱셈과 나눗셈 순서 바꾸기
    • ex2. 양변 제곱하기
    • ex3. 실수 좌표를 써야하는 기하 문제에서 좌표계를 가로 세로로 정수배 늘리기

 

저작자표시 비영리

티스토리툴바