하나의 N x N 환율 테이블이 있다고 가정합니다. 우리가 할 수 있는 거래의 순서가 있는지 여부를 확인해야 합니다. 이제 어떤 통화의 금액 A로 시작하여 해당 통화의 A보다 큰 금액이 될 수 있습니다. 거래 비용이 없으며 소량 거래도 가능합니다.
이 행렬에서 항목 [I, j]의 값은 통화 i의 한 단위로 살 수 있는 통화 j의 양을 나타냅니다. 이제 통화 0은 USD, 1은 CAD, 2는 EUR입니다. 우리는 다음과 같이 차익 거래를 할 수 있습니다 -
-
0.65 EUR에 1 CAD 판매
-
0.65 EUR을 0.7865 USD(0.65 * 1.21)에 판매
-
0.7865 USD를 1.00672 CAD(0.65 * 1.21 * 1.28)에 판매
따라서 입력이 다음과 같으면
| 1 | 1.28 | 0.82 |
| 0.78 | 1 | 0.65 |
| 1.21 | 1.55 | 1 |
그러면 출력이 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
범위 0에서 행렬 크기까지의 i에 대해
-
범위 0에서 행렬[0]의 크기에 있는 j에 대해
-
matrix[i,j] :=-log base 2 value of (matrix[I,j])
-
-
-
v :=행렬의 행 수
-
범위 0에서 v의 k에 대해 수행
-
범위 0에서 v에 있는 i에 대해 수행
-
0~v 범위의 j에 대해 수행
-
행렬[I, j] :=행렬[I, j]의 최소값 및 (행렬[I, k] + 행렬[k,j])
-
-
-
-
행렬의 대각선에 있는 항목 중 0이 아닌 항목이 있으면 True를 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
파이썬
import math class Solution: def solve(self, matrix): 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