트리가 주어지면 root 노드에서 leaf 노드로 가는 경로 중 노드들의 값의 합이 targetSum과 같은 경로가 하나라도 있는지 찾는 문제입니다.경로를 찾는 문제이므로 DFS를 사용했습니다.Leaf 노드는 자식 노드들이 없는 노드를 Leaf 노드로 정의합니다. bool DFS(TreeNode* node, int sum, const int& targetSum) { if (!node) return false; sum += node->val; if (!node->left && !node->right) // Leaf node return sum == targetSum; // 같은지 확인 // 왼쪽경로 || 오른쪽 ..

두 개의 트리가 구조와 각각의 노드가 모두 같은지 확인하는 문제입니다.모든 노드를 방문하면 되는 문제로 DFS와 BFS 방식 모두 사용할 수 있습니다.저는 DFS 방법으로 문제를 풀었습니다.  bool isSameTree(TreeNode* p, TreeNode* q) { if (p == nullptr && q == nullptr) return true; // 두 노드 중 한 노드가 없거나 두 노드의 값이 다르다면 if (p == nullptr || q == nullptr || p->val != q->val) return false; bool left = isSameTree(p->left, q->l..

정수 n이 주어지면 0부터 n까지의 숫자를 2진수로 변환했을 때 각각의 2진수에 1이 몇 개인지세는 문제입니다.0부터 n까지의 수이므로 정답 배열의 크기는 n + 1이 됩니다. 가장 간단한 방법은 매번 10진수를 2진수로 변환할 때 1의 개수를 세는 방법입니다.10진수를 2진수로 바꾸기 위해서는 2로 나눈 값과 나머지로 2진수를 구해줍니다.2진수를 구하는게 아닌 2진수로 변환되었을 때 1의 개수를 구하면 되므로 나머지 값을 전부 더해주면 됩니다. int CountBitHelper(int n) { int bit = 0; while (n) { bit += n % 2; // 2진수가 필요한게 아닌 2진수의 1의 개수만 세면 된다. n /= ..

오름차순으로 정렬되어 있는 배열에서 target보다 큰 값들 중 가장 작은 값을 찾는 문제입니다.정렬되어 있는 배열에서 찾는 문제이기에 이진탐색을 사용했습니다.이진탐색은 정렬된 배열에서 Linear Search보다 빠르게 탐색 가능합니다. target보다 작거나 같으면 찾는 값이 아니므로 제외합니다. l = mid + 1;target보다 크면 정답이 될 수 있는데 그 중 가장 작은 값을 찾는 문제이므로 그 뒤는 제외해주어도 됩니다.r = mid이렇게 l과 r의 값이 같아지면 while loop가 종료되고 이 index의 값이 target보다 크면 배열에 있는 target보다 큰 값 중에서 가장 작은 값이 되지만 아니라면 배열에는 target보다 큰 값이 없는 것 입니다.  char nextGreat..

이진 검색을 사용해 원사는 값의 index를 찾는 문제입니다. 이진 검색은 정렬되어 있는 배열에서 중간의 값을 선택해, 그 값과 찾고자 하는 값을 비교해 찾는 방식입니다.만약 중앙값이 찾는 값보다 크면 그 값은 새로운 최대값이 되고, 작으면 그 값은 새로운 최솟값이 됩니다.그 후 다시 최소값과 최대값의 index를 사용해 그 중앙값을 찾아 비교를 목표값을 찾을 때까지 반복해줍니다. int search(std::vector& nums, int target) { int l = 0, r = nums.size() - 1; while (l ((r - l) * 0.5f); // 중간 값 if (nums[mid] > target) // 중간 값이 더 크면 ..

이 문제는 이진 트리가 주어지면 root부터 leaf  node, 즉 맨 밑의 정점까지 갈 수 있는 모든 경로를 출력하는 문제입니다. 경로를 출력해야 하므로 DFS를 사용하면 됩니다.저는 Recursion DFS 방법을 사용했습니다. /** * 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,..