Mini

https://leetcode.com/problems/counting-bits/description/1. 비트 구현 풀이1. 각각 숫자에대해 2진수를 구하면서 1의 갯수를 계산한다.O(n lgn)class Solution {public: vector countBits(int n) { vector ret; for(int i=0;i 2. dp풀이*행동영역 : n이 홀짝일때를 나눠서 규칙을 발견해라!n==0인 기저사례 처리 주의.class Solution {public: vector countBits(int n) { vector dp(n+1,0); if(n==0) return dp; dp[0]=0; dp[1]=1; ..

https://leetcode.com/problems/clone-graph/description/ 1. 의사코드1. map에 를 담는다.2. 엣지케이스 : 원래널인경우 return nullroot에 이웃이없는경우, 그거 new로 생성해서 리턴3. dfs초기화 : cur(원본)배열의 값으로 노드를 만들어주고, 이웃만 채워주면 된다!!이웃에대해, 이미 클론되었다면(맵에 존재한다면 == 유사 visited) 이웃에 담아준다.아니라면, 거기로 들어간다.4. 아래그림에서 1에서 시작하는 dfs를 돌려보면 이해가 될것이다.class Solution {public: Node* dfs(Node* cur, unordered_map& mp) { vector neighbour; Node* c..

https://leetcode.com/problems/coin-change/description/1. 리트코드 초기화주의리트코드는 아래 함수를 모든tc에 대해 재실행하는듯하다.따라서 이전 dp값을 그대로 사용해버린다.-> 함수내에서 초기화 해주면 된다.int dp[10000+4]; //dp [i][j] : i원을 달성하는 최소 동전갯수, j번째 동전추가시class Solution {public: int coinChange(vector& coins, int amount) { // memset(dp,0,sizeof(dp)); //리트코드는 전역변수 재사용하기땜에 초기화해줘야하는듯?!! 2. 동전dp복습1. 최솟값 구하기는 dp를 최대값으로 초기화해야 후에 min()함수를 쓰기 쉬워진다!!!..

https://leetcode.com/problems/climbing-stairs/1. 전체코드int dp[45+4];int N;class Solution {public: //해당 층에 올랐을때, 그때 경우의수 int go(int cur){ //coutN){ return 0; } if(cur==N){ return 1; } if(dp[cur]!=-1) return dp[cur]; dp[cur]=0; dp[cur]+=go(cur+1); dp[cur]+=go(cur+2); return dp[cur]; } int climbStairs(int..

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]; ..

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..

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); ..

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