본문 바로가기

Programming Problems/Recursive

(6)
이중 리스트의 모든 조합을 출력해보자. [["quick","slow"],["brown","red"],["fox","dog"]] 의 모든 조합을 출력해 보자.예시) quick brown fox void printcombinations(vector & data, int curr, vector maker){if(curr == data.size()){for(string x : maker) cout
폭탄 터트려서 최대 점수 얻기 스테이트가 정리가 안되서 결국 완전탐색 선에서 귀결되는 문제가 된다고 하네. DP 솔루션이 있을까? 근데 DP가 별거냐 그냥 완.탐에 범위상한 붙인거지.. int N, v[22], r[22], dp[ 1
안드로이드의 가능한 모든 비밀번호의 갯수를 세 보자. 제곧내. 세는 프로그램을 짤것. 생각해 보면 이건 모두 서로 연결된 완전 그래프이고, 찾는건 해밀토니안이다. 즉 갯수는 9! 가지.. 그냥 permutation을 찾으면 된다. void printpermutation(unordered_set buffer, vector maker){if(buffer.size()==){cout
스트링 하나를 다른 한쪽에 끼워넣는 경우의 수 구하기 스트링 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){printa..
종이 최소 갯수의 정사각형 조각으로 자르기 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