Tech.log56 [라우팅을 통한 경로배정 체계과 인터네트워킹이란?] 라우팅을 통한 경로 배정 체계 최적성 단순성 안정성 유연성 - 정적 라우팅 기법 입력된 라우팅 정보가 재입력을 하기 전까지는 이전의 값이 변하지 않고 고정된 값을 유지하는 라우팅 기법 정적 라우팅 기법은 관리자가 수동적으로 라우팅 테이블을 관리하는 방법으로, 규모가 작은 네트워크에서 주로 사용 - 장점 : 가장 간단한 구현, 가장 효과적인 라우팅 가능 - 단점 : 전송 경로가 고정되어 트래픽 변화에 따른 동적 경로 배정 불가 - 동적 라우팅 기법 인접한 라우터들 사이에서 네트워크 정보를 교환하고, 라우팅 테이블을 자동으로 작성하도록 하는 것 - 장점 : 특정 네트워크나 라우터가 비정상적으로 동작하는 경우, 네트워크의 특정 위치에서 혼잡이 발생하는 경우에 사용 - 단점 : 경로 결정 과정이 복잡함, 경로 .. 2021. 5. 30. [최소 신장 트리(MST, Minimum Spanning Tree)] 신장트리(Minimum Spanning Tree, MST) 그래프가 모든 노드를 포함하고 모든 노드가 연결 되어있으며 Tree의 속성을 만족하는 그래프를 말한다. 최소신장트리(Minimum Spanning Tree, MST) 신장트리 가운데 가중치의 합이 최소인 경우를 신장 트리라고 한다. 이런 MST를 찾아내는 기법이 크게 두 가지가 있다. 크루스칼 알고리즘(Kruskal’s algorithm) 간선을 오름차순으로 정렬하여, 사이클이 만들어 질 경우를 제외하고 추가하는 방식 디스조인트 셋(disjoint set)을 기본 자료구조로 활용한다. 크루스칼 알고리즘의 시간 복잡도는 O(ElogV)이다. 디스조인트 셋(disjoint set)관련해서는 다음 포스팅에서 기재하겠다. 프림 알고리즘(Prim Algo.. 2021. 5. 30. [Fibonacci에서의 세 가지(Recursion, Dynamic Programming,Bottom-Up Approach] Fibonacci를 구하는 방법은 총 3가지가 있다. Recursion int Fibo(int num) { if(num == 1) return 1; else if( num ==2 ) return 1; else return Fibo(num-1)+Fibo(num-2); } 재귀방식으로 짜는 방식은 이와 같이 반복이 일어난다. fibo(3)이 좌우로 두번 반복하는 낭비가 발생한다. 해당 방식은 시간복잡도가 O(2^n)으로 나타난다. Dynamic Programming(Memoization) 이와 같은 반복되는 낭비를 막기 위해 Memoization 방식을 사용한다. 즉 위에 fibo(3),fibo(2) fibo(1) fibo(0)의 값을 저장해 놓은 뒤에 재 사용하는 것이다. int Fibo(int num) .. 2021. 5. 30. [DFS와 BFS의 차이] DFS(깊이 우선 탐색) 인접하는 한 정점에서 갈곳이 없을 때 까지 탐색하고 되돌아와 다음 정점을 탐색하는 방법 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. //인접 행렬로 구현 void dfs(int x) { check[x] = true; for(int i = 1; i 2021. 5. 30. 이전 1 2 3 4 5 6 ··· 14 다음
