Algorithm

리트코드 211 c++ // 트라이 와일드카드 종결, 재귀vs길이별 트라이

https://leetcode.com/problems/design-add-and-search-words-data-structure/description/?source=submission-noac1. 와일드카드가 처음, 중간, 끝에 있는경우 모두 커버하는 코드1. 삽입부분은 기존과 동일하다.2. 검색에서 재귀함수를 써야한다.bool search(const string& word, int index) const { //끝에const => 이함수에서는 클래스내부 변수 수정금지 if (index == word.size()) { //문자끝에 온경우 return isEnd; } char c = word[index]; ..

리트코드 208. Trie 구현 c++ // 트라이복습, c클래스 초기화 방법

https://leetcode.com/problems/implement-trie-prefix-tree/ 1. c클래스 초기화 방법private: int a, int arr[30]public : className() : a(0), arr() {}암기할것 2. 트라이 복습1. 자식배열을 가진다. Trie* child[26]2. 새로운 자식할당은 new Trie로 한다.자식할당시 cur->child[c-'a'] = new Trie() 암기할것 class Trie {private: int isEnd; Trie* child[26];public: Trie() : child(),isEnd(0) {} //초기화방법 암기할것 void insert(string word) { Tri..

리트코드 1비트의 갯수 c++ //비트마스킹, 최하위 1지우는법

https://leetcode.com/problems/number-of-1-bits/description/1. 최하위 1지우는법n=n&(n-1) 하면 된다.ex) 11 & 10 == 10으로 최하위 1이 지워진다. 2. 1갯수 세는법 i) n을 2진수로 바꾸는 로직을 이용하면 된다.ii) 최하위 1을 계속 지우고 cnt++ 하면된다. n이 1이상인동안 3. 전체코드i)class Solution {public: int hammingWeight(int n) { //coutii)class Solution {public: int hammingWeight(int n) { int cnt=0; while(n){ n=n&(n-1); ..

리트코드 a+b c++ // 비트연산 덧셈구현방법

https://leetcode.com/problems/sum-of-two-integers/1. 의사코드sum(합, 캐리) :기저사례 캐리가0캐리가없는경우, a^b가 a+b이다.캐리가있는경우 (a&b)가 0이아닌경우, 캐리는 (a&b)  합(a^b)에 캐리를 더해줘야한다.캐리가 없을때까지11(2진수)+11(2진수)을 코드로 돌려보면 이해가 쉬울것이다. 2. 전체코드class Solution {public: int getSum(int a, int b) { if(b==0) return a; //기저사례 : carry가 0 int sum=a^b; //10 ^ 01 == 11, 둘다1인경우를 제외하고 덧셈완성 int carry=(a&b) 10

리트코드 자기를 제외한 배열의 곱 c++ // 누적곱 해결방법 : 누적곱 테이블을 정의하라

https://leetcode.com/problems/product-of-array-except-self/description/1. 기존코드0을 제외한 총 곱을 구하고0이 몇개인지에 따라서 분기함.. 너무 복잡함typedef long long ll;class Solution {public: vector productExceptSelf(vector& nums) { vector v,zero; int ret=1, iszero=0,isallzero=1; //0을제외한 총곱 , 0이있는지, 모두0인지 for(auto num:nums){ if(num==0) { iszero=1; zero.push_ba..

리트코드 주식을사고파는가장좋은시기 c++ // 이분탐색(슬라이딩윈도)+그리디, dp

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/1. 이분탐색(슬라이딩윈도)+그리디nC2완탐은 불가능함.이분탐색? st=0, en=n-1? -> 자꾸 분기가 일어남 -> 슬라이딩 윈도우?1.1. buy(st)=0, sell(en)=1로 시작하고음수이면, 비싸게 사고, 싸게 판다는 뜻인데가격이 싼날에 사면 된다.양수면, 정답갱신후 추가 탐색한다.1.2. 부분최적해가 전체최적해가 된다.(그리디)class Solution {public: int maxProfit(vector& prices) { int ret=0; int sell=0,buy=0; int n=prices.size(); if(n==..

리트코드 투썸 c++ // pair 이분탐색 방법 , 해쉬맵, nC2 O(n) 구현방법

https://leetcode.com/problems/two-sum/ 1. pair 이분탐색 방법1.1 lower_bound(begin, end, pair{a,b}) 이렇게 넣어줘야함 1.2. 시행착오diff = target - num 이렇게 둬야함 // abs씌울필요 없음! ex) 2에서 target이 0이면, -2를 찾으면 됨 1.3. 시간복잡도 : 정렬(nlgn) + 각원소에대해 이분탐색(nlgn) typedef pair pii;class Solution {public: vector twoSum(vector& nums, int target) { vector> v; // {value, index} for (int i = 0; i first == complement) { ..

리트코드 1325 리프노드지우기 c++

https://leetcode.com/problems/delete-leaves-with-a-given-value/description/?envType=daily-question&envId=2024-05-171. 의사코드dfs 기반으로, dfs(현재노드)내좌측, 우측을 탐색하는데1. 기저사례 : 내가 null이면 null을 반환2. 양쪽자식이 null 이고 내가 타겟이면 nullptr 반환리프노드의 자식을 null로 명시적으로 대입해주는 코드가 인상깊었다.  2. 전체코드 #include class Solution {public: TreeNode* removeLeafNodes(TreeNode* root, int target) { if(root==nullptr) return nullptr;..