전체 글 (129) 썸네일형 리스트형 [C++/LeetCode] Kth Smallest Element in a BST Daily LeetCoding Challenge for April, Day 18. 문제 Binary Search Tree에서 K번째로 작은 수를 구하는 것이다. 아이디어1: min heap binary sarch tree의 아이템을 순회하여 다 가져와서 min heap(priority queue)에 넣는다.그 후 priority queue에서 K번째의 아이템을 가져오면 됨 완성 submission: 21ms / 24.5MB /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullpt.. [C++/LeetCode] Convert BST to Greater Tree Daily LeetCoding Challenge for April, Day 16. 문제 다음과 같이 Binary Search Tree가 주어졌을 때 이를 반대로 만드는 것이다. 아이디어: DFS 어제에 이어서 오늘도 DFS를 사용한다. 로직을 짜기 전에 문제에서 값이 수정되는 원리를 파악해보자. root의 값은 어떻게 수정될까? 바로 [root->right의 수정으로 얻어진 값 중 가장 큰 값 + root->val] 의 결과이다. 따라서 가장 먼저 할일은 바로 root->right를 수정하는 것이다. 그 후 root->node의 값을 수정해준다. root->left의 값은 root node의 value를 더한 후에, root->left에 대해서 같은 로직을 반복하는 것이다. 그럼 root->right를 .. [C++/LeetCode] Trim a Binary Search Tree Daily LeetCoding Challenge for April, Day 15. 문제 주어진 범위 내에 해당하는 원소들로만 이루어지도록 tree를 변경하기 아이디어 1: DFS DFS(Depth First Search) DFS는 BFS와 비교되는 개념으로, 진행할 수 있는 가장 깊은 node까지 확인하고 상위 노드로 돌아오는 방식이다. 문제의 경우는 다음과 같이 두 가지이다. root의 값이 범위 안에 속할 수 있고, 범위를 벗어날 수 있다. 1. 이때 범위 안에 속한다면 DFS를 활용하여, root->left, root->right 에 대해서도 trim 함수를 재귀적으로 적용해서 잘라진 가지를 가질 수 있도록 하면 된다. 2. 범위를 벗어나는 경우에는 root 자체가 변경되어야 하므로 Binary T.. Synchronization in LINUX - POSIX Semaphore로 producer-consumer 해결하기 동기화 기법 중 semaphore를 사용하는 방법을 알아보자 synchronization 2 지난 포스트에서 동기화 기법인 Lock에 대해서 살펴보았다. 하지만 spinlock이나 disabling interrupt는 short, simple critical section에서만 효과적이다. Mutual exclusion을 제외하고는 별달리 뭘 해주지 않기.. josushell.tistory.com Semaphore Implementation 은 두가지로 되어있다. - POSIX semaphore : 주로 스레드 동기화에 사용됨 - System V Semaphore : 주로 프로세스 동기화에 사용됨 이 중에서 IEEE에서 정한 UNIX의 표준 (syscall 기준)인 POSIX library로 알아보자. .. [C++/LeetCode] Spiral Matrix II Daily LeetCoding Challenge for April, Day 13. 문제 이런 형태로 회전되어 숫자가 배치된 2차원 배열을 생성하는 것이다. 아이디어 방향을 전환하는 key를 만들어서 row, col index에 추가하면서 값을 채우자 이때 방향은 총 4개이다. (◀️🔼▶️🔽) 방향을 전환하는 조건은 row, col이 각각 0, n-1이 되는 경우이다. 즉 2차원 배열의 모서리에서 전환한다. 예외 사항 위 설명에도 있듯이, 꼭 2차원 배열의 모서리가 아니더라도 배열에 값이 채워져있는 경우에도 방향 전환이 필요하다. 따라서 이 예외 처리를 위해서 result 배열을 0으로 초기화하고, 0이 아닌 경우 즉 값이 있는 경우에도 방향을 전환하도록 구현한다. 완성 submission: 0ms / 6.. [C++/LeetCode] Game of Life Daily LeetCoding Challenge for April, Day 12 문제 2차원 vector의 값을 규칙에 맞게 변경하기 아이디어 2차원 vector를 돌면서 이웃한 cell 중에서 몇개의 1이 있는지 확인한 후, 값을 정한다. 완성 submission: 6ms / 6.9MB class Solution { public: void gameOfLife(vector& board) { int row = board.size(); int col = board[0].size(); vector result(row, vector (col, 0)); for(int i = 0;i < row;i++) { for(int j = 0;j < col;j++) { int sum = 0; for(int n = i - 1;n.. [iOS] side bar 라이브러리 없이 직접 구현하기 앱에서 정보를 숨기지만 접근하기 쉽게 만드는 UI는 무엇일까? 바로 side bar이다. 정보를 어느 정도 숨겨주지만 side bar를 터치하여 누르면 다양한 정보와 기능이 나타나도록 구현할 수 있어서 자주 사용된다. 이러한 side bar는 제공해주는 UI 요소가 아니기 때문에 직접 구현해야 한다. 다행히 많은 라이브러리들이 있지만 직접 sidebar 를 구현해보도록 하자. Custom Container View Controller container view controller는 다른 view controller와 달리 실질적인 화면, 자식 뷰 컨트롤러를 관리하는 역할만 한다. 예를 들어 tab bar controller, navigation view controller, page view contro.. [C++/LeetCode] Kth Largest Element in a Stream Daily LeetCoding Challenge for April, Day 8. 문제 배열에서 k번째로 큰 수를 찾음. 이때 add() 함수를 구현하여, 이 함수의 인자로 int 값을 주었을 때 배열에 추가하고 추가한 배열에서 k번째로 큰 수를 반환하도록 구현 아이디어: Heap(priority queue) k번째로 큰 수를 찾는 것이므로, k+1번부터 큰 수는 필요하지 않다. 즉 배열에서 없어도 된다.또한 k번째로 큰 수를 찾는 것이므로 오름차순으로 정렬한 배열이 필요하다.이 조건을 쉽게 만족하는 자료구조는 바로 Heap이다. Heap 1. complete binary tree2. 모든 노드의 값은 자식보다 크거나 같다. (max heap), 작거나 같다.(min heap) Heap은 위의 특성을 만족.. 이전 1 ··· 3 4 5 6 7 8 9 ··· 17 다음
