Application Layer → Transport Layer → Network Layer, 또는 Network Layer → Transport Layer → Application Layer 의 과정에서 Transport Layer에 해당하는 내용이다. Multiplexing(sender측) Application Layer(socket을 통해)에서 받은 데이터를 segment로 나눈다. 데이터에 port 정보와 header 정보를 추가하여 Network Layer로 내려 보낸다. Transport Layer → Network Layer Demultiplexing(receiver측) port 정보와 IP주소를 통해 올바른 Application Layer(socket)을 찾는다. Application La..
Termination의 종류 TCP는 두 가지 연결 해제 방식이 있다. 4-Way Handshake를 통한 연결 해제 RST(Reset)을 통한 연결 해제 4-Way Handshake 연결 종료는 양쪽 호스트 모두 먼저 시도할 수 있다. 편의를 위해 양 쪽 Host를 각각 클라이언트, 서버라고 부르고 설명한다. 연결을 먼저 요청하는 Host ⇒ 클라이언트 연결을 요청받는 Host ⇒ 서버 실제로 TCP는 양방향 통신이기에 ‘클라이언트-클라이언트’의 형태가 존재한다. 4-Way-Handshake 에서 사용되는 TCP 헤더 필드 Sequence Number Segment에 있는 첫 번째 바이트의 바이트 스트림 번호다. TCP는 데이터를 단지 순서대로 정렬되어 있는 바이트 스트림으로 본다. ex) 0~999,..
암호화 알고리즘 암호를 만드는 알고리즘이다. 용어 평문(Plaintext) : 해독 가능한 형태의 메시지(암호화 전 메시지) 암호문(Cipertext) : 해독 불가능한 형태의 메시지(암호화된 메시지) 암호화(Encryption) : 평문을 암호문으로 변환하는 과정 복호화(Decryption) : 암호문을 평문으로 변환하는 과정 전자서명 송신자의 Private Key로 메시지를 서명하여 전달 수신자측에서는 송신자의 Public Key를 이용하여 서명값을 검증 양방향 암호화 암호화와 복호화과정을 통해 송,수신간 주고받는 메시지를 안전하게 암,복호화하는 과정 단방향 암호화 해싱(Hashing)을 이용한 암호화 방식으로 양방향과는 다른 개념이다. 평문을 암호문으로 암호화는 가능하지만 암호문을 평문으로 복호화 ..
Thread Safe Multi-Thread 상황에서 함수, 변수, 객체에 동시 접근이 발생해도 프로그램 실행에 문제가 되지 않는것을 의미한다. Java에서 Thread Safe를 유지하는 방법을 알아보았다. 1. Confinement(제한) 지역 변수는 각 스레드의 자체 스택에 저장되고, 스택은 고유한 영역으로 동시 접근이 발생하지 않는다. 사용 예시 public class Factorial { private static void computeFact(final int n) { BigInteger result = new BigInteger("1"); for (int i = 1; i
MST(Minimum Spanning Tree 최소 신장 트리) 신장 트리 : 모든 정점이 연결된 그래프, 사이클이 존재하지 않아야 한다. n개의 점을 (n-1) 개의 간선으로 연결한다. 최소 신장 트리 : 신장 트리 중 간선 가중치의 합이 가장 작은 신장 트리를 의미한다. Prim(프림) 알고리즘 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법이다. 수행 과정 임의의 정점을 시작 지점으로 선택 연결된 모든 간선의 가중치를 비교 가장 작은 무게의 간선 선택(사이클이 만들어지지 않도록) 모든 정점이 연결될 때까지 2~3번 과정 반복 시간복잡도 V : 정점의 개수 E : 간선의 개수 우선순위 큐로 구현 우선순위 큐 생성 작업 : O(logV) * O(E) = O(ElogV) 각 노드에서..
재귀함수(Recursion) Stack 개념을 이용해 자기 자신을 다시 호출하며 반복하는 함수이다. 구성 탈출 조건, 연산, 재귀 호출로 이루어진다. 탈출 조건을 잘못 설정하면 Stack Overflow가 발생한다. public static int rSum(int n){ // 탈출 조건 if(n == 0) return 0; // 재귀 호출 return n += rSum(n-1); } 장점 가독성을 높일 수 있다.(재귀적인 표현이 자연스러운 경우) 단점 호출이 많아질수록 Stack에 쌓여 메모리 사용량이 계속 증가한다. Stack Overflow가 발생할 수 있다. 재귀함수 사용 예시 피보나치 수열, 팩토리얼 구하기 분할 정복 알고리즘 이진 탐색 하노이의 탑 백트래킹 알고리즘 Tail Recursion(꼬..
그리디 알고리즘(Greedy Algorithm) 다음 단계를 생각하지 않고, 현재 단계에서 가장 최선을 선택하는 기법이다 조건 탐욕 선택 속성(Greedy Choice Property) 이전의 선택이 이후에 영향을 주지 않음 최적 부분 구조(Optimal Substructure) 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다 특징 전체 상황에서의 최적의 결과를 보장하지 못한다. 속도가 매우 빠르다 사용 예시 : 거스름돈, 활동 선택(Action Selection) 문제 등 동적 계획법(Dynamic Programming) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용 조건 겹치는 부분 문제(Overlapping Subproblems)..
Binary Search(이진탐색) 정렬된 배열, 이진 트리에서 특정한 값을 찾아내는 알고리즘이다. 정렬이 전제되어 있어야 한다. 한번 비교를 거칠 때 탐색 범위가 1/2로 줄어든다. 범위의 중앙 값과 비교한다. 찾는 값이 중앙 값보다 작다면 왼쪽(그림 : 내림차순 정렬이므로 오른쪽) 1/2의 범위에서 탐색한다. 찾는 값이 중앙 값보다 크다면 오른쪽(그림 : 내림차순 정렬이므로 왼쪽) 1/2의 범위에서 탐색한다. 1번/2번 해당하는 작업을 반복한다. 찾는 값이 중앙 값이면 탐색을 종료한다. 기본 형태의 Java 코드 int BinarySearch(int dataArr[], int size, int findData) { int low = 0, high = size - 1, mid; // high가 low보..
Heap(힙) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 💡 완전 이진 트리 : 이진 트리의 일종으로, 자식은 왼쪽부터 연결한다. (왼쪽 자식이 없으면서 오른쪽 자식이 존재할 수 없다) 일종의 반정렬 상태를 유지한다. 부모와 자식간에 정렬된 상태지만, 형제 노드간의 정렬은 이루어지지 않은 상태다. 중복된 값을 허용한다. (이진 탐색트리는 중복허용 X) 힙 종류 최대 힙(Max Heap) 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리 최소 힙(Min Heap) 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리 힙 구현 일반적으로 배열을 사용한다.(연결 리스트로 구현할 수도 있긴 하다.) 구현의 편의성을 위해 0번 인덱스는 사용하지 않는다. 일정한 규칙을 유지한다...
Stack(스택) 삽입(push)과 삭제(pop)이 한쪽 끝(top)에서만 일어나는 자료구조다. top : 가장 상단에 위치한 원소를 가리키는 용어 push() : top 위치에 데이터를 삽입하는 기능 시간복잡도 : O(1) 용량이 꽉 찬 스택에 push()를 시도하면 Stack Overflow 에러가 발생한다. pop() : top 위치의 데이터를 삭제/반환 하는 기능 시간복잡도 : O(1) 데이터가 없는 스택에 pop()을 시도하면 Stack Underflow 에러가 발생한다. 특징 후입선출 LIFO(Last In First Out) 특정 데이터를 찾기 위해서는 해당 값을 찾을 때 까지 pop()을 반복해야 한다 - O(N) JAVA 에서는 Stack 라이브러리를 제공한다. Queue(큐) 삽입(en..
