1과 N을 제외한 가장 작은 약수와 가장 큰 약수를 곱하면 N이 된다 int의 Wrapper Class인 Integer 클래스를 이용하면 정수의 최대값과 최소값을 출력가능 static int Integer.MAX_VALUE static int Integer.MIN_VALUE import java.util.Scanner; public class boj_1037 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int cnt = sc.nextInt(); int max = Integer.MIN_VALUE; // max 변수는 초기값으로 가장 min한 정수값..
function fib(n) a = 1, b = 1; if (n == 1 || n == 2) return 1; for i = 3 to n c = a + b; a = b; b = c; return c; iterative function fib(n) if (n == 1 || n == 2) return 1; else return fib(n-1) + fib(n-2); What’s the time complexity? T(n) = T(n-1) + T(n-2) + 1 minimum cost between stations int cost[N][N] = { {0, 10, 75, 94}, {-1, 0, 35, 50}, {-1, -1, 0, 80}, {-1, -1, -1, 0} }; minCost(0, N-1) = MI..

그래프 G =(V,E) V: 노드 node , 정점vertex E: 노드쌍을 연결하는 edge 혹은 link n=|V| = 8 m=|E| = 11 방향 그래프 directed Graph 가중치(Weighted) 그래프 : 에지마다 가중치가 지정된다 인접행렬 adjacency matrix 당연히 대칭 행열 n*n 행렬 A = (a ij) edge있으면 1 없으면 0 저장공간 O(n^2) 어떤 노드 v에 인접한 모든 노드 찾기 O(n) 어떤 에지 (u,v)가 존재하는지 검사 O(1) 인접 리스트 (adjacency list) 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트 비대칭 저장공간 O(n+m) 어떤 노드 v에 인접한 모든 노드 찾기 O(degree(V)) degree(v):..

무방향 (양수) 가중치 그래프 G =(V, E) 각 edge (u, v) ∈E에 대해서 가중치 : W(u, v) 문제 : edge들의 부분집합 T ∈ E를 찾아라 1. T에 속한 edge들에 의해 모든 정점들이 서로 연결된다 2. 가중치의 합 ∑ w(u, v) 이 최소가 되도록 한다 (u, v)∈ T 3. 입력 : n개의 도시 도시와 도시를 연결하는 도로비용 문제 : 최소의 비용으로 모든 도시들이 연결되게 한다 어떤 부분집합 A에 대해 A ∪{(u, v)} 도 역시 MST의 부분집합일 경우 edge (u, v)는 A에 대해서 안전한다 generic -mst (G, W) A