안녕하세요! 오늘은 파이썬 코딩테스트에서 자주 출제되는 기하 문제를 해결하는 방법에 대해 알아보겠습니다. 기하 문제는 주로 도형의 넓이, 둘레, 교차 여부, 거리 계산 등을 포함하며, 알고리즘 문제 풀이 시 중요한 부분입니다. 본 강좌에서는 기본적인 기하학 개념을 바탕으로 자주 출제되는 문제를 설명하고, 이를 성공적으로 풀기 위한 접근 방법을 단계별로 살펴보겠습니다.
문제: 두 선분의 교차 여부 판단하기
두 선분이 주어졌을 때, 이 두 선분이 교차하는지 여부를 판단하는 문제입니다.
문제 정의
주어진 두 선분 AB와 CD의 교차 여부를 판단하시오. 각 선분은 다음과 같이 두 점으로 정의됩니다:
- 선분
AB: 점A(x1, y1), 점B(x2, y2) - 선분
CD: 점C(x3, y3), 점D(x4, y4)
입력 형식
4개의 정수 x1, y1, x2, y2, x3, y3, x4, y4가 주어집니다.
출력 형식
선분이 교차하면 “YES”, 그렇지 않으면 “NO”를 출력합니다.
문제 접근 방법
두 선분이 교차하는지 판단하기 위해서는 기하학적인 개념인 ‘선분의 방향’을 사용해야 합니다. 두 선분의 각 점에 대하여 방향을 구하고, 이를 통해 교차 여부를 확인할 수 있습니다.
1. 방향 계산
선분 AB와 CD에 대해 방향을 계산하기 위해서는 다음의 공식을 사용합니다:
def direction(px, py, qx, qy, rx, ry):
return (qx - px) * (ry - py) - (qy - py) * (rx - px)이 함수는 점 P, Q, R에 대해 방향을 계산하여 양수, 음수, 0을 반환합니다.
2. 선분 교차 판단
선분 AB와 CD의 끝점이 서로 다른 방향을 가질 때 교차한다고 판단할 수 있습니다. 즉, 다음의 조건을 만족해야 합니다:
- 방향(
A, B, C)과 방향(A, B, D)의 곱은 0보다 크고, 방향(C, D, A)과 방향(C, D, B)의 곱도 0보다 큽니다.
이러한 조건을 연결하여 전체 로직을 하나의 함수로 통합할 수 있습니다.
3. 코드 구현
이제까지 설명한 내용을 바탕으로 전체 코드를 구현해 보겠습니다.
def ccw(px, py, qx, qy, rx, ry):
return (qx - px) * (ry - py) - (qy - py) * (rx - px) > 0
def is_intersect(x1, y1, x2, y2, x3, y3, x4, y4):
d1 = ccw(x1, y1, x2, y2, x3, y3)
d2 = ccw(x1, y1, x2, y2, x4, y4)
d3 = ccw(x3, y3, x4, y4, x1, y1)
d4 = ccw(x3, y3, x4, y4, x2, y2)
if d1 != d2 and d3 != d4:
return "YES"
return "NO"
# 예제 입력
x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())
print(is_intersect(x1, y1, x2, y2, x3, y3, x4, y4))결론
이번 강좌에서는 두 선분이 교차하는지 여부를 판단하는 알고리즘을 구현해 보았습니다. 기하 문제는 기초적인 수학 이론을 기반으로 하며, 알고리즘에 대한 이해가 필요합니다. 다양한 예제를 통해 연습하시면 기하 문제에 대한 자신감을 가질 수 있을 것입니다. 앞으로 더 많은 알고리즘 문제를 접해보고, 이를 통해 코딩 실력을 더욱 향상시키시길 바랍니다.
감사합니다!