0. 플로이드 워셜 알고리즘이란? - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용 - 매 단계마다 현재 노드를 거쳐 가는 노드를 기준으로 알고리즘을 수행 - DP - 최단 거리 정보 저장 1. 알고리즘 진행과정 0️⃣ 초기 거리 테이블 설정 - 연결되지 않은 간선에는 무한대 - 자기 자신은 0 - 이외 간선들은 주어지는 거리 1️⃣ N번 돌면서 현재 노드 선택 >> 현재 노드를 거쳐서 지나가는 모든 경우를 고려 2️⃣ N^2번 돌면서 현재 노드를 거쳐 가는 모든 경로 순회 3️⃣ 원래 기록된 거리보다 현재 노드를 거쳐서 지나가는 거리가 더 짧다면 갱신 (직접 연결된 간선은 업데이트 X) -> O(N^3)의 시간복잡도를 가진다 2. 점화식 D[i][j] = min(D[i]..
0. 행렬 곱셈 방법 아이패드 있을때 추가하기.. n * m 행렬과 m* k 행렬의 곱! 1. General Solution 1.1 브루트포스 # 일반적인 3중 반복문 행렬 곱셈 answer = [[0 for _ in range(k)] for _ in range(n)] for f in range(n): for s in range(k): for j in range(m): answer[f][s] += a[f][j] * b[j][s] 1️⃣ n번 반복하면서 첫번째 행렬의 행을 순회한다 2️⃣ k번 반복하면서 두번째 행렬의 열을 순회한다 3️⃣ m번 반복하면서 곱셈을 진행한다 ➡️ Θ(n^3)의 시간복잡도를 가진다 1.2 분할정복 8번의 곱셈이 필요하다 8번의 덧셈이 필요하다 ➡️ Θ(n^3)의 시간복잡도를 가..
0. MOD 연산이란? 두 값을 나눈 나머지를 구하는 연산이다!! ex) 10 MOD 4 = 2 // 10 % 4 = 2 1. 유클리드 호제법 요약 1️⃣ a % b 수행, 결과값 c(나머지) 2️⃣ b % c 수행 3️⃣ 2️⃣ 반복, 나머지가 0이 되면 그 연산의 나누는 수(작은 수)를 최대공약수로 선택 분명 이산에서 배운건데 까먹었다.. 기억해두자 백준 1934 1850 1033 2. 확장 유클리드 호제법
