GoldTree of C.E

그래프 그래프의 정의는 '연결되어 있는 객체 간의 관계를 표현하는 자료구조'이다. 그예로는 전에 알아본 Tree구조도 그래프의 특수한 경우이고, 지하철노선도 또한 그래프의 일종이다. 그래프의 정의와 용어 그래프는 정점(vertex)과 간선(edge)들의 유한 집합이라 할 수 있다. 수학적으로는 G = (V, E)로 표시한다. 정점(Vertices) 여러 가지 특성을 가질 수 있는 객체 V(G) : 그래프 G의 정점들의 집합 노드(node)이다. 간선(edge) 정점들 간의 관계 E(G) : 그래프 G의 간선들의 집합 링크(link)이다. 종류 무방향 그래프(undirected graph) : 간선을 통해서 양방향으로 갈수 있다. 방향 그래프(directed graph) : 간선에 방향성이 존재하는 그래프..

트리의 개념 지금까지는 리스트, 스택, 큐 등의 선형 자료 구조(linear data structure)를 알아봤다. 이번에는 계층적인 구조(hierachiacal structure)알아보려 한다. 계층적인 구조에 대해 예를 들면 컴퓨터의 폴더를 들수있다. 폴더는 상위폴더와 하위폴더로 이루어져있는 것을 알 수 있다.하위폴더를 들어가기 위해서는 먼저 상위폴더를 들어간 후에 하위폴더로 들어갈 수 있다. 트리의 용어들 트리의 구성 요소에 해당하는 A,B,C,...,N,O를 노드(node)라 한다. 계층적인 구조에서 가장 높은 곳에 있는 노드(위 그림의 A)를 루트(root)노드라고 하며, 그 외의 노드를 서브트리(subtree)라고 한다.위 그림은 {B,F,G},{C,H,K,L,M},{D,I,N},{E,J,O..

정규화는 이상현상이 발생하는 릴레이션을 분해하여 이상현상을 없애는 과정이다. 그럼 이상현상은 무엇일까? 이산현상 이상현상은 릴레이션 처리 과정에서 불필요한 데이터 중복으로 인해 발생하는 부작용을 뜻한다. 종류로는 삽입, 수정, 삭제 이상으로 분류 할 수 있다. 삽입이상 불필요한 데이터를 함께 입력하지 않고서는 원하는 데이터만 입력이 불가능한 상황이다. 투플 삽입 시 특정 속성에 해당하는 값이 없어 NULL 값을 입력해야 하는 현상이다. -> NULL 값 문제 발생 수정이상 투플 수정 시 중복된 데이터의 일부만 수정되어 데이터의 불일치 문제가 일어나는 현상이다. 불일치 문제 발생 삭제이상 투플 삭제 시 같이 저장된 다른 정보까지 연쇄적으로 삭제되는 현상이다. 연쇄삭제 문제 발생 함수 종속성 함수 종속성은 ..

연결기반 트랜스포트 : TCP TCP의 특징을 먼저 알아보자 점대점(point to point) 단일 송신자와 단일 수신자의 통신이다. 신뢰적인 순차 바이트 스트림(reliable, in-order byte stream) 메시지의 경계가 없다. 파이프라인(pipelined) stop&wait의 반대 방식으로 특정량(윈도우)만큼의 메시지를 연속적으로 보낸다. 더보기 stop&wait의 방식은 하나의 메시지를 보내면 receiver측에서 받았다는 메시지가 오기 전까지 다음 메시지를 보내지 않는다. TCP 혼잡 및 흐름제어에서 윈도우 크기를 결정한다. 전 이중 데이터(full duplex data) 한 개의 연결에서 양방향 데이터 흐름을 가진다. MSS(maximum segment size) : 최대 세그먼트..

원형 연결 리스트 원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트이다. 단순 연결 리스트와 원형 연결 리스트의 차이점을 알아보자. 위 그림의 단순 연결 리스트를 보면 마지막 노드는 다음 연결할 노드가 없어 NULL값을 가지고 있지만, 원형 연결 리스트의 경우 마지막 노드가 첫번째 노드를 가리키면서 순환하는 모습을 볼 수 있다. 더 구체적으로 얘기하면 단순 연결 리스트의 마지막 노드의 링크는 NULL값을 가지고 있지만, 원형 연결 리스트의 마지막 노드의 링크는 첫번째 노드를 가리키고 있다. 예시로 지하철 4호선과 2호선 순환내선을 들 수 있다. 4호선은 단순 연결 리스트이다. 오이도를 head라고 했을 때, 오이도 -> 정왕 -> 신길온천 -> ... -> 창동 ->상계 -> 당고개 으로..

수학적 귀납법 Basis n = 1일때 성립 Induction Hypersuccess n = k 일때 성립가정 Induction profile n= k+1일때 성립가정 Binomial CoefficientsC(n ,r) = n! / r!(n - r)! Σn, m=0 C(n,r) = 2^n 오일러사이클 (모든 정점의 차수가 짝수여야한다.)

데이터베이스 설계는 건축에서 지반설계와 같다. 데이터베이스 설계(지반설계)가 잘못되면 소프트웨어 설계(건물 설계)에 지장이 생긴다. 데이터베이스 설계(데이터 모델링) 현실 세계의 복잡한 개념을 단순화하고 추상화해서 데이터베이스화하는 과정 데이터베이스 생명주기 데이터베이스의 생성과 운영에 관련된 특징

HeapSOrt O(n lg n) worst case - like merge sort sorts in place - like insertion sort combines the best of both algorithms To understand GeapSort, study Heaps and Heap operations Priority Queues. Heap A is a nearly complete binary tree. Height of node = # of edges on a longest simple path from the node down to a leaf. Height of heap = height of root = 세타(lg n). A heap can be stored as an array A[..

네트워크 애플리케이션의 원리 네트워크 애플리케이션 개발의 중심은 다른 종단 시스템에서 동작하고 네트워크를 통해 서로 통신하는 프로그램을 작성하는 것이다. 예를 들어, 웹 서버 소프트웨어는 웹 브라우저 소프트웨어와 통신한다. 따라서 새로운 애플리케이션을 개발할 때는 여러 종단 시스에서 실행 되는 소프트웨어를 작성할 필요가 있다. 중요한 것은 라우터나 링크 계층 스위치와 같이 네트워크 코어 장비에서 실행되는 소프트웨어를 작성할 필요는 없다는 점이다. 또한 이들 네트워크 코어 장비를 위한 애플리케이션 소프트웨어를 개발하더라도 그렇게 할 수 없다. 네트워크 애플리케이션 구조 애플리케이션 구조는 네트워크 구조(5계층의 인터넷 구조)와 다르다. 애플리케이션 개발자 관점에서 네트워크 구조는 고정되어 있고 애플리케이션..

인터넷이란 무엇인가? 구성요소로 본 인터넷 인터넷은 컴퓨팅 장치를 연결하는 컴퓨터 네트워크이다. 컴퓨터 네트워크(computer network)는 이제 호스트 혹은 종단 시스템이라고 부른다. 종단 시스템은 통신 링크(communication llink)와 패킷 스위치(packet switch)의 네트워크로 연결된다. 통신 링크 동축케이블, 구리선, 광케이블, 라디오 스펙트럼을 포함한 다양한 물리 매체로 구성된다. 이때 각각의 링크들은 다양한 전송률(transmission rate, 링크 대역폭)을 이용하여 데이터를 전송하며, 전송률은 초당 비트 수를 의미하는 bps(bit per second)단위를 사용한다. 패킷(packet) 한 종단 시스템이 다른 종단 시스템으로 보낼 데이터를 가지고 있을 때, 송신..