본문 바로가기

Programming Problems/Recursive

이중 리스트의 모든 조합을 출력해보자. [["quick","slow"],["brown","red"],["fox","dog"]] 의 모든 조합을 출력해 보자.예시) quick brown foxvoid printcombinations(vector<vector<string>> & data, int curr, vector<string> maker){if(curr == data.size()){for(string x : maker) cout << x..
폭탄 터트려서 최대 점수 얻기 스테이트가 정리가 안되서 결국 완전탐색 선에서 귀결되는 문제가 된다고 하네. 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, in..
안드로이드의 가능한 모든 비밀번호의 갯수를 세 보자. 제곧내. 세는 프로그램을 짤것.생각해 보면 이건 모두 서로 연결된 완전 그래프이고, 찾는건 해밀토니안이다.즉 갯수는 9! 가지..그냥 permutation을 찾으면 된다.void printpermutation(unordered_set<int> buffer, vector<int> maker){if(buffer.size()==){cout << maker << endl;return;}for(auto it..
스트링 하나를 다른 한쪽에 끼워넣는 경우의 수 구하기 스트링 A를 순서를 유지한채 B 사이사이에 끼워넣는 모든 경우의 수를 출력하자.ex) AB 와 CD의 경우ABCDACBDACDBCABDCADBCDAB솔루션: 매 경우에 대해 둘중 한쪽의 첫 문자를 새로운 문자열에 끼워넣는다. 한쪽을 다 썼으면 나머지 한쪽을 전부 넣는다. 양쪽을 모두 썼으면 그걸 출력한다.void printall(unordered_set<string> & res, string A, string B, int iA, i..
종이 최소 갯수의 정사각형 조각으로 자르기 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..
행렬에서 붙어있는 연속한 숫자들 중 가장 긴 조합 찾기 Q 행렬에는 1 ~ N^2 의 서로 다른 숫자로 구성되어 있다..ex)1 5 92 3 84 6 7>> ans : 6 7 8 9풀이 : 각 점에 대해 연속된 숫자가 주위에 있는지 확인한다. 재귀적으로 따라간다. 길이가 최대보다 길면 기록한다.크게 재귀가 많이 일어나지는 않을 것으로 보이고 풀고 나면 DP 캐핑이 될 것 같기는 하다.참신한 최선 풀이vector<bool>(N^2,false) 에다가 i이 i-1 과 붙어있는가? 의 값을 ..