LeetCode 문제 1232

"Check If It Is a Straight Line,"는 주어진 좌표들이 모두 직선 상에 있는지 확인하는 문제입니다.

문제 설명:

주어진 n개의 점이 직선 상에 있는지 확인하는 함수 checkStraightLine을 구현하세요. 주어진 점들이 직선에 위치하면 true, 그렇지 않으면 false를 반환합니다.

 

Dart 코드:

class Solution {
  bool checkStraightLine(List<List<int>> coordinates) {
    // 첫번째 점과 두번째 점의 기울기를 계산 해봄 (y2 -y1 / x2 - x1)
    int x1 = coordinates[0][0], y1 = coordinates[0][1];
    int x2 = coordinates[1][0], y2 = coordinates[1][1];

    // 기울기를 계산하는 대신, 두점사이의 차이를 비교하여 나누기 연산을 피할수 있을껄...?
    int dx = x2 - x1; // x차이
    int dy = y2 - y1; // y차이

    // 나머지 점들에 대해 기울기를 비교..
    // 점들을 순차적으로 확인하면서 직선상에 있는지 검사하는 거임
    for (int i = 2; i < coordinates.length; i++) {
        int x = coordinates[i][0], y = coordinates[i][1];

        // 현재 점과 첫번째 두점의 기울기가 동일한지 확인(기울기 비교는 cross product 사용)
        int dx2 = x - x1; // 현재 점과 첫번째 점의 x 차이
        int dy2 = y - y1; // 현재 점과 두번째 점의 y 차이

        // 기울기 비교
        //(dy/dx == dy2/dx2)이니까 cross product로 비교 (dy * dx2 == dy2 * dx)
        if (dy * dx2 != dy2 * dx) {
            return false; // 기울기가 다르면 직선 상에 있지 않음
        }
    }

    // 모든점이 직선 상에 있다면 true를 다시 돌려 받을거임
    return true;
  }

  void main() {
    List<List<int>> coordinates = [
        [1, 2],
        [2, 3],
        [3, 4],
        [4, 5],
        [5, 6],
        [6, 7]
    ];

    print(checkStraightLine(coordinates));; // true 출력
  }
}
//문제: 주어진 2D 좌표리스트가 하나의 직선위에 있는지 확인하는 문제여
// 두 개의 점이 있으면, 이 두점은 항상 직선 위에 있겠네
// 교차 곱셈을 활용하라는데 그게무슨 개소리임
// 아 그러니까 두 기울기가 동일한지 확인 할때 나누기를 피하기 위해 교차곱을 사용하는구만
// 나누기를 사용하는 부동소수점 방식은 넓은 범위를 표현하기 좋지만, 항상 오차가 생긴다는 단점을 가지고 있다

 

설명:

1. 기울기 계산 (dy/dx): 첫 번째 두 점 사이의 기울기 (dy/dx)를 구한 후, 나머지 점들이 같은 기울기를 가지는지 확인합니다.
2. 교차 곱 사용: 두 기울기가 동일한지 확인할 때 나누기를 피하기 위해 교차 곱 (dy * dx2 == dy2 * dx)를 사용하여 비교합니다. 이는 나누기 연산으로 인한 부동소수점 오류를 피할 수 있습니다.
3. for 루프: 점들을 순차적으로 확인하면서 직선 상에 있는지 검사합니다.

추가 설명:

부동소수점의 오류는 과연 무엇일까 에 대해서 설명하기 전에 부동소수점의 방식에 대해서 설명할께요.

 

부동소수점(floating point)이란 

실수는 보통 정수부와 소수부로 나누지만, 가수부와 지수부로 나누어 표현할 수도 있다.

부동 소수점 방식은 실수를 a*2^b 형식으로 저장한다.

이때 a는 1보다 크거나 같고, 2보다 작은 실수이다.

±(1.가수부)×2^지수부-127

앞서 살펴본 고정 소수점 방식은 제한된 자릿수로 인해 표현할 수 있는 범위가 매우 작다. 하지만, 부동 소수점 방식은 위의 수식을 이용하여 매우 큰 실수까지도 표현할 수 있다.

현재 대부분의 시스템에서는 부동 소수점 방식으로 실수를 표현할 수 있다.

64비트 CPU의 double형 실수를 IEEE 부동 소수점 방식으로 표현하면 위와 같다.

지수부는 자릿수(크기)를 나타내는 부분이다. 즉 가수의 어디쯤에 소수점이 있는지 나타낸다.

가수부는 실수의 실제 값을 표현하는 부분이다.

 

부동 소수점 방식 오차

부동 소수점 방식은 고정 소수점 방식보다 훨씬 더 많은 범위까지 표현할 수 있지만, 항상 오차가 존재한다는 단점을 가지고 있다.

부동 소수점 방식에서 오차는 위에서 살펴본 공식에 의해 발생한다.

해당 공식을 사용하면 표현할 수 있는 범위는 늘지만, 10진수를 정확하게 표현할 수는 없다. (무한소수, 순환소수의 경우 가수부가 표현할 수 있는 비트 수를 넘어가게 되면 손실되는 부분이 생기기 때문, 실수 또한 이진수로 표현하기 때문에 가수부가 1/2^n 꼴로 표현되는 경우만 오차없이 정확하게 값이 계산된다.)

부동 소수점 방식 실수 표현할 때 발생하는 오차

double num = 0.1;

for(int i = 0; i < 1000; i++) {

    num += 0.1;

}

System.out.print(num);
실행결과

100.09999999999859

위의 예제에서 0.1을 1000번 더한 합계는 100이 되어야하지만, 실제로는 100.09999999999859가 출력된다.

이처럼 컴퓨터에서 실수를 가지고 수행하는 모든 연산에는 언제나 작은 오차가 존재하게 된다. 이것은 자바뿐만 아니라, 모든 프로그래밍 언어에서 발생하는 기본적인 문제이다.