분류 전체보기
-
[자료구조] C++ HashTable 구현Study/자료구조,알고리즘 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)Study/자료구조,알고리즘 2022. 11. 4. 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)Study/자료구조,알고리즘 2022. 11. 3. 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)Study/자료구조,알고리즘 2022. 11. 3. 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방식과 비교해보면,..
-
그리디 알고리즘 (Greedy Algorithm)코딩 테스트/코딩 테스트 알고리즘 2022. 10. 26. 12:03
01. 그리디 알고리즘이란? 현재 상황에서 가장 좋은 것만 고르는 방식이다. 탐욕법이라고도 한다. 사전에 특정 알고리즘을 공부하지 않아도 풀이를 떠올릴 수 있는 경우가 많다. 02. 그리디 알고리즘의 예시 : 거스름돈 문제 내가 가게의 계산 직원이라고 생각했을 때, 거스름돈이 500원, 100원, 50원, 10원 단위로 있다고 생각하자. 손님에게 거슬러 줘야 할 돈이 N원일 때, 가장 적은 동전을 써서 거슬러줄 수 있는 경우는? 전형적인 그리디 알고리즘의 예시 "가장 큰 화폐 단위부터" 돈을 거슬러 주면 됨 1370원을 거슬러 줘야 한다고 가정할 때 가장 큰 단위인 500원을 2번 거슬러 준다. (남은 돈 370원) 두 번째 큰 단위인 100원을 3번 거슬러 준다 (남은 돈 70원) 세 번째 큰 단위인 ..
-
[알고리즘] 카운팅 정렬(Counting Sort)Study/자료구조,알고리즘 2022. 10. 21. 12:28
1. 특징 원소간 비교를 수행하지 않는 정렬이다. 모든 원소는 양의 정수여야 함 시간 복잡도는 O(n+k), k는 정렬할 배열의 최대값이다. 공간 복잡도는 O(n+k), 정렬을 위한 배열 하나, 카운팅을 위한 배열 하나가 필요하다. 2. 과정 입력 자료 input을 탐색하여 최대값 k를 구한다. k + 1 사이즈의 배열 counts를 생성한다. input을 순회하며, 등장하는 수의 빈도를 기록한다.. (input의 원소가 3이라면, counts[3]에 +1) 0이 1번, 2가 5번 등장하는 배열이라면, counts배열은 [1, 0, 0, 5]가 될 것 input을 순회하며 누적합을 구한다. 오름차순 정렬의 경우, 이전 값 (i-1)을 i에 더한다. 내림차순 정렬의 경우, input의 뒤쪽부터 시작해서, ..
-
[알고리즘] Bubble Sort와 Selection Sort 시간 비교Study/자료구조,알고리즘 2022. 10. 20. 13:25
Bubble Sort와 Insertion Sort를 구현, 시간을 비교해봤다. Bubble Sort void BubbleSort(const vector& input) { cout out[j - 1]) { swap(out[j], out[j - 1]); } } } chrono::duration sec = chrono::system_clock::now() - start; for_each(out.begin(), out.end(), print_vec); cout