필기용 블로그

○JDBC (Java Database Connectivity)

 ▷java에서 DB접근을 위한 표준 API

 ▷여러 DBMS (Database Management System)을 동일한 방법으로 접근하게 도와주는 API

 ▷해당 DBMS, DBMS접근을 위한 JDBC Driver가 필요하다.

 ▶접근 방법

  ▷import java.sql.*

  ▶Register JDBC driver

   ▷드라이버 종류

  ▶DB 연결

   ▷Connection conn = DriverManager.getConnection(DBMS 테이블, 사용자, 암호)

  ▶SQL 문장(쿼리) 정의, 사용

   ▷String sql = "SELECT ~~ FROM ~~ ..."

   ▷PreparedStatement - 같은 명령을 다른 매개변수로 여러 번 실행 가능

  ▶결과 획득

   ▷ResultSet rs = stmt.executeQuery(sql);

   ▷명령어에 따라 메소드가 다름

  ▶종료

※SQL 기초

○Poisson process {N(t), t ≥ 0}

 ▶다음 조건들을 만족하는 Counting Process (주어진 시간 내에 일어난 사건의 수)

  ▷N(0) = 0

  ▷{N(t), t ≥ 0}

  ▷P(N(t + h) - N(t) = 1} = λh + o(h) (h : 작은 시간 / o(h) : 매우 작은 값들 - 무시 가능)

  ▷P(N(t + h) - N(t) ≥ 2} = o(h) - 2번이상 일어날 가능성 거의 없음.

 ▶N(t), t≥0이 Poisson process라면 (rate λ ＞ 0)

  ▷주어진 간격 t 내의 사건의 수 (N(t + h) - N(t))는 Poisson random variable이다. (mean = λt)

 ▶Interarrival and Waiting time distribution

  ▷T_n : (n-1)번째 사건과 n번째 사건 사이의 간격 (sequence of interarrival times)

  ▷T_n ~ Exp(λ) (mean 1/λ)

  ▷Waiting time S_n ~ Gamma(n, λ)

●Client - Server Model

 ▷Client : 서버에 서비스를 요청

 ▶서버 : 클라이언트에게 서비스를 제공

  ▷Host : 서버 주소

  ▷Port : 서버의 서비스 특정

   ▷잘 알려진 Port

○Socket

 ▷java.net.Socket

 ▷Communication의 양 끝 Point를 의미

 ▷Host, port로 구성됨.

 ▶Client - Socket 연결

  ▷Socket (서버Host, 서버Port) : 연결 요청

  ▷getLocalAddress().getHostAddress() : 자신의 Host Address

  ▷getLocalPosr() : 자신의 Port - 가변적?

  ▷getInputStream() : 서버가 전송한 Stream 읽기.

 ▶Server 생성 - 하나의 Client만 허용

  ▷ServerSocket(Port) : 해당 Port로 서버 Socket 생성

  ▷serverSocket.accept() : Client와 Connection이 되면 return, Client Socket 얻어냄.

  ▷serverSocket.InetAddress() : Client 정보

 ▶다중 Client 서버

  ▷Thread 이용

 ▶Timeout 설정

  ▷연결 Timeout

  ▷모든 R/W에 대한 Timeout 설정

 ▶Web Data 받기

●Heap

 ▷Binary Tree의 일종

 ▷Node에 key값들을 저장한다.

 ▶조건

  ▶Heap-Order : key(v) ≥ key(parent(v)) 만족

   ▷최소 Heap - root = 최소 key

   ※ key(v) ≤ key(parent(v)) 인 경우, 최대 Heap

  ▶Complete Binary Tree 만족

   ▷높이가 h인 Binary Tree에 대해서, depth i (i < h)에는 2ⁱ 개의 Node가 있다.

   ▷Internal nodes는 External nodes의 왼쪽에 있다.

 ▶Height of a Heap

  ▷n개의 key를 가지는 Heap의 height : log(n)

  ▷n = 1 + 2 = 4 + ... + 2^h-1 + (1 ~ 2^h) ＜ (2^h+1)

 ▶Bottom-up Heap Construction

  ▶Heap Merging 이용

   ▷2개의 Heap과 새로운 key K에 대해

   ▷k를 root로하며, 2개의 Heap을 subtree로 하는 Heap 생성

   ▷downheap - heap order restore

  ▶phase i에서

   ▷2ⁱ - 1의 heap 2개를 가지고 2ⁱ⁺¹ - 1인 Heap을 만듬.

   ▷O(log(n))

 ▶Heap - Priotity Queue

  ▷Heap을 이용하여 Priority Queue 구현

  ▷각 Node에 Key, Element 저장

  ▷Insert, removeMin 효율적으로 동작 가능

  ▷Last Node Tracking (마지막 노드)

  ▶Insertion

   ▷Last Node 다음에 새로운 element 저장 (key값 저장, Last Node Update)

   ▶Heap Order Restore (Upheap)

    ▷새로운 Node가 Heap order를 만족하지 않을 수 있음.

    ▷부모 노드로 가며 Swaping (key값이 부모 노드보다 작으면 Swap)

    ▷root이거나, 부모 노드보다 클 때 까지 반복

    ▷O(log(n))

  ▶Removal

   ▷Root Node의 Key를 제거

   ▷공백을 Last Node로 매꿈 (+Last Node Update)

   ▶Heap Order Restore (Downheap)

    ▷새로운 root Node가 Heap order를 만족하지 않을 수 있음.

    ▷root에서 자식 노드로 가며 Swaping (key값이 자식 노드들보다 크면 자식 중 하나와 Swap)

    ▷최대 height (log(n)) 에 도달하거나, 자식 노드들보다 작을 때 까지 반복

    ▷O(log(n))

  ▶Last Node Update

   ▷left child에 도달하거나, root에 도달할 때 까지 위로 감. (부모로 감)

   ▷left child에 도달한다면, right child로 이동

   ▷leaf까지 왼쪽 아래로 이동

   ▷O(log(n))

○Heap-sort

 ▷Heap으로 구현된 Priority Queue의 Sorting

 ▷차지하는 공간 : O(n)

 ▷Insert : O(log n)

 ▷removeMin : O(log(n))

 ▷n개의 element : O(n log(n))

○Vector-based Heap

 ▷Vector로 Heap 구현

 ▷length : n + 1인 Vector 사용 (index 0은 사용하지 않음)

 ▶Positioning : rank i의 Node에 대해

  ▷left child : rank 2i

  ▷right child : rank 2i+1

 ▷Insert(e) : rank n+1에 insert

 ▷removeMin() : rank n remove

 ▶In-place Heap Sort

  ▷1. Vector를 Heap으로 만듬

  ▷2. removeMin()하며 Sorting

●Priority Queues

 ▷우선순위의 개념으로 entry들의 집합을 저장함.

 ▷entry: key, value의 짝

 ▷위치가 아닌 우선순위를 기준으로 저장

 ▶메소드

  ▶Main Methods

   ▷Insert(e) : entry e 추가.

   ▷removeMin() : key값이 가장 작은 값(들)을 제거, return

  ▶Additional Methods

   ▷min() : 가장 작은 key를 return (지우진 않음)

   ▷size()

   ▷empty()

 ▶Total Order Relation

  ▷Key값 : 순서가 명시되는 arbitary object여야함.

  ▷다른 2개의 entry가 동일한 key를 가질 수 있다.

  ▶비교 규칙

   ▷Reflexive property (반사성) : x ≤ x

   ▷Antisymmetric property (비대칭성) : x ≤ y ∧ y ≤ x => x = y

   ▷Transitive property (이행성) : x ≤ y ∧ y ≤ z => x ≤ z

○Sequence-based Priority Queue

 ▶Unsorted List

  ▷정렬되지 않는 상태로 저장

  ▶Algorithm

   ▷Insert : O(1) - 바로 넣음.

   ▷removeMin : O(n) - 가장 작은 값 찾아야 함.

 ▶Sorted List

  ▷정렬된 상태로 저장

  ▶Algorithm

   ▷Insert : O(n) - 적절한 위치에 넣어야 함.

   ▷removeMin : O(1) - 가장 앞의 값

○Priority Queue Sorting

 ▷1. 모든 element들을 priority queue에 넣음.

 ▷2. removeMin으로 가장 작은 element부터 가져옴.

 ▶Selection Sort

  ▷Unsorted List를 이용

  ▷1. n개의 insert -> O(n)

  ▷2. n번의 removeMin -> 1+2+...n = n(n-1)/2

  ▷-> O(n²)

 ▶Insertion Sort

  ▷Sorted List를 이용

  ▷1. n개의 insert -> 1+2+...n = n(n-1)/2

  ▷2. n번의 removeMin -> O(n)

  ▷-> O(n²)

○Comparator

 ▷우선순위 비교를 위한 

 ▶isLess(p, q)

  ▷return p < q;

 ▷같다 : !isLess(p, q) && !isLess(q, p)