본문 바로가기

분류 전체보기147

Binary Tree Traversal, Binary Tree Leetcode의 문제를 풀려고 설명을 읽던 중 inorder traversal 이란 단어에서 막혔다. 몇몇 Tree 문제를 풀었는데도, 처음 보는 단어가 튀어 나와 공부할게 생겼다. traversal이란 Binary Tree 자료 구조의 모든 노드를 방문할 수 있는 방법이다. 선형 자료 구조 (연결 리스트, 스택, 큐 등)은 순차적으로 접근하지만 Tree 자료 구조의 접근 방식은 다르다. 보통 Tree에서는 Depth First Search (DFS), Breadth Frist Search (BFS)를 사용해 노드 순회 및 탐색이 가능하다. Binary Tree인 경우 위 두 방법과 함께 Recursion 방법을 사용해 순회 및 탐색이 가능하다. DFS로 Tree를 순회할 경우, Queue를 활용하면 .. 2023. 3. 7.
[LeetCode] 771, Jewels and Stones Skill Use hash table to decrease time complexity to under log(n^2) Others Use string struct member Use ASCII Number of english letter int gstHashTable[60] = { 0 }; class Solution { public: int numJewelsInStones(string jewels, string stones) { memset(&gstHashTable, 0, sizeof(int) * 60); int RetVal = 0; for (int i = 0; i != stones.size(); ++i) { gstHashTable[stones[i] - 65]++; } for (int i = 0; i .. 2023. 2. 14.
PyTorch nn.Linear 참조 : https://pytorch.org/docs/stable/generated/torch.nn.Linear.html Fully Connected Layer 구성 시 기본적으로 선택하는 식 중 하나 입력 데이터 x에 대해 Linear Transformation (선형 변환)을 계산한다. $$ y = xA^{T}+b $$ class Torch.nn.Linear (in_features, out_features, bias=True, device=None, dtype=None) Parameters: in_features (int) : input sample의 size out_features (int) : output sample의 size bias (bool) : (b term), Default : True.. 2023. 2. 6.
[LeetCode] 1720 Decode XORred Array Solution Use principle : A ^ B = C -> A ^ C = B class Solution { public: vector decode(vector& encoded, int first) { vector res; res.push_back(first); for (int i = 0; i != encoded.size(); ++i) { res.push_back(res.back() ^ encoded[i]); } return res; } }; 2023. 1. 29.
XOR 비트 연산의 특징 및 코딩 문제들 코딩 문제를 풀다보면 XOR 연산을 활용하는 부류가 꽤 있다. 이는 XOR 비트 연산이 가지고 있는 몇가지 특징 때문인데, 이들을 잘 활용하면 Time Complexity와 Space Complexity를 각각 O(n)과 O(1)으로 줄일 수 있다. 따라서 특정 문제들에 대해서는 굉장히 효율적인 답안이 될 수 있다. XOR 비트 연산 특징 A ^ B = C -> A ^ C = B. (^ : XOR 연산) 위 식에서 A와 C를 알고 있을 때 B를 구하는 것이 목표이다. 이때 XOR의 연산 특성 사, A와 C 를 XOR 연산한 것이 바로 B이다. ex) 4 ^ 2 = 6 (100 ^ 010 = 110) -> 4 ^ 6 = 2 (100 ^ 110 = 010) 이는 다른 비트 연산들 (AND, OR, NOT)에.. 2023. 1. 29.
이진 검색 알고리즘 (Binary Search Algorithm) 이진 검색 알고리즘 (Binary Search Algorithm) 오름차순 (혹은 내림차순)으로 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘 시작과 마지막 범위 내에서 중간의 값을 임의로 선택하여 찾고자 하는 값과 비교 중간 값이 찾는 값 대비 작다면, 시작 범위를 중간 값으로 설정 중간 값이 찾는 값 대비 크다면, 마지막 범위를 중간 값으로 설정 장점 특정 값을 찾기 위해 배열의 모든 인덱스를 모두 탐색하는 것 대비, 탐색 범위를 절반씩 줄여나가기 때문에 속도가 빠르다. 단점 배열이 정렬되어 있어야 한다. 정렬을 위한 연산이 소요 된다. 적용 문제 예시 배열 내에서 Target 값과 가까운 3개의 원소를 찾는 문제 모든 원소를 탐색하면 O(n^3)의 Time Complexity인데, 이진 탐색 알고.. 2023. 1. 26.

티스토리툴바