Algorithm

[알고리즘] 리트코드 238. Product of Array Except Self c++ // 배열, 누적곱, rbegin, partial_sum

https://leetcode.com/problems/product-of-array-except-self/description/* 풀이1(케이스 분류)경우의수를 나누고구현i) 0의갯수가 0개인경우ii) 0의갯수가 1개인경우iii) 0의갯수가 2개이상인경우class Solution {public: vector productExceptSelf(vector& nums) { vector ret; int zero_count=0; int total_product=1; for(auto num : nums){ if(num==0) zero_count++; else total_product*=num; } ..

[알고리즘] 리트코드 45. 점프 게임 II c++ // dp, 그리디 bfs

* 나의문제점 : 너무 그리디로 접근하려고함그리디는 최후의 수단임.완탐-> 완탐dp -> pq,정렬 -> 이분탐색 ->  ... -> 그리디 순으로 접근하는게 맞음. * 완탐 * 완탐 + dpint dp[10000+4];vector nums;class Solution {public: int jump(vector& _nums) { memset(dp,-1,sizeof(dp)); nums=_nums; return dfs(0); } int dfs(int pos){ if(pos>=nums.size()-1){ return 0; } if(dp[pos]!=-1) return dp[pos]; dp[..

[알고리즘] 리트코드 116. 각 노드의 다음 오른쪽 포인터 채우기 c++ // bfs 트리순회

* 의사코드핵심은 rightNode에 직전우측노드를 캐시해놓고next를 캐시된 그걸로 대입해주는것이다.레벨별로 (rightNode의 초기값은 nullptr 이다.)  * 전체코드class Solution {public: Node* connect(Node* root) { if(!root) return nullptr; //null check 후에 root->next 등에 접근가능함 queue q; q.push(root); while(q.size()){ Node* rightNode = nullptr; for(int i=q.size();i;i--){ //레벨별 구분위한 반복문(1,2,4...) ..

[알고리즘] 리트코드 최대하위배열 c++ // dp

* 의사코드- dp[i] : i번째까지 부분수열중 최대합2가지 경우의수가 있다.i) 이전값을 버리고, 새로시작하는경우ii) 이전값에서 나를 더하는경우둘중에서 큰값을 택하면된다.* 전체코드int dp[100000+4];class Solution {public: int maxSubArray(vector& nums) { dp[0]=nums[0]; for(int i=1;i * 번외 : 탑다운 dp- 완탐재귀class Solution {public: int maxSubArray(vector& nums) { return solve(nums, 0, false); } int solve(vector& A, int i, bool mustPick) { //..

[알고리즘] 리트코드 고유경로 c++ // dp 모든유형

https://leetcode.com/problems/unique-paths/description/* 완탐class Solution {public: int uniquePaths(int m, int n, int i = 0, int j = 0) { if(i >= m || j >= n) return 0; // reached out of bounds - invalid if(i == m-1 && j == n-1) return 1; // reached the destination - valid solution return uniquePaths(m, n, i..

100C2 X 98 C 2 조합 구현

if(v==1) v1.push(index)else remain 백터에 넣는다.remain벡터에 대해서 다시 while_permutation을 반복한다. ex) 0 0 0 0 1 1 (v)idx : 0 1 2 3 4 5 -> v1=[4,5]-> remain : 0 0 0 0 -> 0 0 1 1-> 조합돌림v2 : [2. 3]

프로그래머스 상담원 인원 c++ // 우선순위큐, 중복조합(백트래킹)

https://school.programmers.co.kr/learn/courses/30/lessons/214288 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 의사코드i) 상담사 분배  경의의수 구현상담유형=5일때, 상담사=20명을 분배해야한다.이때, 최소 상담사는 1명씩 있어야한다. -> 15명을 5개칸에 분배해야한다[ 1 1 1 1 1] [ 0 0 0 0 0] 서로다른5자리에서 중복을포함해 15개를 고르면된다. ex) 첫째자리만 15번고르면 상담사가 [16 1 1 1 1]이 된다.중복조합의 구현은 st를두고, vis체크를 없애면 된다.모든 상담사..

리트코드 3. 반복되는 문자가 없는 가장 긴 부분 문자열 c++ // 슬라이딩 윈도우

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/* 의사코드1. map에 해당문자의 등장횟수기록2. 해당문자가 2회이상등장 -> 등장횟수가1이 될때까지 l을 우측으로 조정3. 모든 중복문자없는 부분문자열을 탐색하면서 그때의 최대값을 ret에 저장함* 전체코드class Solution {public: int lengthOfLongestSubstring(string s) { unordered_map m; //m[a]=2, a의 등장횟수가2임 int r=0,l=0,n=s.size(), ret=0; while(r1){ //2회이상인경우, 1회가되도록 조정해야함..