2차원 평면상에 세 개의 벡터 A, B, C가 주어져 있다고 가정해 보겠습니다. 확인해야 할 문제는 벡터 A에 90도 시계 방향 회전과 벡터 C의 덧셈이라는 두 가지 연산을 필요한 만큼 자유롭게 반복 적용하여 벡터 B를 만들어 낼 수 있는지의 여부입니다.
예를 들어 A = (-4, -2), B = (-1, 2), C = (-2, -1)이라면 답은 True입니다. A에 C를 한 번 더하면 (-2, -1)이 되고, 여기에 90도 시계 방향으로 회전하면 정확히 (-1, 2), 즉 B에 도달하기 때문입니다.
핵심 아이디어
이 문제를 효율적으로 풀려면 다음과 같은 수학적 성질을 활용하면 좋습니다.
- 90도 시계 방향 회전을 4번 적용하면 원래 벡터로 돌아오므로, 회전은 0번, 1번, 2번, 3번 중 하나로 귀결됩니다.
- 회전과 덧셈을 자유롭게 섞어 적용할 수 있으므로, 도달 가능한 최종 벡터는 항상 Rⁱ(A) + m·C + n·R(C) 형태로 표현됩니다. 여기서 R은 90도 시계 방향 회전, m과 n은 임의의 정수입니다.
- 따라서 각 회전 경우(i = 0, 1, 2, 3)마다 차이 벡터 B − Rⁱ(A)가 C와 R(C)의 정수 선형 결합인지만 검사하면 됩니다.
알고리즘 단계
먼저 util(p, q, r, s) 함수를 정의합니다. 이 함수는 차이 벡터 (p, q)가 기준 벡터 (r, s)와 그 90도 회전 벡터의 정수 배 조합으로 표현 가능한지를 판정합니다.
- d := r × r + s × s 를 계산합니다.
- d가 0이라면 (r, s)가 영벡터라는 의미이므로, p와 q가 모두 0일 때만 true를 반환합니다.
- 그 외의 경우에는 (p × r + q × s)와 (q × r − p × s)가 모두 d로 나누어 떨어질 때 true, 아니면 false를 반환합니다.
메인 함수에서는 네 가지 회전 경우(0°, 90°, 180°, 270°)에 대해 util()을 호출하고, 하나라도 true가 나오면 전체 결과는 True, 그렇지 않으면 False입니다.
예제 구현
다음 파이썬 코드로 실제 동작을 확인해 보겠습니다.
def util(p, q, r, s):
d = r * r + s * s
if d == 0:
return p == 0 and q == 0
return (p * r + q * s) % d == 0 and (q * r - p * s) % d == 0
def solve(p, q, r):
return (
util(p[0] - q[0], p[1] - q[1], r[0], r[1])
or util(p[0] + q[0], p[1] + q[1], r[0], r[1])
or util(p[0] - q[1], p[1] + q[0], r[0], r[1])
or util(p[0] + q[1], p[1] - q[0], r[0], r[1])
)
p = (-4, -2)
q = (-1, 2)
r = (-2, -1)
print(solve(p, q, r))입력
(-4, -2), (-1, 2), (-2, -1)
출력
True
복잡도 분석
검사해야 할 회전 경우는 네 가지뿐이고 각 판정은 상수 시간 안에 끝나므로, 전체 시간 복잡도는 O(1)입니다. 별도의 자료구조를 사용하지 않으므로 공간 복잡도 역시 O(1)입니다.