게임 개발자 지망생의 개발로그 게임 개발자 지망생의 개발로그

Study/자료구조,알고리즘

• [자료구조] 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 ..

  Read More
• [알고리즘] 병합 정렬 (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; ..

  Read More
• 꼬리 재귀 (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) 에 의해 재귀 호출을 빠져나가는 과정에서 * 연산을 해 주어..

  Read More
• [알고리즘] 퀵 정렬 (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번 ..

  Read More
• [알고리즘] 카운팅 정렬(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의 뒤쪽부터 시작해서, ..

  Read More
• [알고리즘] 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

  Read More
• [자료구조] 이진 탐색 트리 (Binary Search Tree)

  Study/자료구조,알고리즘 2022. 9. 22. 15:59

  01. 이진 탐색 트리란? 이진 탐색 트리는 이진트리 기반의, 탐색을 용이하게 하기 위한 자료구조 탐색을 위한 키 값 기준으로 정렬된다. 이진 탐색 트리의 정의는 다음과 같다. 1. 모든 노드는 유일한 키를 갖는다. 2. 왼쪽 서브트리의 키는 루트의 키보다 작다. 3. 오른쪽 서브트리의 키는 루트의 키보다 크다. 4. 왼쪽과 오른쪽 서브트리도 이진트리이다. 02. 이진 탐색 트리의 연산 이진 탐색 트리는 삽입, 삭제 과정에서 이진트리의 특성을 유지해야 한다. 탐색 탐색 연산은 키 값 비교를 통해 왼쪽과 오른쪽 노드를 탐색할지 결정한다. 찾고자 하는 키 값과 현재 노드의 키 값이 일치한다면 탐색 성공 찾고자 하는 키가 현재 노드보다 작다면, 왼쪽 노드로 이동해 다시 탐색한다. 찾고자 하는 키가 현재 노드보..

  Read More
• [C++ 쉽게 풀어쓴 자료구조] 프로그래밍 프로젝트 8

  Study/자료구조,알고리즘 2022. 9. 20. 15:43

  완전 이진트리 검사 함수 구현 완전 이진트리란 높이n 의 트리에서 n-1레벨까지는 포화상태, n레벨의 노드들은 왼쪽부터 채워져 있는 상태인 이진트리를 의미한다. 완전 이진트리 검사는 레벨 순회를 통해 구현했다. Left와 Right중 하나라도 null node일 경우, 그 이후 나타나는 노드들은 모든 노드가 단말노드여야 한다. bool CBinaryTree::IsFull() { std::queue bQueue; bQueue.push(m_Root); while (!bQueue.empty()) { bool meetNotFull = false; CBinaryNode* node = bQueue.front(); // full node라면 계속 탐색한다. if (node->GetLeft() && node->GetR..

  Read More