개발 일기장

#include #include #include #include #include using namespace std; // 동적 계획법 (DP) // memoization int cache[50][50]; // n개에서 r개를 추출할 경우의 수를 계산하는 함수 int combination(int n, int r) { // 0개를 뽑을 경우 및 n개에서 n개를 뽑을 경우 경우의 수는 1개이다. if (r == 0 || n == r) return 1; // 이미 답을 구한 적 있으면 바로 반환 int& ret = cache[n][r]; if (ret != -1) return ret; // 새로 답을 구해서 캐시에 저장 return ret = combination(n - 1, r - 1) + combinati..

void Board::GenerateMap_Prim() { struct CostEdge { int cost; Pos vtx; bool operator< (const CostEdge& other) const { return cost < other.cost; } }; for (int32 y = 0; y < _size; y++) { for (int32 x = 0; x < _size; x++) { if (x % 2 == 0 || y % 2 == 0) _tile[y][x] = TileType::WALL; else _tile[y][x] = TileType::EMPTY; } } //edges[u] : u 정점과 연결된 간선 목록 map edges; for (int32 y = 0; y < _size; y++) { fo..

#include #include #include #include using namespace std; /* Kruskal 알고리즘 스패닝 트리-간선의 수를 최소화(사이클이 생기면 안된다)해서, 모든 정점을 연결한다. N개의 정점을 N-1개의 간선으로 연결 ex) 통신 네트워크 구축 -> 실용성이 있을려면, 비용을 최소화 해야한다. 크루스칼 MST 알고리즘 - 탐욕적인(Greedy) 방법을 이용 - 지금 이 순간에 최적인 답을 선택하여 결과를 도출하자. - 모든 길을 확인하고, 최저 비용을 먼저 연결시킨다. - 노드간에 길이 안뚤린 곳이 있으면, 다시 최저 비용을 확인하고 연결시킨다. - 순환이 되지 않도록 항상 주의한다. -> 순환이 되는 노드들을 하나의 묶음으로 취급한다. 상호 배타적 집합(Disjoi..

#include #include using namespace std; // 그래프 / 트리 응용 // 오늘의 주제 : 최소 스패닝 트리 (Minimum Spanning Tree) // 상호 배타적 집합 (Disjoint Set) // -> 유니온-파인드 Union - Find (합치기-찾기) // Lineage Battleground 개발 // 혈맹전 + 서바이벌 // 1인 팀 1000명 (팀 id 0~999) // 동맹 (1번팀 + 2번팀 = 1번팀) // 트리 구조를 이용한 상호 배타적 집합의 표현 // [0] [1] [2] [3] [4] struct Node { Node* leader; }; // [1][3] // [2] [4][5] //[0] // 시간복잡도 : 트리의 높이에 비례한 시간이 걸림...

#include #include #include #include #include using namespace std; #include // 해시 테이블 // map vs hash_map // map : Red-Black Tree // 균형적 이진 트리 // - 추가/탐색/삭제 O(logN) // C# dictionary = C++ map (X) // C# dictionary = C++ unordered_map // hash_map(c++11 표준 unordered_map) // - 추가/탐색/삭제 O(1) // 메모리를 내주고 속도를 얻는다. // EX) 아파트 우편함 // [201][202][203][204][205] // [101][102][103][104][105] // 1 ~ 1000 user( ..

퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 알고리즘 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 분..

#include #include #include #include #include using namespace std; #include // 오늘의 주제 : 정렬 // 1_ 버블 정렬 (Bubble Sort) // 가장 처음부터 차례차례 다음 수와 비교하여 정렬한다. // 시간 복잡도 (N-1) + (N-2) + (N-3) ... +2+1 // = O(N^2) void BubbleSort(vector& v) { const int n = (int)v.size(); for (int i = 0; i v[j+1]) { int temp = v[j]; v[j] = v[j + 1]; v[j + 1] = temp; ..

BinarySearchTree.h #pragma once struct Node { Node* parent = nullptr; Node* left = nullptr; Node* right = nullptr; int key = {}; }; class BinarySearchTree { public: void Print() { Print(_root, 10, 0); } void Print(Node* node, int x, int y); void Print_Inorder() { Print_Inorder(_root); } void Print_Inorder(Node* node); Node* Search(Node* node, int key); Node* Search2(Node* node, int key); Node* M..

Player.h #pragma once class Board; class Player { enum { MOVE_TICK = 100 }; public: void Init(Board* board); void Update(uint64 deltaTick); void SetPos(Pos pos) { _pos = pos; } Pos GetPos() { return _pos; } bool IsGo(Pos pos); private: void RightHand(); void Bfs(); void AStar(); private: Pos _pos = {}; int32 _dir = DIR_UP; Board* _board = nullptr; vector _path; uint32 _pathIndex = 0; uint64 _sum..

#include #include #include #include #include using namespace std; template class PriorityQueue { public: void push(const T& data) { // 우선 힙 구조부터 맞춰준다. _heap.push_back(data); //도장깨기 시작 //static_cast(대상); // 현재 Index를 받는다. int now = static_cast(_heap.size()) - 1; while (now > 0) { int next = (now - 1) / 2; if (_predicate(_heap[now], _heap[next])) break; ::swap(_heap[now], _heap[next]); now = next;..