CS

HTTP GET vs POST

What is HTTP? HTTP(Hyper Text Transfer Protocol)는 클라이언트와 서버 간의 통신을 위해 만들어진 프로토콜이다. 클라이언트가 서버에 HTTP 요청을 보내면, 서버가 필요한 정보를 포함하여 클라이언트에게 응답하는 것이다. HTTP Methods HTTP에는 크게 9가지의 메소드가 있다. 1. GET 2. POST 3. PUT 4. HEAD 5. DELETE 6. PATCH 7. OPTIONS 8. CONNECT 9. TRACE 가장 많이 사용하는 것은 GET과 POST 메서드이다. GET GET은 지정된 리소스에서 데이터를 요청하는 데 사용된다. 요청하는 데이터가 HTTP Request Message의 Header 부분에 url 이 담겨서 전송되고, ? 뒤에 쿼리 문자열..

최소 신장 트리(Minimum Spanning Tree, MST)

신장 트리(Spanning Tree) 신장 트리란, 사이클을 형성하지 않는 그래프를 말한다. 나는 부모님의 자식이 될 수 있지만 내 형제자매의 자식은 될 수 없는 것처럼, 사이클이 없다는 것은 부모-자식 관계만 형성된다는 것이고 따라서 신장 트리는 트리의 형태를 가지고 있다. // 신장 트리의 특징 1. 그래프의 모든 정점이 간선에 의해 하나로 연결됨 2. 그래프 내에서 사이클 형성 X (첫 번째 그래프도 오른쪽으로 90도 회전시키면 트리처럼 보임) 최소 신장 트리(Minimum Spanning Tree) 가중치가 있는 그래프에서도 신장 트리를 구성할 수 있는데, 신장 트리의 모든 간선의 가중치 합이 최소인 그래프를 최소 비용 신장 트리(Minimum Cost Spanning Tree) 또는 최소 신장 ..

그래프

📈 Graph 그래프는 대표적인 비선형 자료 구조로, 정점(vertex)과 간선(edge)으로 이루어진 자료 구조이다. 트리 역시 제한된 유형의 그래프이다. 정점과 간선으로 이루어져 있지만 그래프와 달리 사이클이 없어야 한다는 특징이 있다. 모든 트리는 항상 그래프가 되지만 모든 그래프가 트리인 것은 아니다! Linked List와 Heap 역시 그래프의 특별한 경우이다. 🤷‍♀️ Undirected Graph vs Directed Graph Undirected Graph은 간선이 방향을 갖지 않는 그래프이고, Directed Graph은 간선이 방향성을 가지는 그래프이다. 📝 그래프의 표현 그래프를 표현하는 방식은 크게 두 가지 방법이 있다. 1. Adjacency Matrix(인접 행렬) 2. Adj..

Hash Table

Hash Table 해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다. 따라서 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있다. 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지고 unordered_map으로 구현한다. 해시 테이블에 데이터를 삽입하기 위해서는 저장하고자 하는 자료와 연관된 키를 생성해야 하는데 이 키를 생성하기 위한 함수를 해시 함수라고 한다. 좋은 해시 함수를 사용하면 해시 테이블에 데이터가 고르게 분포되고, 이는 충돌이 발생할 가능성이 낮다는 뜻이다. 따라서 좋은 해시 함수는 충돌을 덜 일으켜야 하고 계산이 쉬워야 한다. Hash Collision 서로 다른 두 개의 값 $i_{1}$과 $i_{2}$가 해시 테이블의 같은..

Red-Black Tree(RBT)

Red-Black Tree 레드 블랙 트리는 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 logN이다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하고, 추가된 비트는 삽입 또는 삭제의 과정에서 트리가 균형을 유지하도록 하는 데 사용된다. 대표적으로 C++ STL의 set, multiset, map, multimap 이 레드 블랙 트리를 이용하여 구현되어있다. Why Red-Black Tree? 왜 레드 블랙 트리를 사용하는 걸까? 이 이유에 대해 알기 위해서는 BST(이진 탐색 트리)의 단점부터 파악해야 한다. BST란, 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말한다. ..

Heap(Max Heap, Min Heap)

Heap 영단어 Heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 가지고 있다. 아래 그림에서도 볼 수 있듯이, 맨 아래부터 데이터를 차곡차곡 쌓아둔 모양이다. Heap은 완전 이진트리로 모든 노드가 연속적으로 존재하기 때문에 연결 리스트보다는 배열로 구현하는 것이 효율적이다. 또한 heap은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같은 자료구조이다. 즉, 루트 노드에 저장된 값이 가장 커야 한다. 이처럼 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진트리를 최대 힙(Max Heap)이라고 한다. 이와 반대로, 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리인 최소 힙(Min Heap)도 존재한다. 최소 힙은 특히 shortest job first를 구현할때..

Tree(Binary Tree, 포화 이진 트리, 완전 이진 트리, BST)

Tree 트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고 트리 구조로 배열된 일종의 계층적 데이터의 집합이다. 따라서 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 자료를 저장하는 것이 목표라기보다는, 자료 간의 관계를 표현하는 것이 더 우선인 자료구조라고 볼 수 있다. Tree의 특징 1. 부모/자식 계층 구조를 가진다. 2. V - 1 = E (노드 수 - 1 = 간선 수) 모든 노드가 자신의 부모 노드와 연결된 간선을 가지고 있는데 루트 노드는 부모 노드가 없기 때문에 간선이 하나 부족하다. 3. 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내에서 특정 노드와 특정 노드까지의 경로는 반드시 존재한다. Tree의 구성요소 1. Node(노드) ..

Stack & Queue

🍡 Stack 스택은 가장 마지막에 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료구조이다. 스택에 원소를 삽입할때는 그냥 마지막 위치에 올리기만 하면 되므로 O(1)이 걸리고 원소를 검색할 때는 원하는 값이 나올 때까지 마지막 원소부터 하나씩 제거해봐야 하기 때문에 최악의 경우 O(n)이 걸린다. 📌 Stack의 구현 Stack의 구현 방법은 두 가지가 있다. 1. Array 기반 2. Linked List 기반 Array와 Linked List 자체가 이미 하나의 자료구조이지만, 이 자료구조를 사용해서 Stack이라는 자료구조를 구현할 수 있는 것이다. Array를 기반으로 구현한 스택과 Linked List 기반으로 구현한 스택 모두 각각의 장단..