정수 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,..

이진 트리가 주어졌을 때 트리의 가장 얕은 깊이를 구하는 문제입니다.DFS와 BFS 두 방식으로 모두 풀 수 있습니다.하지만 DFS는 결국 모든 노드를 방문하게 되고 BFS는 중간에 가장 얕은 깊이를 찾으면 끝나기 때문에 BFS가 조금 더 빠릅니다. BFS 방식/** * 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) {} * ..

이진 트리가 주어졌을 때 각 Level의 노드의 값의 평균을 찾는 문제입니다.Level 단위로 노드를 방문해야 하기에 인접한 노드들을 방문하는 너비우선탐색인 BFS를 사용해 문제를 풀어야 합니다. queue를 사용해 문제를 풀었습니다.큐에 root 노드를 넣어주면 큐에 Level 0의 모든 노드를 넣은 셈이 되는데 이때 큐의 크기가 1이 됩니다.이는 Level 0에 있는 모든 노드의 개수과 동일합니다.이후 큐에 저장된 노드를 사용해 자식 노드들을 큐에 다시 저장하면 큐에는 Level 1의 노드들만 들어가게 됩니다.그러면 현재 큐의 크기는 Level 1의 노드의 개수와 같습니다.이런 특징을 사용해 각 Level의 값의 평균을 구해줍니다. 이 방식을 더이상 방문할 노드가 없을때까지 반복해줍니다./** * D..