CS

동기-비동기, 블로킹-논블로킹

이 두가지 개념은 서로 전혀 다른 곳에 초점을 맞춘 별개의 개념들이므로 서로 직접적인 관련은 거의 없다고 봐도 됩니다. 동기(sync) / 비동기(async)는 행위에 관한 개념 - 프로세스의 수행 순서에 관한 매커니즘 블럭(block) / 논블럭(non-block)은 함수 호출에 관한 개념 - 프로세스의 제어권에 관련된 매커니즘 - 제어권 : 제어권은 자신(함수)의 코드를 실행할 권리 같은 것이다. 제어권을 가진 함수는 자신의 코드를 끝까지 실행한 후, 자신을 호출한 함수에게 돌려준다. - 결과값을 기다린다는 것 : A 함수에서 B 함수를 호출했을 때, A 함수가 B 함수의 결과값을 기다리느냐의 여부를 의미한다. Blocking / Non-Blocking이 현재의 작업 상태에 따라 동작이 결정되는것이라..

Cookie vs Session vs JWT (With JWT 사용시 주의할 점)

Session vs Cookie vs JWT HTTP의 특성 HTTP는 인터넷 상에서 데이터를 주고 받기 위한 서버/클라이언트 모델을 따르는 프로토콜이다. HTTP는 요청에 대한 응답을 처리하게 되면 연결을 끊어 버리는 비연결성(connectionless) 및 무상태성(stateless) 이라는 특징을 가지고 있다. 서버가 다수의 클라이언트와 연결을 계속 유지한다면, 이에 따른 자원 낭비가 심해지지만, 비연결성 및 무상태성의 특징을 가진다면 불필요한 자원 낭비를 줄일 수 있다는 장점이 있다. 그러나 비연결성 및 무상태성의 단점은 서버는 클라이언트를 식별할 수 없다는 단점이다. Cookie와 Session은 비연결성 및 무상태성 특징을 보완한 기술이다. 기본적으로 HTTP 프로토콜 환경은 "connecti..

CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘 CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다. 프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다. CPU 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게 준비 큐(ready queue)에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것을 목표로 한다 즉 CPU 스케줄링 알고리즘의 목표는 상황에 맞게 CPU를 어떤 프로세스에 배정하여 효율적으로 처리하는방법 오버헤드를 낮추고, 사용률을 높히고, 응답시간은 짧게, 기아현상을 낮추는것이 목표 비선점형 방식 비선점(Non-Preemptive) : 프로세스가 CPU를 점유하면 I/O나 인터럽트 발생 또는..

동시성과 병렬성 (Concurrency vs Parallelism)

동시성과 병렬성 (Concurrency vs Parallelism) 동시성(Concurrency) 과 병렬성(Parallelism)을 위키에서는 다음과 같이 정의한다. Concurrent computing is a form of computing in which several computations are executed concurrently. Parallel computing is a type of computation where many calculations or the execution of processes are carried out simultaneously. Concurrent computing 은 여러 계산이 동시에 실행되는 컴퓨팅의 한 형태이다. Parallel computing 은 ..

[자료구조] 해시, 해시테이블

해시(Hash) 해시란? 해시(Hash) 함수, 또는 해시 알고리즘은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑, 변환 해주는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드 등인데 간단하게 해시라고한다. 즉 해시(hash)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다 해시 함수?(Hash Function) 데이터를 효율적으로 관리하기 위해, 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수입니다. 암호 알고리즘에는 키가 사용되지만, 해시 함수는 키를 사용하지 않으므로 같은 입력에 대해서는 항상 같은 출력이 나오게 됩니다. 해..

[자료구조] 그래프와 DFS, BFS

그래프(Graph) 그래프란 정점(Vertex)과 간선(Edge)로 이루어진 자료구조이다. 트리 또한 그래프이며, 트리는 사이클이 허용되지 않고, 그래프는 사이클이 허용된다. 사이클 : 그래프의 특정 정점에서 출발하여 돌아다니다가 다시 처음 출발했던 곳으로 되돌아 갈 수 있으면 사이클이 있다고 한다. 그래프 용어 정점 (Vertext, V) : 노드 라고도 하며 데이터가 저장되는 그래프의 기본 원소 간선 (Edge, E) : 정점(V, Node)를 연결하는 선, link, brach 라고도 부름 인접 정점 (adjacenct vertex, adj) : 간선에 의해 연결된 정점(그림 0, 3 등 이어진 정점) 단순 경로 (simple path) : 경로 중에서 반복되는 정점이 없는 경우. 동일한 간선을 지..

[자료구조] Heap 힙, 우선순위 큐

힙(Heap) 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. 힙에는 두가지 종류가 있다. 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 : 최대 힙(Max Heap) 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 : 최소 힙(Min Heap) 우선 순위 큐(Priority queue)를 위해서 만들어졌다. - 힙 자체가 우선순위 큐이다. 큐는 FIFO(First In First Out, 선입선출) 자료구조인데, 우선순위큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다. Queue의 시간 복잡도는 enqueue = O(1), dequeue O(1) 이고 Priority queue 의 시간 복잡도는 push(삽..

[자료구조] 트리, B Tree, B+Tree

B Tree & B+ Tree 검색을 위한 자료구조중에서 이진트리는 한 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형(O(n)) 급으로 떨어지지만, 균형이 잘맞으면 성능이 O(log N) 수준으로 보이는 장점이 있어 이를 바탕으로 개선하고자 하는 자료구조들이 나왔습니다. B Tree는 이진트리를 확장해서 더 많은수의 자식을 가질 수 있고, 균형이 맞지 않는 편향트리가 되지 않도록 균형을 맞추는 구조를 갖고 있습니다. 데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종입니다. 단순하고 효율적이며 레벨로만 따지면 완전히 균형을 맞춘 트리입니다. 대량의 데이터를 처리할 때 하나의 노드에 많은 데이터를 가질 수 있으므로 큰 장점을 갖고 있습니다. B Tree의 규칙..

[자료구조] 트리, AVL 트리

AVL Tree (AVL은 발명자 세명의 이름에서 따왔다) 자가 균형 이진 탐색 트리. 이진 탐색 트리에서, 노드들이 삽입시 한쪽으로 편향되면 결국 탐색에서 O(N)의 시간이 걸리게 된다. * 그림 : 편향트리. 이진 탐색 트리의 편향트리를 극복하기 위해 재구성(회전, Rotate)을 통해 트리를 균형있게 만든다. AVL 트리는 다음과 같은 특징을 가진다. 이진 탐색 트리(BST)의 속성을 가진다. 왼쪽, 오른쪽 서브 트리의 높이차이가 최대 1이다. 삽입, 삭제 등 어떤 시점에서 높이 차이가 1보다 커지면 회전(Ratation)을 통해 균형을 맞춰 높이를 1로 맞춘다. AVL 트리는 높이를 logN으로 유지하기 떄문에 삽입, 검색 ,삭제의 시간 복잡도는 O(log N) 이다. AVL 트리는 균형이 무너졌..

[자료구조] 트리, 레드블랙 트리 (Red-Black-Tree)

Red-Black Tree Binary Search Tree를 기반으로 하는 자료구조. 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어. 연산 삽입 insert : O(lon N) 조회 search : O(log N) 삭제 delete : O(log N) 정의 레드 블랙 트리는 다음의 성질들을 만족하는 BST(이진 탐색 트리) 이다. 모든 노드는 Red(빨강) or Black(검정) 의 색을 갖는다. 루트 노드는 검정색이다. 모든 리프 노드들은 검정색이다. 레드 노드의 자식은 모두 검정색이다 모든 리프 노드에서 Black Depth는 같다. 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 각 노드에 대해서 노드로부터 descendan..