ALGORITHM/c&c++ leetcode (22) 썸네일형 리스트형 [C++/LeetCode] Minimum Operations to Reduce X to Zero - using Sliding Window Daily LeetCoding Challenge for June, Day 11. 문제 아이디어: Sliding Window Sliding Window 특정 조건의 연속 합을 구할 때 고정된 사이즈의 윈도우를 이동시키며 O(N)으로 푸는 알고리즘 Two-Pointer 알고리즘과 달리 고정된 길이의 윈도우를 이동시킬 때 사용한다. 또한 정렬되어 있지 않아도 사용할 수 있다는 점에서 유용하다. 윈도우의 크기가 고정적이기 때문에 포인터가 2개일 필요도 없이 왼쪽 또는 오른쪽 포인터에 사이즈를 더하고 빼는 것으로 쉽게 윈도우의 범위를 구할 수 있다. 주로 Map을 이용해서 구현한다. Sliding Window 알고리즘의 특성과 시간 복잡도가 O(N)인 이유 sliding window의 특징은 윈도우의 크기가 고정.. [C++/LeetCode] Network Delay Time Daily LeetCoding Challenge May, Day 14 문제: 최장 거리 판별하기 아이디어: Dijkstra 신호가 전달되는 시간은 가장 긴 시간에 의해 영향 받는다. 따라서 시작 노드부터 다른 노드까지의 최단 거리를 구하고, 그 중 가중치가 가장 큰 값이 바로 Delay Time이 된다. 완성 submission: 120ms / 39.8MB class Solution { public: void dikjstra(vector graph[], vector &dist, int start) { // 우선 순위 큐 사용 priority_queue q; // 시작 노드를 넣고 이때의 가중치는 0이다. 시작 노드의 거리는 0으로 초기화 q.push({0, start}); dist[start] = 0; .. [C++/LeetCode] Is Graph Bipartite? - using BFS Daily LeetCoding Challenge for April, Day 29. 문제: 이분 그래프(Bipartite Graph) 판단하기 이분 그래프 Bipartite Graph node들을 두개의 집합으로 구분할 수 있고, 같은 집합에 속한 node끼리는 연결되지 않아야 한다. 즉 다시 말해서 3색 칠하기와 같은 문제라고 볼 수 있다. 연결되어 있는 노드끼리는 같은 색이 되지 않도록 색칠하는 문제와 같다. 아이디어: BFS (or DFS) BFS를 사용하여 그래프를 전체 탐색하여 연결되어 있는 노드가 같은 색인 경우 false를 return 하면 된다. 완성 class Solution { public: void BFS(vector &color, vector graph, int root, int c,.. [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.. 이전 1 2 3 다음
