개발노트 개발노트

1. Network Layer란? 네트워크 계층의 핵심 기능은 출발지부터 목적지까지의 길을 찾아주는것이다. 호스트는 길을 찾을 때 default gateway로 패킷 전송을 하기 때문에 라우팅 성능이 크지 않아도 괜찮다. 하지만 라우터는 연결된 수 많은 라우터들 간의 정보를 교환하면서 경로를 결정하기 때문에 라우팅 성능이 우수하다. Routing Routing Processor에서 Routing Algorithm을 통해 나온 결과 값을 Forwarding Table에 저장하여, 출발지에서 목적지까지의 모든 경로 중 최적의 경로를 결정한다. 이때 Forwarding Table에는 목적지 IP 주소와 해당 포트 번호가 저장된다. Forwarding Data Plance 영역에서 입력으로 들어온 패킷 헤더의 ..

Iterable과 Iterator Java Collection Framework 상위에 Iterable 인터페이스가 존재한다. Iterable 인터페이스 안에는 Iterator 추상 메소드가 존재한다. 따라서 Collection 인터페이스 계층구조에서 구현된 클래스들은 모두 iterator 메소드를 가지고 있다. 따라서 이 클래스들은 모두 Iterator를 사용할 수 있다. (단 map이나 set은 key, value로 이루어져있기 때문에 직접 iterator를 호출할 수없고 keySet이나 entrySet 메서드를 이용해 사용한다.) 이를 사용한 이유는 Java Collection Framework에 저장된 데이터를 읽어오는 방법을 표준화하고 싶기 때문이다. Iterator Method hasNext(..

1. JCF란 Java에서 기본적인 자료구조들을 한 곳에 모아 관리하고 편하게 사용하기 위해 제공한다. 하얀 배경 색이 아닌것들은 인터페이스고, 하얀 배경은 실제 구현한 클래스다. 2. List 순서가 있는 데이터들의 집합이며 데이터들의 중복을 허용한다. Vector 원하는 Index에 바로 접근할 수 있는 Random Access가 빠른 시간에 가능하다. 데이터가 꽐 찰 경우 Array Doubling을 이용한다. 즉, 공간이 모자를 때 2배의 공간을 재 할당한다. 이로 인해 메모리를 많이 소모하는 단점도 있다. 또한 데이터를 중간에 삽입/삭제가 일어날 경우 데이터를 Transfer하는 Cost가 발생한다. 모든 메소드가 동기화를 보장해주어 공유 자원이나 복수의 사용자가 존재할 때 좀 더 안전하게 프로..

1. 정렬이란? 순서 없이 나열된 자료 중 특정 Key에 따라 오름차순/내림차순으로 자료를 재배열 한다.. 정렬은 실 생활에서 혹은 프로그래밍을 하면서 자주 사용되는 개념이다. 2. Bubble Sort 인접한 두 값을 비교하여 정렬하는 방법이다. 한쪽에서 다른 한쪽으로 크기를 비교 & 교환함으로써 반대편까지 가게 되고, 가장 큰 값 혹은 작은 값이 한쪽 끝으로 이동하게 된다. 즉 단계마다 제일 최대/최소 값이 끝에서부터 정해진다. 이러한 과정이 마치 물속의 거품과 같다해서 버블정렬이라고 부른다. 버블 정렬의 경우 최상, 평균, 최악의 경우 항상 일정하게 O(n^2)이다. Worst Case : 역순으로 정렬되었을 때 Basic Operation의 갯수는 총 O((n^2 /2 )x 3)이다. 이는 SWA..

1. 최단 경로 문제란? 최단 경로 문제란 두 노드를 잇는 가중치의 합이 가장 짧은 경로를 찾는 문제이다. 가중치가 모두 동일하면 BFS로 찾을 수 있다. srouce가 1개이고 destination이 1 개인 경우 srouce가 1개이고 destination이 n 개인 경우 srouce가 n개이고 destination이 n 개인 경우 Lemma의 정리 최단경로의 부분 경로는 모두 최단 경로이다. 2. Dijkstra's Algorithm 간선의 가중치가 음수가 아닐 때 사용하며 Prim's Algorith과 매우 유사한 방식으로 진행된다. 여기서도 정점들은 UnSeen Verticies, Tree Verticies, Fringe Verticies에 속하며 모든 정점들을 Tree Verticies로 넣는..

1. Greedy Algorithm Greedy Algorithm이란 최적해를 푸는 방법 중 하나로, 현 상황에서 어떤 '기준'을 가지고 가장 좋아 보이는 선택을 계속한다. 이는 현 상황에서 제일 좋다고 생각 했지만 나중에는 안 좋은 선택일 수도 있다. 하지만 중간에 수정은 못한다. 그럼에도 이런 경우는 드물기 때문에 Greedy Algorithm은 자주 사용되는 알고리즘 기법이다. 최적해란? 여러 정답 중 가장 좋은 정답을 고르는것이다. 우리는 Greedy Algorithm을 이용하여 Minimum Spanning Tree Problem과 Shortest Path Problem을 해결한다. 2. Minimum Spanning Tree Spanning Tree란? Undirected Graph 이면서 C..

1. Binary Search Tree란? Dictionary를 구현하는 방법 중 하나이다. 이는 다음과 같은 조건을 만족한다. 구조 조건 : Binary Tree의 구조적 특징을 갖는다. 즉, 트리형태로 구성돼 있으며 자식은 0 또는 1개 또는 2개를 가진다. 순서 조건 : 모든 SubTree에 대해서 왼쪽 자식의 Key

Dictinary란 임의의 Key를 삽입/삭제/탐색하는 자료구조이다. 아이템들은 Pair [Key, Value]를 가진다. 예를 들어, 사전에서 단어 정의, DNS Mapping Table 등 검색을 할 때 사용된다. 구현방식에 따라 설명을 진행 한다. 1. List-based Dictinary = Log File = Sequence Unsort List 데이터가 들어오는대로 저장한다. 삽입 : 들어오는대로 저장하면 되므로 O(1)이다. 삭제 : 배열의 경우 원소들을 transfer 하기 때문에, 리스트의 경우 탐색하기 때문에 O(n)이 소요된다. 탐색 : Unsort 돼있어 모든 노드를 탐색하며 O(n)이다. Example) 기록, 로그 파일과 같이 삽입 연산이 자주 일어나는 경우 사용된다. 2. Se..