j-engine 님의 블로그

이진 트리가 주어졌을 때 트리의 가장 얕은 깊이를 구하는 문제입니다.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..

버블 정렬은 시간 복잡도가 O(n^2)인 상당히 느린 알고리듬이지만 코드가 매우 단순합니다. 기본적으로 배열의 두 수(a, b)를 선택한 뒤, 이 두 수가 정렬되어 있다면 넘어가고 아니라면 두 수를 바꾸는 방식(Swap)으로 진행됩니다.이 비교를 배열의 처음부터 끝까지 반복하면 오름차순으로 정렬할 때 가장 큰 값이 배열의 맨 마지막이 됩니다.다시 한번 비교를 진행하면 2번째로 큰 값이 가장 큰 값의 앞으로 오게됩니다.배열에 아무 변화가 없을 때까지 반복하거나 더는 비교할 수 없을 때까지 진행이 되었다면 정렬이 끝이 납니다. void BubbleSort(vector& nums) { int n = nums.size(); for (int i = n - 1; i > 0; i--) { bool swappe..

이 문제는 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..

선택 정렬은 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2)만큼의 시간이 걸리는 알고리듬이다. 알고리듬이 단순하며 메모리가 원래 배열에 교체(Swap)을 위한 임시 변수를 제외하면 추가적으로 필요하지 않아 메모리가 제한적인 경우에 사용시 이점이 존재합니다. 선택 정렬 알고리듬 순서:   1. 주어진 배열 중에 최소값을 찾는다.   2. 그 값을 맨 앞에 위치한 값과 교체한다.   3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. (1, 2번 반복) 주어진 배열 중 최소값을 찾기 위한 Loop와 각각의 값의 자리를 비교하기 위한 Loop가 필요해 이중 루프를 사용합니다.이 과정이 i가 배열의 끝에 도달할 때까지, 즉 바깥쪽 Loop가 끝날 때..

배열에는 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를 한 번 돌려주면서 이전의 값과 비교해 ..