문제 url:
알고리즘 수업 - 알고리즘의 수행 시간 5
문제:
🐱👤 실제 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
System.out.println(n * n * n);
System.out.println(3);
}
}
해당 문제는 for문이 3중으로 되어 있는 형태이다. for문은 O(N)의 시간 복잡도를 가지는데, 이것이 3중으로 되어 있다면 O(N ^ 3)의 시간 복잡도를 가질 것이다.
MenOfPassion의 알고리즘을 봤을 때 모든 for문이 1부터 n까지의 범위를 반복한다고 한다. 즉, n ^ 3만큼 연산을 한다고 볼 수 있어 n n n으로 계산하였다.
🤢 Math.pow()의 한계
정말.. 열심히 적었는데, 출간 직전에 벨로그가 터져서 세이브가 되지 않았다..
다시 적으려고 하니.. 내용이 이전보다 많이 간소화 됐을 것이다.
먼저, 초기 코드를 보여주면
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
System.out.println((long) Math.pow(n, 3));
System.out.println(3);
}
}
해당 코드로 제출하니, 틀렸다고 한다. 분명 맞게했는데
그래서 찾아보니 아래와 같은 답글을 찾을 수 있었다.
Math.pow는 double형으로 계산하고 리턴하는데, 너무 큰 long 숫자는 double 형으로 표현시 오차범위가 존재합니다. 따라 정확하게 계산되지 못하는 것입니다.
java 의 double 형은 부동소수점 방식을 사용하기에, 부동소수점에 대해 공부하는 것이 좋아 보입니다.
이것이 무슨말인지 챗GPT한테 물어보니, 아래와 같은 답변을 주었다.
아하!. 부동 소수점 방식을 사용하기 때문에 long값이 표현될 때 오차가 발생하여 정확성이 떨어질 수 있어 틀렸다는 걸 알 수 있다.
그렇다면 왜 오차가 발생하는 걸까? 이전에 정리 잘해놨는데 이게 왜 날라가
조금 간단하게 설명하겠다.
9.123456과 같이 유한 소수가 존재한다고 보자. 값으로는 떨어지는 숫자이지만,
이를 2진수로 변환하면 무한 소수가 되는 경우가 존재한다.타 블로그를 참조하여 예시를 가져오면
10진수: 9.1234567
2진수: 1001.000111111001101011011011...
정규화: 1.001000111111001101011011011...
해당 10진수를 2진수로 변환하면 이렇게 무한소수가 되버리고, 이러한 무한소수는 double로도 다 담지 못해 결국 범위까지만 저장되게 된다.이렇게 되면, 값이 짤리게 되면서 오차가 발생하는 것이다.
왜 해당 문제에서 Math.pow() 메서드를 사용하면 틀리는지를 간단하게 살펴보았고,
실수형 데이터 타입을 다룰 때 유의해서 사용해야 한다는 점을 살펴보았다.
💜 참고자료
