Internal Fragmentation(내부 단편화) Partitioning 상황에서 발생한다. Partition의 크기가 프로세스의 크기보다 커서 메모리가 남지만, 다른 프로세스가 사용할 수 없는 상태를 말한다. 100MB의 공간(Partition)에 Process C를 할당했다. 20MB의 여유 메모리가 존재하지만 Process C 에게 할당되어 사용할 수 없다. 이를 내부단편화라고 한다. External Fragmentation(외부 단편화) 남아있는 메모리의 크기가 실행하고자 하는 프로세스보다 크지만, 연속적이지 않은 공간에 존재하여 실행하지 못하는 현상을 의미한다. 50MB의 두 여유 메모리가 존재하고 총 100MB의 여유 메모리가 존재한다. 그러나, 연속적이지 않은 공간에 존재하여 80MB인..
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,..
3-Way Handshake TCP/IP 프로토콜을 이용해서 통신하는 응용프로그램은 데이터를 주고받기 전에 먼저 연결을 진행한다. 3-Way Handshake는 이 연결 과정을 의미한다. 편의를 위해 양 쪽 Host를 각각 클라이언트, 서버라고 부르고 설명하겠다. 연결을 먼저 요청하는 Host ⇒ 클라이언트 연결을 요청받는 Host ⇒ 서버 실제로 TCP는 양방향 통신이기에 ‘클라이언트-클라이언트’의 형태가 존재한다. 3-Way-Handshake 에서 사용되는 TCP 헤더 필드 Sequence Number Segment에 있는 첫 번째 바이트의 바이트 스트림 번호다. TCP는 데이터를 단지 순서대로 정렬되어 있는 바이트 스트림으로 본다. ex) 0~999, 1000~1999의 Segment를 보낼 때 s..
암호화 알고리즘 암호를 만드는 알고리즘이다. 용어 평문(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보..
