환율 정보가 담긴 N × N 표가 있다고 가정해 봅시다. 우리가 확인해야 할 것은 일련의 거래를 반복했을 때, 특정 통화로 시작한 금액 A보다 더 많은 금액을 같은 통화로 되돌려받을 수 있는 경로가 존재하는지 여부입니다. 이때 거래 수수료는 없으며, 소수점 단위의 거래도 가능하다고 가정합니다.
문제 이해하기
행렬에서 [i, j] 위치의 값은 통화 i 1단위로 구매할 수 있는 통화 j의 양을 의미합니다. 예를 들어 통화 0은 USD(미국 달러), 통화 1은 CAD(캐나다 달러), 통화 2는 EUR(유로)라고 해보겠습니다. 그러면 다음과 같은 순서로 차익거래가 가능합니다.
- 1 CAD를 0.65 EUR로 매도
- 0.65 EUR를 0.7865 USD로 매도 (0.65 × 1.21)
- 0.7865 USD를 1.00672 CAD로 매도 (0.65 × 1.21 × 1.28)
처음 1 CAD로 시작해 최종적으로 약 1.00672 CAD를 얻게 되므로, 이것이 바로 차익거래 기회입니다.
입력 및 출력 예시
입력이 아래와 같은 환율 행렬이라면,
| 1 | 1.28 | 0.82 |
| 0.78 | 1 | 0.65 |
| 1.21 | 1.55 | 1 |
출력은 True가 됩니다.
접근 방법: 로그 변환과 플로이드-워셜 알고리즘
차익거래 문제는 그래프 이론의 음수 사이클(negative cycle) 탐지 문제로 변환할 수 있습니다. 곱셈 연산을 로그를 취하면 덧셈으로 바뀌기 때문에, 각 환율에 −log₂를 적용하면 최단 경로 알고리즘을 활용할 수 있습니다. 구체적인 절차는 다음과 같습니다.
- 행렬의 모든 원소 matrix[i][j]를 −log₂(matrix[i][j]) 값으로 변환합니다.
- v := 행렬의 행 개수로 설정합니다.
- 플로이드-워셜(Floyd-Warshall) 알고리즘을 적용합니다.
- k를 0부터 v−1까지 반복
- i를 0부터 v−1까지 반복
- j를 0부터 v−1까지 반복
- matrix[i][j] := min(matrix[i][j], matrix[i][k] + matrix[k][j])
- 알고리즘 종료 후 대각선 원소 중 하나라도 음수가 존재하면 True를 반환합니다. 이는 자기 자신으로 돌아오는 경로에서 이득이 발생한다는 뜻, 즉 차익거래 기회가 있다는 의미입니다.
파이썬 구현 코드
import math
class Solution:
def solve(self, matrix):
# 모든 환율을 -log2 값으로 변환
for i in range(len(matrix)):
for j in range(len(matrix[0])):
matrix[i][j] = -math.log(matrix[i][j], 2)
v = len(matrix)
# 플로이드-워셜 알고리즘으로 최단 경로 계산
for k in range(0, v):
for i in range(0, v):
for j in range(0, v):
matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
# 대각선에 음수가 있으면 차익거래 가능
return any(matrix[i][i] < 0 for i in range(len(matrix)))
ob = Solution()
matrix = [
[1, 1.28, 0.82],
[0.78, 1, 0.65],
[1.21, 1.55, 1]
]
print(ob.solve(matrix))실행 결과
입력:
matrix = [
[1, 1.28, 0.82],
[0.78, 1, 0.65],
[1.21, 1.55, 1]
]출력:
True
핵심 정리
이 알고리즘의 시간 복잡도는 플로이드-워셜 알고리즘에 따라 O(N³)입니다. 통화의 종류가 많지 않은 실제 외환 시장에서는 충분히 실용적인 성능입니다. 핵심 아이디어를 요약하면 다음과 같습니다.
- 곱셈으로 표현되는 환율 관계를 로그 변환으로 덧셈 문제로 치환
- 플로이드-워셜 알고리즘으로 모든 통화 쌍 간의 최소 비용 경로 계산
- 대각선의 음수 값 = 음수 사이클 존재 = 차익거래 기회 발견