'2015/10'에 해당되는 글 4건

  1. 2015.10.26 Java finalize
  2. 2015.10.16 이진탐색(Binary Search)
  3. 2015.10.06 TCP Three-way Hand Shaking
  4. 2015.10.06 동기 vs 비동기

Java finalize

JAVA 2015. 10. 26. 01:42


'JAVA' 카테고리의 다른 글

Commons DBCP  (0) 2015.11.07
자바 classpath  (0) 2015.11.03
Call By Value vs Call By Reference  (0) 2015.09.14
List, Map, Set - Collection  (0) 2015.08.29
자바 8 특징  (0) 2015.08.29
Posted by slender ankles
,

이진탐색

이진탐색이란 한 번 비교를 거칠 때마다 탐색 범위가 반(1/2)으로 줄어드는 탐색 방법입니다. 순차탐색에 비해 얼마나 빠른 알고리즘이냐면 70억 명 중에서 특정한 정보를 탐색하려 할 때, 순차 탐색은 평균적으로 35억 번을 비교하고, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있다.


이진 탐색 과정

1~7까지 정렬되어 있는 수에서 5를 찾는 과정이다.

1~7까지의 정렬된 수가 주어짐

1) mid 값 = (0 + 6) / 2 = 3 

[3]의 값인 4보다 찾고자 하는 값이 큼

2) 인덱스 4~6까지 검색, mid값 = 5

[5]의 값인 6보다 찾고자하는 값이 더 작음

3) 4 ~4까지 검색, mid 값 = 5

찾고자하는 값을 찾음


총 3번의 비교 연산이면 원하는 값을 찾을 수 있음!


이진 탐색의 성능

데이터 집합의 크기를 n으로 두고, 반복 횟수를 k로 둔다면 아래와 같은 수식이 만들어 진다.

n x (1/2)k = 1

n x 1/2k = 1

n = 2k

k = log2n


이진 검색의 구현

Iterative한 구현

    public static int binarysearch(int[] arr, int target){
        int low = 0, high = arr.length - 1;
        while(low <= high){
            int mid = (low + high) / 2;
            if(target < arr[mid]){
                high = mid - 1;
            }
            else if(target > arr[mid]){
                low = mid + 1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
cs


recursive한 구현

    public static int binarysearch(int[] arr, int left, int right, int target){
        // 예외 처리(target값이 arr에 아예 없는 경우)
        if(right < left){
            return -1;
        }
        int mid = (left + right) / 2;
        if(target < arr[mid]){
            return binarysearch(arr, left, mid - 1, target);
        }
        else if(target > arr[mid]){
            return binarysearch(arr, mid + 1, right, target);
        }
        else{
            return mid;
        }
    }
cs







'알고리즘' 카테고리의 다른 글

최소 비용 스패닝 트리 - kruskal 알고리즘  (0) 2015.11.20
최소 비용 스패닝 트리 - Prim알고리즘  (0) 2015.11.20
쉘 정렬  (0) 2015.09.26
퀵정렬  (0) 2015.09.26
삽입정렬  (0) 2015.09.26
Posted by slender ankles
,

TCP Three-way HandShaking 이란?

클라이언트와 서버가 통신하기 전 세 번의 패킷 교환을 통해 확인하는 과정을 말합니다.


TCP Three-way HandShaking의 과정



- CLIENT에서 웹 서버로 연결을 최초시도시 먼저 SYN 패킷을 보냅니다.

- SYN 패킷을 보낸 CLIENT는 SYN-SENT 상태가 됩니다.

- SERVER에서 CLOSED는 PORT가 닫혀있는 상태를 뜻하고, 포트가 서비스 가능한 상태인 LISTEN상태로 만들어주어야 합니다.

- LISTEN상태에서 CLIENT로부터 SYN패킷을 받으면 이에 대한 응답으로 SYN + ACK 패킷을 CLIENT로 보냅니다.

- SERVER는 CLIENT IP에 대해 포트 SYN-RECEIVED 상태로 전환됩니다.

- SERVER로부터 SYN+ACK 패킷을 받으면, CLIENT는 ESTABLISHED상태로 변하게 되면서 연결을 확인합니다.

- CLIENT는 SERVER로 SYN에 대한 응답으로 ACK패킷을 보냅니다.

- SERVER는 이 ACK 패킷을 받고 해당 CLIENT IP에 대한 포트 ESTABLISHED상태로 전환됩니다.

- 이로써 SERVER와 CLIENT의 TCP 3-WAY HandShaking 과정을 마치게 됩니다.


Code Bit(TCP Header)

TCP Header에는 Code Bit라는 항목이 있습니다. 이는 6bit로 되어있으며 각각의 bit는 의미를 가지고 있습니다.

URG - ACK - PSH - RST - SYN - FIN 순서로 되어 있으며 해당 위치의 비트에 1이 들어가게 되면 이 패킷의 어떤 패킷인가를 알려주게 됩니다. 즉 000010이라고 하면 SYN 패킷이 되는 겁니다.


Sequence Number

Sequence Number과 Acknowledgemnet Number이 있는데 TCP가 패킷을 주고 받을 때 순서와 Date와 관련됩니다. 

여기서 간단하게 설명하자면, 최초 TCP 3-way HandShaking과정을 Sequence Number과 Acknowledgement Number로 나타내겠습니다.

처음 클라이언트에서 SYN패킷을 보낼 때 Sequence Number(A)에 랜덤으로 숫자를 넣어서 보냅니다. 

여기서는 1이라고 하겠습니다. 서버가 이 SYN패킷을 받게 되면 응답으로 SYN+ACK패킷을 보내게 되는데, 

서버에서 보내는 Sequence Number(B)의 경우 또 랜덤의 숫자를 보내게 됩니다. 

여기서는 편의상 70이라고 하겠습니다. Acknowledgement Number의 경우, 앞 클라이언트에서 보내온 

SYN패킷의 Sequence Number에다 +1을 하여 보내게 됩니다.(A+1). 

즉 여기서는 Sequence Number가 2가 됩니다. 마지막으로 클라이언트에서 서버로부터 오는 

SYN + ACK를 받고 응답으로 ACK 패킷을 보내게 되는데 이때 서버에서 받은 Sequence Number에다 + 1을 

하여 보냅니다.

(B+1) 즉 71이라는 숫자를 Sequence Number로 보내게 됩니다.


참조 : http://cafe.naver.com/nsis/41903




'네트워크' 카테고리의 다른 글

동기 vs 비동기  (0) 2015.10.06
빅 엔디안(Big Endian) vs 리틀 엔티안(Little Endian)  (0) 2015.09.14
GET방식 과 POST방식  (0) 2015.08.08
HTTP 와 HTTPS  (0) 2015.08.08
HTTP 프로토콜  (0) 2015.08.08
Posted by slender ankles
,

동기 vs 비동기

네트워크 2015. 10. 6. 13:50

우선 쉽게 설명하겠습니다.

비동기(Asynchronous)

우선 비동기란 말 그대로 동시에 일어나지 않는다는 의미입니다. 무엇이 같이 일어나지 않는 것일까? 바로 요청과 결과가 동시에 일어나지 않을 것이라는 약속입니다. 즉 요청한 즉시 응답해주는 것이 아니라 이따가라도 줄께라는 의미입니다.

동기(Synchronous)

동기란 말 그대로 동시에 일어난다는 의미입니다. 무엇이 같이 일어나는 것인가? 바로 요청과 결과가 동시에 일어난다는 약속입니다. 즉 요청한 즉시 응답해준다는 것입니다.




'네트워크' 카테고리의 다른 글

TCP Three-way Hand Shaking  (0) 2015.10.06
빅 엔디안(Big Endian) vs 리틀 엔티안(Little Endian)  (0) 2015.09.14
GET방식 과 POST방식  (0) 2015.08.08
HTTP 와 HTTPS  (0) 2015.08.08
HTTP 프로토콜  (0) 2015.08.08
Posted by slender ankles
,