백준 1312번 "소수"

백준 1312번

• 1312번 문제는 처음에 풀이방법을 완전히 잘못잡아 한참 헤맸던 문제이다. 

 

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

1312번: 소수

 

맨 처음으로 작성한 코드

let fs = require('fs');
let input = fs.readFileSync('./input.txt').toString().split(' ');

let num = Number(input[0]) / Number(input[1]);
let target = Number(input[2]);

let left = Math.floor(num * Math.pow(10,target));
let right = Math.floor(num * Math.pow(10, target-1));


let result = Math.floor(left - right*10);
console.log(result);

 

처음엔 이 문제가 굉장히 쉽다고 생각했다. 내가 생각한 문제의 풀이방법은 아래와 같다.

 

입력이 25 7 5 일경우

25 / 7 = 3.571428571428571 

이때 5번째 소수점을 구해야하는것이므로 한 변수는 10^5를 곱하고 나머지 한변수에는 그보다 하나 낮은 10^4를 곱하여

 

357142 - (35714 * 10) 의 형태를 만들어서 계산하면 원하는 답인 2가 나온다.

 

 

하지만 위 방법으로 수많은 반례를 마주했다. 이 문제는 부동소수점으로부터 시작된다. 위 방법에대한 반례는 아래와 같다.

 

입력이 1 3 19 일경우

1 / 3 = 0.3333333333333333 이라는 무한 소수가 생성된다. 

이때 위 방법대로 계산하게 되면 3 이 아닌 0이라는 값을 얻게된다. 

이는 컴퓨터가 계산하면서 미세한 오차가 발생하기 때문이다.

하나의 예시로 계산하는 중간과정에서 left와 right의 값을 출력해보면 아래와 같은 상태가된다.

결과값

 

즉, 위 풀이방법과 같이 한번에 나눠서 계산을 하고자 하면 넘치는 무한소수로인해 제대로된 데이터를 얻어낼 수 없게된다. 풀이방법이 처음부터 틀렸다는것을 모르고 많은 시간을 저 방대한 양의 데이터를 어떻게 처리할지 고민했다..

 

 

 

정답으로 제출한 코드

• 문제 해결방안의 핵심 키는 나머지연산에 있다. 한번에 나누는것이 아닌 하나씩 차례대로 갉아먹는 느낌으로 처리하는 것이다. 우리가 높은 수의 나눗셈을 수기로 계산한다고 생각해보자. 우리는 10자리를 구하고 그 나머지를 나누어 1의자리를 구하고,또 그것을 나누어 첫번째 소수를 구하고,또 반복하며 2번째,3번째 소수 등등 순차적으로 구해나간다. 그것이 이 문제 풀이법의 핵심이다. 아래는 필자가 작성한 정답코드이다.

let fs = require('fs');
let input = fs.readFileSync('./input.txt').toString().split(' ');

let target = Number(input[2]);
let left = Number(input[0]);
let right = Number(input[1]);
let result = left;

for(let i = 0; i < target; i++){
    result %= right;
    result *= 10;    
}

console.log(Math.floor(((result/10)/right)*10));

 

정답!

 

 

하나의 예시를 잡고 천천히 코드를 따라가보자. 

아까의 반례였던 1 3 19를 예시로 들겠다.

 

1 % 3 = 1이다.

여기서 몫은 0 나머지가 1인것이다.

우린 1의자리의 숫자를 구한것이다. 이제 소수점 첫번째자리를 구하려면 *10을 해준뒤 다시 나누어주면된다.

 

10 % 3 = 1

몫은 3, 나머지는 1

이때 소수점 첫번째 자리가 3인것이다. 이 작업을 총 19번 반복해주면 된다.

 

19번의 반복이 끝나면 이제 우리는 나머지가 아닌 몫을 구해주면된다.

하지만 필자는 반복문에서 *10을 한채 마무리되기떄문에 19번의 반복이 끝났을때  result의 값이 10이된다.

따라서 이를 10을 다시 나눠준뒤 3과 나누어주면 0.333333.. 이 될것이다. 이때 소수점 첫번째 자리가 19번째 소수이므로 *10을 해주고 Math.floor를 사용하여 나머지 소수를 버려주면 우리가 원하는 값을 얻을 수 있다.

 

 

느낀점

• 해당 문제를 풀면서 방향을 잘못잡았다는걸 몰랐을때 많이 당황스러웠고 어떤 방법을 써도 항상 데이터의 오차로인한 문제가 발생하는걸 막을 수 없었다. 그래서 부동소수점에대한 많은 구글링을 하는 도중에 toFixed() 를 사용해도 100번째 소수점까지 밖에 처리를 못한다는것을 알았을때 무언가 잘못되었다는걸 알았다. 찾아야되는 물건이 들어있는 박스를 한번에 뒤집어놓고 그안에서 물건을 찾으려 했다는걸 알았고 하나씩 천천히 꺼내면서 찾아보면 어떨까 하는 생각이 들었다. 그 결과 데이터의 오차는 없었고 보다 깔끔한 코딩을 할 수 있었다. 이 문제로부터 데이터를 처리하는 순서에대한 중요성을 알게된거 같다.