Algorithm

리트코드 2. 두개의숫자추가 c++ // stoi 주의점, 노드 begin 저장방법, 두 링크드리스트 덧셈방법

https://leetcode.com/problems/add-two-numbers/description/ * stoi 주의점21억( 2,147,483,647 )== 문자열로 10자리만 벗어나도 out of range 가뜸-> stoll을 사용할것 ( 9,223,372,036,854,775,807)-한계 : 20자리이상은 불가능함.-> 숫자계산으로 구현해야함. 문자열꼼수 안통해 * 기존코드숫자를 문자열로 바꾸면서 덧셈하고해당 숫자를 다시 노드로 바꿈- 문제 : stoi 에서 stoll로 해도 ll의 범위도 벗어나버림/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * List..

리트코드 57 삽입간격 c++ // 구현, 라인스위핑은 케이스 분류하라

https://leetcode.com/problems/insert-interval/description/1. 의사코드이때, 핵심은 new를 탐색완료한것중 제일 우측의 간격으로 유지하는 점이다. 2. 전체코드class Solution {public: vector> insert(vector>& intervals, vector& newInterval) { vector> ret; //new에는 현재 탐색완료한 간격중 제일 우측의 간격이 들어있다. for(auto interval : intervals){ if(interval[1]시간복잡도 : O(N) 추정

[알고리즘] 구름 해외주식투자 c++ // 소수점 절사방법, 비교방법, 로그값구하는법

https://level.goorm.io/exam/150257/00%EC%A6%9D%EA%B6%8C-%EC%A3%BC%EC%8B%9D%ED%88%AC%EC%9E%90%EC%9E%90-a/quiz/1 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 1. 소수점 절사방법ex)5.41에서 1을 절사(버리기)하려면10을곱한후 floor 하면된다5.41 -> 54.1 -> 54 2. 소수점 비교방법직접비교 : | a- b| 10^n 을 곱해서 정수로 바꾼후 비교하는걸 추천함!값이 중요한게 아니라 대소만 보면되므로 정수로 바꿔서 == 비교가 정확한듯? 2.5 .로그값구하는법log2 함수를 쓰면된다.log 2 (10) 만 = 16 이다.// function..

리트코드 153 회전 정렬 배열에서 최소값 찾기 c++ // 이분탐색

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/1. 의사코드우리는 보물인 0을 찾는것이다.[4 5 6 7 0 1 2]st      m       enmid>en이면, 보물이 우측에 있는것이다. -> st=mid+1[0 1 2]에서mid 0 en=mid; //mid-1아님[0 1]에서mid=0 보물이 좌측 -> en=0;en과 st가 0으로 수렴했고, 그곳이 보물이다! 2. 전체코드class Solution {public: int findMin(vector& nums) { int st=0,en=nums.size()-1; while(st

리트코드 338. Counting Bits c++ // 1의갯수세기, dp, 비트

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

리트코드 133 그래프 클론 c++ // 그래프 복사하는방법

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

리트코드 322 코인변경 c++ // 동전dp복습, 리트코드 초기화주의

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()함수를 쓰기 쉬워진다!!!..

리트코드 70 계단오르기 c++ // 재귀함수 리턴값 전파 이해, dp

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