리스트 : 콘텐츠가 있으면 최근 5건을 불러옵니다.
-
[자료구조] C++ HashTable 구현자료구조,알고리즘 2022.11.11 16:16
#pragma once #include #include class HashNode { private: std::string m_Key; int m_Value; HashNode* m_Next; public: HashNode() : m_Next(nullptr) { } HashNode(const std::string& key, int val) : m_Key(key), m_Value(val), m_Next(nullptr) { } HashNode* GetNext() { return m_Next; } void SetNext(HashNode* node) { m_Next = node; } const std::string& GetKey() const { return m_Key; } int GetValue() const ..
-
[알고리즘] 병합 정렬 (Merge Sort)자료구조,알고리즘 2022.11.04 18:21
01. 병합 정렬의 개념 안정 정렬이다. 정렬을 위한 별도의 공간이 필요하다. 분할 정복 알고리즘이다. 주로 순환 호출로 구현 매우 빠른 속도를 보장 ( O(NlogN) ) 02. 과정 설명 배열을 반으로 나누는 것을 반복한다. 사이즈 1짜리 배열까지 나누고 나면, 나눈 순서의 역순으로 정렬해가며 부분 배열을 합친다. 말로는 사실 설명할 게 별로 없다... 그림으로 보는 게 더 설명이 쉬울 듯 하여 첨부 03. C++ 코드 void Merge(int*& arr, int*& tmp, int left, int right) { if (left == right) return; int l = left; int mid = (l + right) / 2; int midIdx = mid + 1; int idx = l; ..
-
꼬리 재귀 (Tail Recursion)자료구조,알고리즘 2022.11.03 17:19
1. 꼬리 재귀 재귀 호출이 끝나면 아무것도 하지 않고 리턴하는 방법 컴파일러 최적화에 의해 재귀 호출이 깊어져도 스택 프레임이 쌓이지 않고 재사용하기 때문에 빨라진다. 2. 예시 int Factorial(int n) { if (n == 1) return 1; return n * Factorial(n - 1); } int FactorialTail(int n, int acc = 1) { if (n == 1) return acc; return FactorialTail(n - 1, n * acc); } 팩토리얼을 구하는 함수를 재귀방식, 꼬리 재귀 방식으로 작성해 보았다. 위 함수는 return statement에서 n * Factorial(n-1) 에 의해 재귀 호출을 빠져나가는 과정에서 * 연산을 해 주어..
-
[알고리즘] 퀵 정렬 (Quick Sort)자료구조,알고리즘 2022.11.03 12:35
01. 퀵 정렬의 개념 불안정 정렬이며, 다른 원소와의 비교를 통해 정렬하는 비교 정렬 분할 정복 알고리즘이다. 매우 빠른 속도를 보장 ( O(NlogN) ) 주로 순환 호출로 구현 02. 과정 설명 오름차순으로 정렬한다고 가정한다. 리스트 안에 있는 한 요소를 선택 (보통 맨 앞의 원소), 이를 Pivot이라고 한다. 피벗을 기준으로, 피벗보다 작은 요소들을 모드 왼쪽으로 옮기고 피벗보다 큰 요소를 오른쪽으로 옮긴다. 피벗을 제외한 왼쪽, 오른쪽 요소들을 각각 따로 정렬한다. 나눠진 부분들이 더 이상 분할이 불가능 할 떄까지 반복 03. 자세한 설명 배열에 [4, 6, 3, 2, 8, 7, 9, 1, 0, 5] 가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬한다. 초기 상태에서 pivot을 0번 ..
-
IOCP방식의 TCP 기반 채팅 서버/클라이언트DevLog 2022.10.26 12:51
01. 구동 영상 02. 주요 구현 내용 IOCP 구현 서버가 다수의 클라이언트를 관리하는 과정에서의 임계영역 동기화를 위한 Ciritical Section 사용 클라이언트는 전송/수신 스레드로 나누어 멀티스레드로 구현 03. 후기 다수의 스레드가 Blocked상태로 대기하다가, IO Complete 이벤트가 발생하면 처리하는 IOCP를 이해할 수 있었다. 비동기 IO와 Overlapped IO에 대해 이해할 수 있었다. 동기 IO보다 좋은 점은 Write/Recv해놓고 다른 걸 처리할 수 있다는 점? 하지만 IO 상태를 확인해야 한다는 점에서 코드가 복잡해지는 느낌 하나의 소켓당 하나의 스레드를 할당하는 방식보다 적게 스레드를 사용하고도 효율적으로 처리할 수 있을듯 하다. Select방식과 비교해보면,..