여러분 안녕하세요! 오늘은 자바스크립트 코딩 테스트에서 자주 등장하는 문제 중 하나인 ‘선분의 교차 여부 구하기’에 대해 다뤄보겠습니다. 이 문제는 면접에서 자주 출제되며, 기하학적인 개념을 이해하고 코드로 구현하는 능력을 키우는데 큰 도움이 됩니다.
문제 설명
주어진 두 개의 선분이 교차하는지 여부를 판단하는 문제입니다. 각 선분은 두 점으로 정의되며, 선분 A는 점 A1(x1, y1)과 A2(x2, y2)로, 선분 B는 점 B1(x3, y3)와 B2(x4, y4)로 표시됩니다. 우리는 이러한 두 선분이 서로 교차하는지 여부를 판단해야 합니다.
입력
- A1: (x1, y1)
- A2: (x2, y2)
- B1: (x3, y3)
- B2: (x4, y4)
출력
교차하는 경우 true를, 그렇지 않은 경우 false를 반환해야 합니다.
예제
입력 예제
A1: (1, 1), A2: (4, 4)
B1: (1, 4), B2: (4, 1)
출력 예제
true
문제 접근 방식
이 문제를 해결하기 위해서는 몇 가지 기하학적인 개념과 알고리즘을 활용해야 합니다. 특히, 선분의 교차 여부를 판단하기 위한 두 가지 방법을 소개합니다. 첫 번째 방법은 사각형의 넓이를 이용한 방법이고, 두 번째는 벡터의 외적(Cross Product) 개념을 이용한 방법입니다.
1. 외적을 이용한 교차 여부 판단
선분이 교차하는지 여부를 판단하기 위해 벡터의 외적을 사용합니다. 두 방향 벡터 A와 B간의 외적이 0보다 크면 한 방향에 있고, 0보다 작으면 반대 방향에 있음을 알 수 있습니다.
직선의 방정식
Let's define line segments A and B:
A: [(x1, y1), (x2, y2)]
B: [(x3, y3), (x4, y4)]
외적 공식
선분 AB와 AC에 대해 다음과 같은 외적 공식을 사용할 수 있습니다:
cross(A, B) = (A.x * B.y - A.y * B.x)
2. 선분과 한 선의 교차 여부 판단
선분이 주어졌을 때, 한 선이 특정 선분을 교차하는지 여부를 판단하기 위해서는 또 다른 기법을 사용할 수 있습니다. 이 기본적으로 각 선분의 끝점을 포함한 직선을 읽어들여 교차 여부를 계산하는 것입니다.
구현 코드
이제 위에서 설명한 방식으로 실제 코드를 구현해 보겠습니다.
function isIntersect(A1, A2, B1, B2) {
const orientation = (p, q, r) => {
const val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
if (val === 0) return 0; // collinear
return (val > 0) ? 1 : 2; // clock or counterclock wise
};
const onSegment = (p, q, r) => {
return (
q[0] <= Math.max(p[0], r[0]) &&
q[0] >= Math.min(p[0], r[0]) &&
q[1] <= Math.max(p[1], r[1]) &&
q[1] >= Math.min(p[1], r[1])
);
};
const o1 = orientation(A1, A2, B1);
const o2 = orientation(A1, A2, B2);
const o3 = orientation(B1, B2, A1);
const o4 = orientation(B1, B2, A2);
if (o1 !== o2 && o3 !== o4) return true;
if (o1 === 0 && onSegment(A1, B1, A2)) return true;
if (o2 === 0 && onSegment(A1, B2, A2)) return true;
if (o3 === 0 && onSegment(B1, A1, B2)) return true;
if (o4 === 0 && onSegment(B1, A2, B2)) return true;
return false;
}
// Example usage
const A1 = [1, 1],
A2 = [4, 4],
B1 = [1, 4],
B2 = [4, 1];
console.log(isIntersect(A1, A2, B1, B2)); // true
코드 설명
우선, orientation 함수는 주어진 세 점(p, q, r)에 대한 방향성을 판별합니다. 이를 통해 선분 A, B의 교차 여부를 판단할 수 있습니다.
그 다음, onSegment 함수는 점 q가 선분 pr 위에 있는지를 판단합니다. 교차 여부를 확인한 후, 특정 경우 (세 점이 모두 일치하는 경우)에 대해 추가적인 판단을 진행합니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(1)입니다. 단 한 번의 비교를 통해 교차 여부를 확인할 수 있기 때문입니다.
결론
이번 강좌에서는 자바스크립트를 이용해 선분의 교차 여부를 판단하는 알고리즘을 알아보았습니다. 기하학적 문제에 대한 이해와 코딩 능력을 키울 수 있었기를 바랍니다. 면접 준비에 도움이 되었길 바라며, 다음 강좌에서 또 만나요!