ALGORITHM (45) 썸네일형 리스트형 [C++/LeetCode] Min Cost to Connect All Points - using MST Daily LeetCoding Challenge for April, Day 26. 문제 맨하튼 거리가 최소가 되도록 정점을 연결하고, 가중치의 최소 합을 구하기 아이디어: 최소 신장 트리 MST 최소 신장 트리 Minimum Spanning Tree, MST Spanning Tree 그래프에서 모든 정점이 연결되도록 만든 그래프 즉 다음과 같이 모든 Edge들이 연결되지 않아도 된다. 즉 최소 연결 그래프 Spanning Tree는 DFS, BFS에 의해 O(n) 으로 찾을 수 있으며, cycle을 생성해서는 안된다. 따라서 모든 node를 포함하기 때문에 정확하게 (n-1)개의 edge로 연결된다. Minimum Spanning Tree spanning tree를 생성할 때 Edge들의 가중치의 합이 .. [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.. [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.. [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은 위의 특성을 만족.. [C/LeetCode] Container With Most Water Daily LeetCoding Challenge April, Day 5 문제 높이가 배열로 주어졌을 때, 만들 수 있는 가장 넓은 사각형 영역의 크기 구하기 (width = 1로 고정) 아이디어: brute force 이중 배열을 돌면서 두개의 index를 선택하고 이를 통해 만들 수 있는 사각형의 크기와 max 값을 비교함 완성: time limit exceeded 눈물이 나게도 시간초과가 발생했다. int min(int a, int b) { return a height[.. 이전 1 2 3 4 5 6 다음
