개발노트 개발노트

1. 우선순위 큐란? 우선순위에 따라 데이터가 추출되는 자료구조이다. 들어간 순서 상관 없이 우선순위가 높은 데이터가 먼저 추출된다. 우리가 앞서 본 Queue는 들어온 시점을 기준으로한 Priority Queue라고 말할 수 있다. 이때 Queue는 먼저 들어간 데이터가 먼저 나오는 우선순위를 가진다. 이때 Pair(Key, Value) 형태의 아이템들로 저장 한다. 우선 순위가 높은 것이 먼저 추출되는 Max Priority Queue, 우선순위가 낮은 것이 먼저 추출되는 Min Priority Queue로 구성된다. ADT 보통 아래 2개의 연산을 이용한다. insert : 조건에 맞게 아이템을 삽입한다. removeMin : 우선순위가 가장 높은/낮은 아이템을 추출 한 후 구현 조건에 맞게 아이템..

1. 그래프란? 정점객체와 간선객체로 이루어진 자료구조이다. 일상 속에서 자주 사용되는 자료구조 중 하나이다. 용어 node [vertex] : 위치라는 개념이다. 정점이라고도 부른다. edge : 노드를 연결하는 선을 말하며 간선에 가중치를 둘 수 있다. 간선이라고도 부른다. adjacent vertex : 간선에 의해 직접 연결된 정점을 말한다. degree : 무방향 그래프에서 하나의 정점에 인접한 정점의 수이다. 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배이다. Subgraph : 그래프의 부분 그래프를 말한다. Path : v->w의 모든 간선의 나열이다. Cycle : 해당 노드에서 시작하여 다시 해당 노드로 돌아오는 경우를 말한다. Complete Graph ..

1. Tree란? 데이터들이 계층구조 형식으로 이루어진 자료구조를 말한다. 특징 트리는 선형구조가 아닌 비선형 구조인 계층 구조를 가진 자료구조다. 즉, 상-하 관계가 명확하다. Cycle이 없이 Path가 1개이다. 즉, 임의의 두 노드간의 경로가 유일하다. 어느 노드에서도 그 노드의 부모/자식들을 알 수 있어야 한다. 그래프의 한 종류로 노드가 N개 있으면 항상 N-1개의 간선을 가진다. Example - 조직도, 가계도, 파일 시스템, 스킬트리 등 용어 Root Node : 부모가 없는 노드이며, 트리는 하나의 루트 노드만을 가진다. Leaf Node : 자식이 없는 노드이다. Internal Node : 자식이 1개 이상의 노드를 말하며 Leaf Node와 Root Node가 아닌 노드를 말한다...

1. Stack Last In First Out 한쪽 끝에서 자료를 넣고, 빼는 자료구조이다. Example RunTime Stack 함수 , 재귀 함수 방문기록 ctrl + z 실행 취소 괄호 검사 , 수식 연산 미로찾기 DFS ADT Function 삽입 : Push 연산으로 Top에서만 이루어진다. 삭제 : Pop 연산으로 Top에서만 이루어진다. 탐색 : Top의 element를 return한다. Door가 1개이며 이를 Top이라고 부른다. 삽입/삭제/탐색 연산 모두 O(1)에 수행 가능하다. 2. Queue First In First Out 마지막에 들어 온것 보다 처음 들어온 것에 초점을 둔다. 즉, 처음 들어온 데이터가 먼저 나가는 구조이다. Example 1. 우선순위 같은 작업 예약 시..

1. Algorithm이란? 컴퓨터를 이용하여 문제를 해결하는 잘 정의된 절차 알고리즘 풀이 전략 Problem : 입력과 출력을 정의한다. Strategy : 환경에 따른 알고리즘 설계 기법을 정의한다. Ex) 메모리 비중이 큰 경우 Time cost보다 Memory Cost에 중점을 두어 알고리즘을 설계한다. 이때, Problem이 달라지면 전략 역시 달라질 수 있다. Algorithm : 절차를 세운다. Ex) PseudoCode Analysis : Correctness, Time/Space 성능, Optimal Check와 같은 분석 Implementation : 구현 Verification : Test를 진행하는 검증 단계 2. Analysis 우리는 알고리즘이 최적인지를 알기 위해 수행시간 혹..

1. 자료구조란? 자료구조는 데이터들의 집합을 의미한다. '적절한' 자료구조란 데이터들을 효율적으로 저장을 하고, 필요 연산을 빠른 시간내에 처리함을 의미한다. 여기서 말하는 연산이란 보통 삽입/삭제/탐색을 의미하며 상황에 따라 자주 사용하는 연산들이 존재한다. 예를 들어, 로그 파일과 같이 삽입의 연산을 많이 하고 삭제, 탐색의 연산을 적게 한다면 Unsorted Array와 같이 삽입이 O(1)인 방식을 사용하면 좋다. 혹은, 교통망과 같이 네트워크 상의 현실 문제를 모델링 할 때 그래프와 같은 방식으로 자료를 저장하면 된다. 2. 자료구조의 분류 여기서 말하는 선형구조란 데이터들을 선의 형태로 일렬로 저장하는 방식을 말하며, 비선형 구조는 데이터를 나란히 저장하지 않는 구조를 의미 한다. 3. AD..

Transport 계층의 주 목적은 end system의 process to process 전송 역할을 수행한다. 부가적으로 streaming을 위한 서비스, 신뢰성 기반의 데이터 전달을 위한 flow control 등도 제공한다. 1. User Datagram Protocol Process to Process 전송을 위한 multiplexing, demultiplexing만을 제공한다. UDP와 같이 비연결형 네트워크에서는 목적지 IP, Port만으로 소켓을 식별한다. TCP와 같이 소켓에 대해 1:1 통신을 하지 않고 여러 유저가 보낸 데이터를 하나의 소켓에서 받아들이므로 Resource 소모량은 적지만 Application이 모든 데이터를 받아들이므로 프로세스의 과부화 위험이 있다. header의 ..

1. Application Layer의 구조 Client - Server 구조 클라이언트는 서버와만 통신하고 동적 IP를 갖습니다. 지속적으로 서버와 연결하는것이 아닌 간헐적으로 연결합니다. 주로 서버에 Request 메시지를 보내고 서버로부터 요청 메시지를 brouser에 display 하는 역할을 수행합니다. 서버는 항상 켜져있고 고정 IP 주소를 갖습니다. 서버 과부화를 대비하여 같은 기능을 하는 서버 군집 혹은 성능 향상을 위한 캐시 서버를 함꼐 하기도 합니다. 클라이언트로부터 받은 request를 상황에 맞게 Response하는 역할을 수행합니다. 인터넷에서는 이 구조로 통신을 수행합니다. Peer to Peer 구조 별도의 서버 없이 Peer[End System]끼리 직접 통신을 한다. 서버처..