안녕하세요, 반례 찾았습니다.

(파이썬 랜덤 모듈로 임의로 만든 반례라 데이터가 깔끔하지 않은점 양해 부탁 드립니다)

참고로, 제가 반례 가지고 분석해 봤는데요,

로직은 맞는거 같은데

44번째 줄에서 기울기 구하는 과정에서

기울기가 소숫점이 되면서

정밀도 오류가 생긴 것 같습니다.

(예를 들어, 아래 반례는 위 코드에서 70 ~ 74번째 줄의 케이스에 걸리는데요,

a 값과 b의 값을 구해보았더니

a : 17187.285714285714, b : 17187.285714285717 이렇게 나왔습니다.

하지만 사실 둘 다 y절편이 같습니다. 즉, 같은 직선 위에 있는 점들입니다.

그러나 소숫점 계산을 하면서 정밀도 오류가 생기면서 잘못된 답을 냈습니다.)

이런 정밀도 오류는 프로그래밍에서 자주 발생하는 오류 중 하나라고 알고 있습니다.

처음에서 너무나도 작은 사소한 오차라 생각해서 무시하고 지나칠 수 있지만

이런 작은 오차가 쌓이고 쌓이고 쌓이면

나중에서는 터무니도 없이 큰 오차가 되어버립니다.

따라서 소수점 계산 등 정밀도 계산이 요구되는 문제에서는

소수점을 사용하지 않고 풀 수 있으면 되도록 정수로 풀어야 한다고 알고 있습니다.

혹시 구글이나 블로그 등에서 ccw 알고리즘이라고 검색해서 찾아보시겠어요??

행렬식을 이용한 알고리즘 인데요,

이 방법을 이용하면 소수점 없이 정수로만 계산이 가능합니다.

아 답변 정말 감사합니다.

전 단순히 두 점을 구해서 비교만 하는 거라 소수점이랑 상관 없을 거라고 생각했는데, 소수점이 길어지면 계산에 오차가 생겼을 줄은 생각 못네요

앞으로는 저도 글 올리기 전에 랜덤모듈로 반례를 좀 돌려 봐야겠네요

CCW 알고리즘은 검색해서 나오는 건 알고 있었습니다만, 일단 너무 보고 하는 느낌이라 일단은 제 생각대로 풀어도 왠지 될 거 같아서 가급적 한 번 도전해 본 거였습니다. 

암튼 답변 정말 감사합니다!!