목록Algorithm (30)

궁금한게 많은 개발자 노트

[ leetcode ] 102. Binary Tree Level Order Traversal

Binary Tree가 주어졌을 때, level order로 순회하는 순서를 반환하는 문제입니다. BFS(Breadth-First-Search)로 접근하여 최상위 노드부터 넣고 자식들을 순서대로 넣으면서 level order로 순회합니다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, Tree..
Algorithm 2023. 5. 2. 13:19
[ leetcode ] 110. Balanced Binary Tree

Binary Tree가 주어졌을 때, 해당 트리가 균형 잡힌 트리인지를 확인하는 문제입니다. 균형 잡힌 트리는 서로 다른 노드를 루트 노드로 하는 서브 트리 사이에 높이 차이가 1이하인 노드들로 구성된 트리를 의미합니다. 마찬가지로 재귀를 이용하여 left, right child로 시작하는 서브 트리의 균형 여부를 확인하고, 해당 노드의 균형 여부는 각 left, right child subtree의 depth를 구하여 판단합니다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(n..
Algorithm 2023. 5. 2. 13:13
[ leetcode ] 111. Minimum Depth of Binary Tree

Binary Tree가 주어졌을 때, root에서 leaf node까지 가장 짧은 경로의 길이를 구하는 문제입니다. 재귀를 이용하여 해당 노드가 NULL이면 0을 반환하고 left, child중 짧은 길이를 반복적으로 반환하면서 해를 구합니다. 이 때 left나 right child중 하나 이상 NULL이면 최소값이 0으로 되므로 조건문으로 큰 값이 포함되도록 해줍니다. 둘 다 NULL이 아닐 때는 둘 중 작은 값, 하나 이상 NULL 이면 1 이거나 값이 있는 것을 반환 하도록 합니다. (자식 한쪽만 값이 있는 경우 해당 노드는 leaf가 아니므로 leaf의 값을 가져가야 함) /** * Definition for a binary tree node. * struct TreeNode { * int val..
Algorithm 2023. 5. 2. 12:53
[ leetcode ] 258. Add Digits

string으로 들어온 숫자를 각 자리 수를 더해 한자리가 남을 때 까지 더하고 반환하는 문제입니다. 마지막 두 자리 수를 더해서 두 자리가 되면 사용한 두 칸을 비우고 다시 두칸을 더하고, 한 자리 수가 되면 사용한 두 칸을 비우고 한 자리를 더하는 방식으로 답을 구합니다. class Solution { public: int addDigits(int num) { while (num >= 10) { int one = num % 10; int two = (num / 10) % 10; int sum = one + two; num = sum >= 10 ? (num / 100 * 100) : (num / 100 * 10); num += sum; } return num; } };
Algorithm 2023. 5. 2. 11:40
[ leetcode ] 1288. Remove Covered Intervals

여러 구간들이 주어졌을 때, 어떤 한 구간이 다른 구간에 포함되는 경우 제거하고 남은 구간의 수를 반환하는 문제입니다. 이 때 정렬이 필요한데, 기본 오름 차순 정렬이 아닌 start는 오름 차순이고 end는 큰수가 먼저 앞에 오도록 정렬해야 순서대로 확인 시 다음 구간을 포함하는지 확인하기에 용이합니다. #include bool compare(vector a, vector b) { if (a[0] == b[0]) return a[1] > b[1]; return a[0] < b[0]; } class Solution { public: int removeCoveredIntervals(vector& intervals) { sort(intervals.begin(), intervals.end(), compare)..
Algorithm 2023. 5. 2. 11:31
Prev 1 2 3 4 5 6 Next