j-engine 님의 블로그

계단을 올라갈 때 n번째까지 갈 수 있는 방법의 수를 물어보는 문제입니다.계단을 오를때 제한이 있는데 한 번에 1칸 또는 2칸씩 오를 수 있습니다. 이 뜻은 n번째 계단에 가기 위해서는 n-1번째 계단에서 1칸을 올라가거나 n-2번째 계단에서 2칸을 오를 수 있습니다.이를 쉽게 Recursion으로 풀 수 있습니다.  int climb(int n) { if (n == 0 || n == 1) // 안오르거나, 가장 첫 1칸 return 1; // 방법의 수는 1 // n번째 계단을 오르려면 n-1에서 한칸 또는 n-2에서 두 칸씩 오르면 된다 return climb(n - 1) + climb(n - 2); }(이 방..

이 문제는 트리를 좌우구조를 뒤집어주는 문제입니다.전체 트리 구조를 뒤집기위해 각각의 노드를 어떻게 해야할지 살펴보면 결국 각 노드의 왼쪽 자식과 오른쪽 자식 노드를 바꿔주면 됩니다.모든 노드의 자식 노드들을 바꿔줘야 하므로 DFS를 사용했습니다. Recursion/** * 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) {} * ..

이 문제는 트리가 두 개 주어집니다. 원래 트리의 구조 안에 서브 트리 구조와 같은 구조가 있는지 확인하는 문제입니다.만약 서브 트리 구조와 같은 구조가 있어도 추가적인 노드가 붙어있으면 같은 구조가 아닙니다. 서브 트리의 root 노드와 같은 노드가 나올때까지 자식 노드들을 타고 갑니다.만약 root 노드와 같은 노드를 찾았다면 그 구조가 같은지 확인해줍니다.  bool isSameStructure(TreeNode* main, TreeNode* sub) { if (!main || !sub) // 두 노드 중 하나만 nullptr이거나 모두 nullptr인 경우 return !main && !sub; // 두 노드 모두 nullptr인 경우엔 true 아니면 fals..

이진 트리가 주어지면 트리의 가장 큰 깊이값을 찾는 문제입니다.자식 노드로 계속 이동하며 깊이값을 찾는 문제이기에 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, TreeNode *left, TreeNode *right) : val(x), left(left),..

이진 트리가 주어지면 트리의 지름을 알아내는 문제입니다.트리의 지름은 한 노드에서 다른 노드로 가는 가장 긴 경로입니다.이 경로는 root노드를 지나갈 수도 있고 아닐 수도 있습니다. 만약 위의 예시와 같은 트리가 주어지면 가장 긴 경로는 노드 4에서 노드 3으로 가는 경로 혹은 노드 5에서 노드 3으로 가는 경로가 될 수 있습니다. 이는 노드 1의 왼쪽 자식의 최대 길이 + 오른쪽 자식의 최대 길이와 같은데 노드 1의 왼쪽 자식의 최대 길이는 2이고 오른쪽 자식의 최대 길이는 1로 트리의 지름은 3이 됩니다. 즉, 각 노드를 방문하며 노드의 왼쪽 자식의 최대 깊이와 오른쪽 자식의 최대 깊이를 더하면 그 노드를 root로 하는 subtree의 지름이 됩니다.이렇게 각 노드의 지름(Diameter)값을 비..

이진 트리 두 개가 주어졌을 때 트리들을 하나의 트리로 합치는 문제입니다.병합 규칙 :       1) 두 트리의 노드가 모두 존재하면 두 노드의 값을 합쳐 병합된 트리의 노드의 값으로 사용       2) 두 노드 중 null이 아닌 노드를 병합된 트리의 노드로 사용       3) 둘 다 null이면 nullptr /** * 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(n..

트리가 주어지면 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..