beubeu95

최소비용 신장트리 최소 신장 트리  (Minimum Spanning Tree)  네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것.사례 : 도로 건설, 전기 회로, 통신 ,배관 등등흔히 아는 트리는 rooted 트리 라고 한다.싸이클이 없고 연결된(connected), 무방향( Undirected) 그래프를 트리라고 부른다. Undirected ( 무방향 ) weight( 가중치 ) 그래프이고, 가중치들은 모두 양수이다.싸이클이 없어야 된다.싸이클이 존재한다고 가정해보자. 그렇다면 싸이클 상의 랜덤한 한 엣지를 버리더라도 모든 노드들은 연결됨.노드가 n 개인 트리는 항상 n-1 개의 엣지를 가짐.해가 유일하지는 않음구현은 Kruskal 알고리즘과 ..

Directed Acyclic Graph DAG는 방향 사이클이 없는 방향 그래프예) 작업들의 우선순위 위상정렬DAG의 노드들을 순서화하는것을 말한다.단, 모든 에지에 대해서 i  알고리즘 1topologicalSort1(G){ for   topologicalSort2(G){ for each v C V visited[v] 정점의 순서는 상관없음 if(visited[v] = NO) then DFS-TS(v,R);}//알고리즘이 끝나면 연결 리스트 R에는 정점들이 위상정렬된 순서로 매달려있다.//수행시간 : ɵ(n+m)      최단경로 최단 경로 : 한 노드에서 다른 노드까지 이동하는데 드는 비용이 최소인 경로를 찾는 문제 1. Single - source ( one to a..

깊이우선순회 (DFS)   깊이우선탐색(DFS)이진트리의 순회 방법인 inorder, preorder, postorder 순회방법이 DFS의 이진트리 버전에 해당한다.leaf 노드에 도달했다는 것! -> 되돌아 가서 다시 확인DFS(G, v)   visited[v]  그래프가 disconnected 그래프 이거나 혹은 방향 그래프라면 DFS에 의해서 모든 노드가 방문되지 않을 수도 있음DFS를 반복하여 모든 노드 방문시간복잡도첫번째 for문에 의해서 시간복잡도 O(n)두번째 for문에 의해서 v노드와 엣지로 이어진 노드가 visited인지를 체크한다. 인접리스트로 표현했다면 시간복잡도는 엣지의 갯수에 비례하게 된다. O(m)최종적으로 O(n + m)의 시간복잡도를 갖는다.인접행렬로 표현했다면 인접노드의..

그래프 순회  순회(traversal)그래프의 모든 노드들을 방문하는 일BFS (Breadth-First Search , 너비우선순회)DFS (Depth-First Search, 깊이우선순회)너비우선순회(BFS) BFS 알고리즘은 다음 순서로 노드들을 방문L0 = {s}, 여기서 s는 출발 노드L1 = L0 의 모든 이웃 노드들L2 = L1 의 이웃들 중  L0에 속하지 않는 노드들....첫번째로 거리=1인 노드들 / 두번째로 거리=2인 노드들 동심원 형태로    큐를 이용한 너비우선순회출반 노드를 체크한다. (체크는 이미 방문된 노드라는 표시)출발 노드를 큐에 넣어준다.큐가 empty가 아닌동안 while문을 돌면서 반복한다.큐에서 노드를 꺼내고 그 노드의 인접노드 중 아직 방문하지 않은 노드들은 체크..

Graph그래프그래프는 여러 개의 점(노드 또는 정점)들이 선으로 연결된 구조를 나타내는 수학적인 개념입니다. 그래프는 다양한 현실 세계의 문제를 모델링하고 분석하는 데 사용됩니다. (무방향) 그래프 G = (V, E)V : 노드 혹은 정점(vertex)E : 노드쌍을 연결하는 Edge 혹은 LinkObject들 간의 이진관계를 표현n = |V|, m = |E| (개수)무방향이란 예를 들어 (1,2) 나 (2,1) 이 같은 개념 방향 그래프 (Directed Graph) 방향그래프(Directed Graph) G = (V, E)Edge (u, v) : u로부터 v로의 방향을 가짐가중치 그래프Edge마다 가중치(weight)가 존재 (사용빈도 높음)  두 노드 사이에 에지 여러개 있을 수 있느냐자기자신에게..

좋은 해시 함수란?만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해시 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해시함수값이 불규칙적이 되도록 하는게 바람직해시함수값이 키의 특정 부분에 의해서만 결정되지 않아야 함Division 기법h(k) = k mod m예: m = 20 and k = 91 ==> h(k) = 11장점: 한번의 mod연산으로 계산, 따라서 빠름단점: 어떤 m값에 대해서는 해시 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음.Multiplication 기법0에서 1사이의 상수 A를 선택: 0 kA의 소수부분만을 택한다소수 부분에 m을 곱한 후 소수점 아래를 버린다.꼭 위의 기법을 사용하여 해시 함수를 만들어야..

Hashing  해시 테이블(hash table) : 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조여기에서는 해시 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장 각 키에 대한 해시함수값을 그 키를 저장할 배열 인덱스로 사용  해싱(Hashing) : 해시 테이블을 이용한 탐색해시 테이블은 dynamic set(탐색과 삽입, 삭제를 지원하는 자료구조)을 구현하는 효과적인 방법의 하나*적절한 가정*하에서 평균 탐색, 삽입, 삭제시간 O(1)보통 최악의 경우 O(n) 충돌(collision)두 개 이상의 키가 동일한 위치로 해싱되는 경우즉, 서로 다른 두 키 k1과 k2에 대해서 h(k1) = h(k2)인 상황일반적으로|U| >> m 이므로 항상 발생 가능 (즉, 일반적..

순환함수와 수학적 귀납법 : 자기 자신을 호출하는 함수public class Code01 { public static void main(String [] args){ func(); } public static void func(){ System.out.println("Hello..."); func(); }}=> 무한루프에 빠짐 :순환은 항상 무한루프에 빠질까? -> NO~!public class Code02{ public static void main(String[] args){ int n =4; func(n); } public static void func(int k){ if(k : 무한루프에 빠지지 않으려면..

정렬정렬 :  여러 방식의 정렬을 하는 알고리즘  생각할 점! 1) out-of-place 정렬과 in-place 정렬out-of-place 정렬은 모든 데이터를 자료 구조의 복사본에 옮긴 후 순서대로 배열하여 정렬하는 방법입니다.in-place 정렬은 자료 구조를 그대로 두고 그 안에서 요소들의 위치를 바꾸어 정렬하는 방법입니다.2) 안정 정렬과 불안정 정렬안정 정렬은 중복된 숫자가 원래 순서를 유지한 상태로 정렬하는 방법입니다. 불안정 정렬은 중복된 숫자의 순서를 보장할 수 없습니다.3) 시간 복잡도모든 정렬 알고리즘에 대해 최악의 경우, 평균적인 경우, 최선의 경우의 복잡도를 알아볼 것입니다.최악의 경우는 정렬 전에 큰 수에서 작은 수로 있는 경우최선의 경우는 이미 정렬되어 있는 경우입니다.평균적인..

AVL 트리  AVL 트리란?: AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다.: AVL 트리에서는 왼쪽과 오른쪽의 높이 차이가 항상 1보다 작거나 같아야 합니다. * 트리1. 이진트리 : 모든 노드들이 둘 이하(0,1,2 개)의 자식을 가진 트리이다.2. 이진탐색트리 : 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진 트리이다.3. 정 이진트리 : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.4. 완전 이진트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다.  1 ) AVL의  노드class Node{ T data; Node left; Node right; Node parent; // 생성자 public Node(T obj){ data = obj;..