[알고리즘] 최단거리 알고리즘 - 플로이드 와샬 알고리즘
포인트 플로이드 와샬 알고리즘은 최단거리를 구하는 알고리즘으로 모든 점에서 모든 점에 최단 거리를 구해주는 알고리즘 입니다. 단, 그래프 내부에 음수 사이클이 있는 경우 최단 거리를 구할 수 없습니다. dp (다이나믹) 을 활용하여 시간 복잡도 O(n^3)에서 문제를 해결합니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python # 플로이드 와샬 알고리즘 O(n^3) 에 문제를 해결할 수 있으면, # dp 를 사용하여 모든 점에서 모든 점 최단 거리를 구해준다. # 음수 사이클이 있는 경우 구할 수 없다. (벨만 포드와 똑같다.) INF = 987654321 data = [ [0, 5, INF, 8], [7, 0, 9, INF], [2, INF, 0, 4], [INF, INF, 3, 0..
2021. 4. 28.
[알고리즘] rotate image
포인트 시계 방향과 반시계 방향을 적용할 수 있는가? 를 물어보는 문제 입니다. python 에서는 zip 을 사용해서 하는 방법도 있지만, 이 방법도 유용하니 잘 사용해보면 좋을 것 같습니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 시계 방향 matrix = matrix[::-1] n = len(matrix) for row in range(n): for col in range(row + 1, n): matrix[row][col], matrix[col][row] = matrix[col][row], matrix[row][col] print(matrix) matrix = [[1, 2, 3], [4, ..
2021. 4. 25.