j-engine 님의 블로그

이진 검색을 사용해 원사는 값의 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..

이 문제는 1차원 배열이 주어지면 2차원 배열로 바꾸는 문제입니다.즉, 1차원 배열을 2차원 배열처럼 사용할 줄 알면 풀 수 있는 문제입니다.  1D Array로 2D Array처럼 사용하기 위해서는 Index를 다음과 같이 사용하면 됩니다. 어떤 2차원 index (x, y)의 1차원 index는 x + width * y"와 같습니다. (y * width + x)vector> construct2DArray(vector& original, int m, int n) { if (original.size() != m * n) // 두 크기가 같지 않으면 변환 불가 return {}; vector> ans(m, vector(n, 0)); for (int ..

주어진 배열에서 한 쌍이 아닌, 즉 같은 숫자가 존재하지 않는 숫자를 찾는 문제입니다.총 3가지 방식이 존재하는데 이 중 추가적인 조건인 linear runtime, 즉 시간 복잡도가 O(N)이고 추가적인 공간은 사용하지 말아야 합니다. 맵을 사용한 빈도수 확인 방식 nums 배열에 같은 숫자가 몇 개 있는지 확인하기 위해 정렬된 맵은 필요하지 않으므로 해시맵인 unordered_map을 사용했습니다. (해시맵이 key값으로 value를 찾는데 시간이 더 적게 걸립니다. Average: O(1))그리고 빈도수를 확인해 1번만 나왔다면 그 숫자가 답이 됩니다.이 방법은 O(N)의 시간복잡도를 가지지만 맵을 사용하기 위해 추가적인 공간이 필요해 문제의 조건을 만족할 수 없습니다.int singleNumber..

배열에는 0부터 n까지의 숫자가 저장되어 있지만 배열의 크기는 n과 같아 0부터 n까지의 숫자 중 배열에 없는 숫자가 존재하는데 이 배열에 없는 숫자를 찾아야합니다. 첫번째 풀이 제 첫번째 풀이는 정렬을 사용했습니다. 정렬을 하면 0부터 큰 숫자대로 정렬되기 때문에 index와 value가 같게됩니다.이때 index와 value가 다르면 그 index인 숫자가 배열에 없는 것 입니다.int missingNumber(vector& nums) { int n = nums.size(); std::sort(nums.begin(), nums.end()); // 정렬 for (int i = 0; i  두 번째 풀이 0부터 n까지의 숫자를 다 있는지 알아야 한다면 결..

Leetcode의 Easy 문제 중 Array와 관련된 문제다. 간단한 문제로 배열에서 value가 한 번이라도 반복되면 true를 반환, 반복되는 값이 하나도 없다면 false를 반환하면 된다. 내 풀이는 먼저 정렬을 사용해 배열을 정렬해 준 뒤 한 번이상 반복되는 값을 찾아주는 것이다.bool containsDuplicate(vector& nums) { std::sort(nums.begin(), nums.end()); // sort for comparison for (int i = 1; i  C++의 sort() 함수는 개선된 Quick Sort 알고리즘을 바탕으로 만들어져 O(n log n)의 시간복잡도를 보장한다.이후 nums의 개수만큼 loop를 한 번 돌려주면서 이전의 값과 비교해 ..