게임 클라 개발

개요 알고리즘이나 자료 구조의 성능을 볼 때 amortized analysis란 단어를 많이 보게 된다. 이걸 한국어로 번역하면 분할 상환 분석이라는 생소한 단어가 나와 헷갈리는데, 간단히 말하면... 성능을 분석함에 있어서 "N개의 시퀀스를 수행할 때의 평균 시간을 측정했다." 라는 의미이다. 왜 이러냐? dynamic array를 한번 생각해보자. dynamic array는 capacity가 꽉 찬 상태에서 add가 일어날 경우, 흔히 doubling 이라 불리우는 비싼 연산을 수행한다. 따라서 dynamic array의 Add 연산의 시간 복잡도는 얼마인가? 라고 묻는다면 대부분의 경우에는 O(1)이겠지만 doubling이 일어날 때는 O(n) (n은 현재 array에 있는 요소의 갯수)이라고 할 ..

리트코드 64 - Minimum Path Sum (M) 더보기 class Solution { public: int minPathSum(vector& grid) { int m = grid.size(); int n = grid[0].size(); for (int i = 1; i next = iter; cur = cur->next; iter = iter->next; cur->next = nullptr; } ..

리트코드 52 - N-Queens II (H) 더보기 struct Point { int row, column; Point(int row, int column) : row(row) , column(column){} }; class Solution { public: int totalNQueens(int n) { vector queens; queens.reserve(n); int ans = 0; Dfs(n, 0, queens, ans); return ans; } private: void Dfs(int n , int row, vector& queens, int& ans) { if (row == n) { ++ans; return; } for(int col=0;col max) max = curSum; } retur..

리트코드 40 - Combination Sum II (M) 더보기 class Solution { public: vector combinationSum2(vector& candidates, int target) { vector ret; vector current; sort(candidates.begin(), candidates.end()); search(0, target, current, candidates, ret); return ret; } //dfs void search(int startIdx, int left, vector& current, const vector& candidates, vector& ans) { if (left < 0) return; if (left == 0) { ans.empla..

리트코드 24 - Swap Nodes in Pairs (M) 더보기 class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode * root = new ListNode(0, head); auto cur = root; while(cur->next != nullptr && cur->next->next != nullptr) { auto left = cur->next; auto right = left->next; cur->next = right; left->next = right->next; right->next = left; cur = left; } return root->next; } }; 리트코드 25 - Reverse Nodes in k..

리트코드 10 - Regular Expression Matching (H) 더보기 class Solution { public: bool isMatch(string s, string p) { vector dp(s.size() + 1, vector(p.size() + 1, false)); dp[0][0] = true; for (int i = 0; i = 2 && dp[i][j - 2]) || (i > 0 && j > 1 && (p[j - 2] == '.' || p[j - 2] == s[i - 1]) && (dp[i - 1][j - 2] || dp[i - 1][j])); } } } return dp[s.size()][p.size()]; } }; 리트코드 11 - Container With Most Water ..

프로그래머스 - 사라지는 발판 (lv3) 더보기 #include #include using namespace std; struct point { point(int x, int y) : x(x), y(y) {} int x, y; }; bool isIn(vector& board, int x, int y) { return x >= 0 && y >= 0 && x < board.size() && y < board[0].size() && board[x][y] == 1; } vector getNearBy(vector& board, point loc) { vector ret; int x, y; vector diffs { {0,1}, {0,-1}, {1,0}, {-1,0} }; for(auto diff : diffs) ..

백준 10875 - 뱀 더보기 #include #include #include #include using namespace std; //(2,4) - (2,10) 은 is_row = false, axis=2, min = 4, max= 10 으로 표현 struct Line { bool is_row; int axis, min, max; bool operator axis == rhs.axis) return this->max axis < rhs.axis; } }; bool cross(const Line& a, const Line& b) { if (a.is_row == b.is_row) { if (a.ax..

개요 알아둘 만한 알고리즘 및 자료구조를 정리. 해당 알고리즘에 대해 자세히 알아보는 게 아니라 나중에 '아 이런 게 있었지. 하며 찾아볼 수 있도록 하는 용도.' 여기 나열된 게 최선의 알고리즘은 아닐 수 있으므로 어디까지나 구글링의 시작점으로 활용해야 한다. (ex. 경로의 가중치가 음수인 경로를 구하고 싶다면 벨먼 포드를 쓰는게 아니라 벨먼 포드보다 나은 알고리즘을 검색해본다.) 너무 기초적인 것(ex. KMP)은 다루지 않는다. 일반 펜윅트리, 세그먼트트리의 Lazy Propagation 구간 자체를 업데이트할때 쓸 수 있다. 백준 문제 (백준 2934 - LRH 식물)가 있다. 세그먼트트리랑 비슷함. 희소 테이블 (Sparse Table) 어 대충 정적인 Array의 1,2,4,8,16... 번..

1. 프로그래머스 - 입실퇴실 더보기 #include #include using namespace std; vector solution(vector enter, vector leave) { vector answer(enter.size()); vector room(enter.size()); int num_people = 0; int leave_idx = 0; for(auto entry : enter) { //지금 방에있는애들 만남횟수 1증가 int num_left_checked = num_people; for(size_t i=0 ; i 0;++i) { if (room[i] == true) { ++answer[i]; --num_left_che..