[Java] 부동소수점 오차를 피하자!

백준에서 시뮬레이션 문제를 풀다가 한참을 디버깅하면서 삽질했던 과정을 기록하고자 합니다..

 

결론부터 말씀드리자면, double 자료형의 부동소수점 오차로 인한 문제였습니다.

추가로 짝수/홀수 구분을 (2&1)로 해야하는데 (2^1)로 하고서는 "왜맞틀"했던 저를 발견할 수 있었습니다..

(반성하고 자바의 정석 다시 펼칠게요)

 

🔗 문제

https://www.acmicpc.net/problem/20057

문제는 삼성 기출로 유명한 마법사 상어 시리즈입니다.

 

📝 풀이

간단하게 풀이를 설명하자면 달팽이 회전 로직을 구현 후 각 방향에 따른 '위치 및 비율'을 인덱싱하여 구현했습니다.

2차원 격자 문제를 많이 풀어봤다면 쉽게 떠올리고 풀 수 있을거라 생각합니다.

 

조심해야하는 부분은 오른쪽부터 시작하는 달팽이 회전이 아니기에 마지막에 추가적으로 한번 더 왼쪽 회전을 진행해야 한다는 점입니다.

 

소스코드도 함께 첨부하겠습니다.

🔎 소스코드(정답)

import java.io.*;
import java.util.*;

//BOJ_20057
public class Main {
    static int n, res;
    static int[][] map;
    static int[] dx = new int[]{0,1,0,-1};
    static int[] dy = new int[]{-1,0,1,0};
    static int[] edgeX = new int[]{1,-1,-1,1};
    static int[] edgeY = new int[]{-1,-1,1,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        map = new int[n][n];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //달팽이 회전
        int x = n/2, y = n/2;   //중심점
        int step = 1;

        while(step < n) {
            //왼쪽 회전
            for(int i=0; i<step; i++) {
                y--;
                //로직
                tornado(x,y,0);
            }

            //아래쪽 회전
            for(int i=0; i<step; i++) {
                x++;
                //로직
                tornado(x,y,1);
            }

            step++;
            //오른쪽 회전
            for(int i=0; i<step; i++) {
                y++;
                //로직
                tornado(x,y,2);
            }

            //위쪽 회전
            for(int i=0; i<step; i++) {
                x--;
                //로직
                tornado(x,y,3);
            }

            step++;
        }

        //왼쪽 회전 -> 0,0에서 멈추도록
        for(int i=0; i<step-1; i++) {
            y--;
            //로직
            tornado(x,y,0);
        }

        System.out.println(res);

    }

    static int[] rate = new int[]{7, 2};
    static int[] edgeRate = new int[]{10,10,1,1};
    static void tornado(int x, int y, int d) {
        int dust = map[x][y];  // 현재 모래의 절대 양
        int remain = map[x][y];  // a자리에 들어갈 나머지 양

        //진행 방향 기준 오른쪽 비율 계산
        int dist = (d+3) % 4;
        for(int i=1; i<=2; i++) {
            int nx = x + dx[dist] * i;
            int ny = y + dy[dist] * i;
            int cnt = (dust * rate[i-1])/100; //cnt : 이동하는 모래 값

            remain -= cnt;
            if(isRange(nx,ny)) {  //범위 밖
                res += cnt;
                continue;
            }
            map[nx][ny] += cnt;
        }

        //진행 방향 기준 왼쪽 비율 계산
        dist = (d+1) % 4;
        for(int i=1; i<=2; i++) {
            int nx = x + dx[dist] * i;
            int ny = y + dy[dist] * i;
            int cnt = (dust * rate[i-1])/100;

            remain -= cnt;
            if(isRange(nx,ny)) {
                res += cnt;
                continue;
            }
            map[nx][ny] += cnt;
        }

        //진행 방향 기준 대각선 계산
        dist = d % 2 == 0 ? d : (d+2) % 4;  //짝수 : 인덱스 그대로, 홀수 : +2

        for(int i=0; i<4; i++) {
            int nx = x + edgeX[(dist + i) % 4];
            int ny = y + edgeY[(dist + i) % 4];
            int cnt = (dust * edgeRate[i])/100;
            
            remain -= cnt;
            if(isRange(nx,ny)) {
                res += cnt;
                continue;
            }
            map[nx][ny] += cnt;
        }

        //진행 방향 기준 직진(2칸) 계산
        int nx = x + (dx[d]*2);
        int ny = y + (dy[d]*2);

        int cnt = (dust * 5)/100;

        remain -= cnt;
        if(isRange(nx,ny)) {
            res += cnt;
        }
        else {
            map[nx][ny] += cnt;
        }

        //알파 자리
        nx = x + dx[d];
        ny = y + dy[d];

        if(isRange(nx,ny)) {
            res += remain;
        }
        else {
            map[nx][ny] += remain;
        }

        map[x][y] = 0;
    }

    //범위 밖 = true
    static boolean isRange(int x, int y) {
        return x<0 || y<0 || x>=n || y>=n;
    }
}

 

위 코드는 정답코드로 수정 후 코드입니다.

소스코드를 보면 아래처럼 비율을 구하는 로직이 곳곳에 포함되어 있습니다.

int cnt = (dust * rate[i-1])/100;

 

처음에는 이 부분을 dust * 0.07과 같이 double 자료형을 사용하여 구현했었는데요.

 

예제 절반은 맞고 절반은 틀리더라구요. 그래서 한참을 찾던 중 '혹시?'하는 생각에 로직을 위와 같이 바꿨더니 맞출 수 있었습니다.

 

오늘은 이 double 자료형의 사용에 있어 조심해야하는 부분인 '부동소수점 오차'에 대해 추가적으로 정리해볼까합니다.

 

❓부동소수점 오차

컴퓨터에서 double 자료형은 정확한 소수가 아닌 근사값으로 저장됩니다.

따라서 곱 연산의 결과가 기대하는 값과 미세하게 다를 수 있고, (int)로 변환하면서 예상과 다른 값이 나올 수 있습니다.

이 사실을 모른다면 웬만해선 기대값이 나오기에 디버깅이 어려운 부분이 아닐까 생각합니다.

 

✅ 그렇다면 이러한 오차는 왜 발생할까?

컴퓨터는 실수를 이진수로 표현할 때 근사 오차를 발생시킬 수 있습니다.

다들 알고있듯, 컴퓨터는 모든 수를 0또는 1로만 표현을 하는데요. 10진수 소수 중 상당수는 이러한 이진수로 정확히 표현되지 않는 경우가 많습니다.

 

실제로 이러한 실수들은 부동소수점(Floating Point)의 형태로 저장됩니다.

IEEE 754표준에 의해 (−1)S×M×2E 이러한 형태로 저장이 됩니다.

각 변수들은 다음과 같습니다.

 

• S (Sign, 1비트): 부호 비트 (0이면 양수, 1이면 음수)
• M (Mantissa, 52비트): 가수부 (유효숫자)
• E (Exponent, 11비트): 지수부 (2의 몇 제곱인지 나타냄)

예로 0.1을 이진수로 변환하게 된다면 다음과 같은 무한소수가 됩니다.

0.1 (10진수) = 0.0001100110011001100110011001100110011... (2진수, 무한 반복)

 

컴퓨터는 이러한 값을 가수부에 맞춰 근사값으로 저장하게되며, 이 과정에서 반올림 오차가 발생합니다.

 

한번 예시를 보는게 이해가 편할거라 생각합니다.

public class Main {
    public static void main(String[] args) {
        double a = 0.1;
        double b = 0.2;
        System.out.println(a + b);  // 0.30000000000000004
    }
}

위 코드의 기대값은 0.3임에도 불구하고 결과는 주석과 같이 나오게 됩니다. (0.1과 0.2가 정확하게 표현되지 않기 때문)

 

이번 문제에서 주어지는 비율은 10%, 7%, 5%, 2%, 1%로 전부 정확하게 표현되지 않는 수는 아닙니다.

분모가 2의 거듭제곱으로 나누어 떨어지는 경우에는 정확하게 표현이 되기에 부동소수점 오차의 문제가 될 수 있는 비율은 5%와 7% 두개입니다.

 

실제로도 7% 부분에서 오차가 생겨 잘못된 값이 나오는 경우를 디버깅에서 확인할 수 있었어요.

 

이러한 실수는 두번하지 않는게 좋아보이는 기초적인 부분이였던 것 같습니다. (무려 2시간이나 쏟고 찾음...)

헉