혼자 정리

https://programmers.co.kr/learn/courses/30/lessons/92334 첫 풀이 import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.ArrayList; import java.util.Set; import java.util.HashSet; class Solution { public int[] solution(String[] id_list, String[] report, int k) { HashMap accused = new HashMap(); HashMap accusedCount = new HashMap(); Set criminalSet = new HashSet(..

어떤 문제를 해결하기 위해? 그래프의 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem) cf) 그래프의 정점끼리 최단 경로 구하는 다른 문제는 다음과 같다. 하나의 정점에서 다른 하나의 정점까지의 최단 경로 구하는 문제(single source and single destination shortest path problem) 하나의 목적지로 가는 모든 최단 경로를 구하는 문제(single destination shortest path problem) 모든 최단 경로 구하는 문제(all pairs shortest path problem) 기본 전제 단 하나의 간선(정점과 정점을 잇는 선)이라도 가중치가 음수이면 안 된다. 음수이면 ..

(구체적 슈트라센 알고리즘은 생략함) 정방행렬의 곱은 다음으로 일반화할 수 있다. $A = (a_{ij})$이고 $B = (b_{ij})$인 $n \times n$행렬일 때, $C = A \cdot B$의 원소 $c_{ij}$는 $i,j = 1,2, \cdots, n$에 대해 다음과 같이 나타낼 수 있다. $$ c_{ij} = \sum_{k=1}^{n} a_{ik} \cdot b_{kj} $$ 이를 단순한 방법으로 연산을 시키면 각 (for i = 1 to n) (for j = 1 to n)마다 (for k = 1 to n)번의 $a_{ik} \cdot b_{kj}$의 연산이 있어야 하므로, $\Theta(n^3)$의 시간이 소요된다. 언뜻 생각하기에는 $\Omega(3)$의 시간이 걸릴 것 같지만 $o..