본문 바로가기

Programming Problems/Recursive

(6)
이중 리스트의 모든 조합을 출력해보자. [["quick","slow"],["brown","red"],["fox","dog"]] 의 모든 조합을 출력해 보자.예시) quick brown foxvoid printcombinations(vector> & data, int curr, vector maker){if(curr == data.size()){for(string x : maker) cout << x << " ";cout << endl;return;}// general casefor(int i = 0 ; i < data[curr].size() ; i++){maker.push_back(data[curr][i]);printcombinations(data,curr+1,maker);maker.pop_back()..
폭탄 터트려서 최대 점수 얻기 스테이트가 정리가 안되서 결국 완전탐색 선에서 귀결되는 문제가 된다고 하네. DP 솔루션이 있을까? 근데 DP가 별거냐 그냥 완.탐에 범위상한 붙인거지..int N, v[22], r[22], dp[ 1 << 22 ]; // init dp to -1 == not done bool Contains(int mask, int i) { return mask & (1 << i); } bool Conflicts(int i, int j) { // j affects i return (abs(i-j) <= r[j] || abs(i+N-j) <= r[j] || abs(j+N-i) <= r[j]); } int Go(int used_mask) { if (dp[used_mask] != -1) // already done befo..
안드로이드의 가능한 모든 비밀번호의 갯수를 세 보자. 제곧내. 세는 프로그램을 짤것.생각해 보면 이건 모두 서로 연결된 완전 그래프이고, 찾는건 해밀토니안이다.즉 갯수는 9! 가지..그냥 permutation을 찾으면 된다.void printpermutation(unordered_set buffer, vector maker){if(buffer.size()==){cout << maker << endl;return;}for(auto it = buffer.begin() ; it!=buffer.end() ; it++){maker.push_back(*it);buffer.erase(it);printpermutation(buffer, maker);buffer.insert(maker.back());it = buffer.find(maker.back());..
스트링 하나를 다른 한쪽에 끼워넣는 경우의 수 구하기 스트링 A를 순서를 유지한채 B 사이사이에 끼워넣는 모든 경우의 수를 출력하자.ex) AB 와 CD의 경우ABCDACBDACDBCABDCADBCDAB솔루션: 매 경우에 대해 둘중 한쪽의 첫 문자를 새로운 문자열에 끼워넣는다. 한쪽을 다 썼으면 나머지 한쪽을 전부 넣는다. 양쪽을 모두 썼으면 그걸 출력한다.void printall(unordered_set & res, string A, string B, int iA, int iB, string maker){ if(A.size()==iA&&B.size()==iB){res.insert(maker);return;}if(A.size()!=iA){printall(res,A,B,iA+1,iB,maker+A[iA]);}if(B.size()!=iB){pri..
종이 최소 갯수의 정사각형 조각으로 자르기 13 * 29 : 13*13 2개, 3*3 4개 1* 1 3개 = ans : 9풀이 : 아무래도 짧은 변을 한 변으로 하는 정사각형을 긴 쪽으로 할 수 있는 만큼 만든 후에, 남은 길이를 재귀적으로 호출하면 된다.base case는 한쪽 길이가 1이면 조각의 수는 긴 쪽 길이이다.int findsquares(int M, int N){// base caseif(N==1) return M;// general caseint count = M/N;return count + findsquares(N,M%N);}시간 복잡도 .. O(log 루트N) 쯤 되지 않을까? 작은 것 보다 작게 만드니까 작은 것으로 만든다고 가정하면 대략 logN이고..
행렬에서 붙어있는 연속한 숫자들 중 가장 긴 조합 찾기 Q 행렬에는 1 ~ N^2 의 서로 다른 숫자로 구성되어 있다..ex)1 5 92 3 84 6 7>> ans : 6 7 8 9풀이 : 각 점에 대해 연속된 숫자가 주위에 있는지 확인한다. 재귀적으로 따라간다. 길이가 최대보다 길면 기록한다.크게 재귀가 많이 일어나지는 않을 것으로 보이고 풀고 나면 DP 캐핑이 될 것 같기는 하다.참신한 최선 풀이vector(N^2,false) 에다가 i이 i-1 과 붙어있는가? 의 값을 찾아서 채운다.최종적으로 이 불리안 어레이의 true가 가장 긴 부분이 정답이다.https://www.careercup.com/question?id=5147801809846272