'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 |
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 |
이진탐색
이진탐색이란 한 번 비교를 거칠 때마다 탐색 범위가 반(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 |
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 |
우선 쉽게 설명하겠습니다.
비동기(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 |