Mini

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

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

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

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

https://www.acmicpc.net/problem/140031. LIS 오류수정이전문제는  Ai가 1부터시작하기 때문에if(lis[idx]==0) 이 해당 num이 처음등장하는 개큰수임 과 필요충분조건이 된다하지만, Ai에 0이 있는경우 이 '0'이 처음등장한다는 의미인지 lis안에 계산된 '0'이 라는 의미인지 불명확하다!!!// https://www.acmicpc.net/problem/14003 따라서, if(idx == len) 이렇게 하는것이 Ai의 범위에 상관없이 처음등장하는 개큰수라는 것과 필요충분조건이다!!//lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!! 예시) lis : -2 0 0 5에서 -1삽입시 lis[idx]==0이고, len+1이된다.하지만, len증..

https://www.acmicpc.net/problem/12015 1. 설명1. 기존 dp : O(n^2) // n개입력에대해 * 앞의n개를 살펴보며 최대값을 찾아야함2. lower_bound : lb성질에 의해 n개입력 * lgn으로 구현쌉가능 2. 의사코드1. num을 1개씩보면서2. (lis에없는) 개큰수가 등장한경우, lis길이+13. 나머지는 lb성질에의해 날먹된다.작은값이오면, 기존값을 작은값으로 교체함 i)작은값이옴 -> 10 20 30 에서 25in, idx=30, 30값이 25로 교체됨ii)같은값이옴 -> 10 20 30 에서 20in, idx=20, 변화없음iii)개큰값이옴 -> 10 20 30 [ ]에서 40in , idx=0, lis에 추가해줌4. ex)10 -> 저장, lis+1..

https://www.acmicpc.net/problem/147191. 의사코드1. 높이에따라 2차원배열을 만들어줌2. 값이0인곳에 물이 찰수있는지 탐색함3. 좌측이 1이있고 우측에 1이있어야 물이찰수있음빈칸들(0)에 대해 O,X 가능한지 불가능한지 조사함.2. 전체코드#include using namespace std;int Y,X,num, a[504][504],ret;vector> v; //탐색대상위치int left(int y, int x) { if (x = X) { return 0; } if (a[y][x] == 1) return 1; return right(y, x + 1);}//해당좌표에 빗물이 찰수있는지int go(int y, int x) { //좌측에 ..

https://www.acmicpc.net/problem/110001. 강의실배정 vs 회의실배정1. 회의실배정 : 시작시간이 빠른것부터 배정하면 된다. 배정이가능하다면, ret++ 하면된다.end변수를 사용한다 // 가장최근에 끝난 회의의 종료시간int end = 0; int tot = 0; while(pq.size() > 0){ sub = pq.top(); if(end 2. 강의실배정 :  시작시간기준으로정렬, pq는 종료시간기준으로 정렬top.sec과 입력값.first를 비교하며 가능하다면(즉, 같은 회의실 사용으로 처리하는것이다. -> pq.size가 써야되는 강의실의 수가 된다. 2. pq cmp 구현시 주의점1. cmp는 매개변수가 같으면 거짓을 리턴해야함2..