안녕하세요! 이번 포스팅에서는 파이썬을 이용한 코딩테스트 문제 중 하나인 “선분의 방향 구하기” 문제를 살펴보겠습니다. 본 문제를 통해 실질적인 문제 해결 능력을 기르고, 코딩테스트에서 자주 출제되는 기하학적 문제를 연습해보도록 하겠습니다.
문제 설명
두 점 A(x1, y1)와 B(x2, y2)가 주어질 때, 선분 AB와 선분 CD의 방향을 구하는 문제입니다. 선분 AB를 기준으로, 선분 CD의 방향을 구해 다음의 값을 출력하세요:
- 1: 선분 CD가 선분 AB의 왼쪽에 있을 때
- -1: 선분 CD가 선분 AB의 오른쪽에 있을 때
- 0: 선분 CD와 선분 AB가 평행할 때
입력 형식
첫 번째 줄에는 점 A와 B의 좌표가 공백으로 구분되어 주어지며, 두 번째 줄에는 점 C와 D의 좌표가 공백으로 구분되어 주어집니다.
A의 x y 좌표: x1 y1
B의 x y 좌표: x2 y2
C의 x y 좌표: x3 y3
D의 x y 좌표: x4 y4
출력 형식
선분 CD의 방향을 나타내는 정수를 출력합니다.
문제 해결 접근법
본 문제를 해결하기 위해서는 먼저 선분 AB와 선분 CD의 방향 벡터를 구합니다. 방향 벡터는 다음과 같이 계산할 수 있습니다:
- AB 벡터 = (x2 – x1, y2 – y1)
- CD 벡터 = (x4 – x3, y4 – y3)
이어서, 두 벡터의 외적을 구하여 방향을 판단합니다. 외적의 결과 값에 따라 선분의 방향을 결정할 수 있습니다.
외적 계산
두 벡터 (x1, y1)와 (x2, y2)의 외적은 다음과 같이 계산됩니다:
cross_product = x1 * y2 - y1 * x2이 값이 > 0이면 왼쪽, < 0이면 오른쪽, 0이면 평행입니다.
예제
예를 들어 A(1, 1), B(4, 4), C(4, 1), D(1, 4)가 주어진 경우, AB의 방향 벡터는 (3, 3)입니다. CD의 방향 벡터는 (-3, 3)입니다. 외적을 계산하면:
cross_product = (3 * 3) - (3 * -3) = 9 + 9 = 18 (따라서 선분 CD는 AB의 왼쪽에 위치합니다.)코드 구현
이제 위의 과정을 바탕으로 파이썬 코드를 작성해 보겠습니다:
def direction(a, b, c, d):
# 벡터 AB
ab = (b[0] - a[0], b[1] - a[1])
# 벡터 CD
cd = (d[0] - c[0], d[1] - c[1])
# 외적 계산
cross_product = ab[0] * cd[1] - ab[1] * cd[0]
if cross_product > 0:
return 1 # 왼쪽
elif cross_product < 0:
return -1 # 오른쪽
else:
return 0 # 평행
# 입력 예시
a = (1, 1)
b = (4, 4)
c = (4, 1)
d = (1, 4)
# 함수 호출
result = direction(a, b, c, d)
print(result)
결과
위 코드를 실행하면, 선분 CD는 AB의 왼쪽에 위치하기 때문에 결과는 1이 됩니다.
마무리
이번 포스팅에서는 선분의 방향을 구하는 알고리즘 문제를 풀어보았습니다. 이 문제는 기하학적 사고를 필요로 하며 벡터 외적에 대한 이해가 중요합니다. 다양한 문제를 풀면서 이러한 기하학적인 문제를 익히고, 코딩테스트에서 좋은 결과를 거두시길 바랍니다!
추가적인 팁
- 다양한 입력에 대해 충분히 테스트해보세요.
- 문제를 이해하는 데 있어 시각적인 도표를 활용하면 좋습니다.
- 외적의 결과를 통해 직접 시각적으로 디버깅해보세요.