Algorithm

[Algo] 백준 소문난칠공주 c++ // 조합, 완탐, 갯수세기는 int dfs

일단 이문제는 2번째 푸는  문제이다.근데 못풀었다...모 기업 코테에서 비슷한 문제가 나와 다시 복습하였다. * 못푼이유설계도가 없으니 중간에 막히면 코드만 수정함 -> 점점 스파게티가 되어 망하였다. 아래정도 설계는 꼭하자!* 의사코드25C7 구현vector를 넥퍼돌리면서 1인부분의 idx를 selected에 넣으면된다.이때, 지도에도 표시해둔다. //나중에 선택된곳만 갈수있도록 제한해야하니까.i/5, i%5를 이용해, 값을 2차원으로 바꿔준다.이다솜 cnt > = 4 구현selected를 순회하면서 arr을 검사한다.이후 4이상인 경우만 dfs 검사로 보낸다.이때, selected 중 아무 좌표나 하나 보내면 된다.dfs 구현 - version 1dfs는 연결된 갯수가 7개이면, 정답을 +1 하면된..

[Algo] c++ next_permutation으로 조합 구현하기

//25C7 구현 // N개의 요소를 가진 벡터 생성, 뒤에서 K개만 1로 설정 n = 25; vector v(n); fill(v.end() - 7, v.end(), 1); int cnt = 0; do { cnt++; /*for (int i = 0; i

[알고리즘] 416. Partition Equal Subset Sum c++ 리트코드 // 완탐, dp

https://leetcode.com/problems/partition-equal-subset-sum/solutions/1624939/cpython-5-simple-solutions-w-explanation-optimization-from-brute-force-to-dp-to-bitmask/* 완탐-내생각 : 200C1 + 200C2 + 200C3 + ,... + 200C 200 == 2^200 //빡세다..-답 : 이진트리로 쉽게생각하면됨 // num[idx]를 sum1에 넣기 or sum2에 넣기 == 2^200vector nums;class Solution {public: int go(int idx, int sum1, int sum2){ if(idx>=nums.size()){ ..

[알고리즘] 리트코드 658. k개의 가장 가까운 요소 찾기 c++ // 이진탐색, 투포인터

* 완탐-내코드{차이, idx}를 저장하고차이로정렬하고, idx로 원본에 다시접근하는방법매우 비효율적임.class Solution {public: static bool cmp(pair p1, pair p2){ if(p1.first==p2.first){ //인덱스작은거우선 return p1.second findClosestElements(vector& arr, int k, int x) { vector> gabs; //{차이, 인덱스} for(int i=0;i ret; for(int i=0;i- 정답코드굳이 idx를 저장할필요없이 차이로 원본배열을 정렬해버리면됨.class Solution {public: vector findCl..

[알고리즘] 리트코드 417. Pacific Atlantic Water Flow c++ // dp

https://leetcode.com/problems/pacific-atlantic-water-flow/ * 완탐모든좌표에대해 모든곳을 가보면서 갈수있는지 검사함O(N * M * N * M )int dy[]={1,0,-1,0};int dx[]={0,1,0,-1};vector> heights;vector> ret;int vis[204][204],dp[204][204]; //해당좌표에서 바다로 갈수있는지int n,m;int a,b;class Solution {public: //해당좌표가 pacific바다로 갈수있는지, 좌-우 탐색 void dfs(int y, int x){ // if(x =m || y>=n){ // can go atlantic // b=1; ..

[알고리즘] leetcode 790. 도미노와 트로미노 타일링 c++ // dp

* 완탐1. 타일의 종류정리하기2. 상태정의 : 열번호, 이전이 완전한지 여부long mod = 1e9+7;int n;class Solution {public: long dfs(int i, int prevgab){ if(i==n && prevgab==0){ //success return 1; } if(i==n && prevgab == 1){ //fail return 0; } if(i>n){ //out of index return 0; } //이전열이 빈칸이있는경우, if(prevgab){ return dfs(i+1,0) ..

[알고리즘] 리트코드 19. 리스트 끝에서 N번째 노드 제거 c++ // 노드탐색

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/* 내풀이size를 찾고prev값이 없길래 저장하고,제거대상인 노드인경우, prev->next = cur->next로 바꿔줬다.ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ결과 :맨앞의 노드를 제거하는경우 오답이났음.이경우는 head = head -> next를 리턴하면 됬다./** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next..

[알고리즘] 리트코드 1696. 점프 게임 VI c++ // set, deque dp

https://leetcode.com/problems/jump-game-vi/ * 그냥 dppos N에대해 k번반복문 == O(N * K) -> 100억 -> 터진다.   vector nums; int k;int dp[100000+4];class Solution {public: int dfs(int pos){ //pos에서 그때의 최대점수 if(pos==nums.size()-1){ return nums[pos]; } if(pos>=nums.size()){ //배제 return -987654321; } if(dp[pos]!=-1){ return dp[pos]; } ..