'Programming Problems/Recursive'에 해당되는 글 6건

Programming Problems/Recursive

이중 리스트의 모든 조합을 출력해보자.

[["quick","slow"],["brown","red"],["fox","dog"]] 의 모든 조합을 출력해 보자.

예시) quick brown fox


void printcombinations(vector<vector<string>> & data, int curr, vector<string> maker){

if(curr == data.size()){

for(string x : maker) cout << x << " ";

cout << endl;

return;

}


// general case


for(int i = 0 ; i < data[curr].size() ; i++){

maker.push_back(data[curr][i]);

printcombinations(data,curr+1,maker);

maker.pop_back();

}


}


time complexity : O(M1M2...Mn)

Programming Problems/Recursive

폭탄 터트려서 최대 점수 얻기

스테이트가 정리가 안되서 결국 완전탐색 선에서 귀결되는 문제가 된다고 하네. 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 before?
        return dp[used_mask];
    dp[used_mask] = 0;
    for (int i = 0; i < N; i++)
        if ( ! Contains(used_mask, i) ) {
            bool ok = true;
            for (int j = 0 ; j < N ; j++)
                if (Contains(used_mask, j) && Conflicts(i,j)) {
                    ok = false;
                    break;
               } 
           if (ok)
               dp[used_mask] = max( dp[used_mask], v[i] + Go(used_mask | (1<<i)));
       }
    return dp[used_mask];
}

int main() {
	int i;
	scanf("%d", &N);
	for (i = 0 ; i < N ; i++)
		scanf("%d %d", &r[i], &v[i]);
	memset(dp, -1, sizeof dp);
	printf("%d\n", Go(0));
	return 0;
}


Programming Problems/Recursive

안드로이드의 가능한 모든 비밀번호의 갯수를 세 보자.

제곧내. 세는 프로그램을 짤것.


생각해 보면 이건 모두 서로 연결된 완전 그래프이고, 찾는건 해밀토니안이다.


즉 갯수는 9! 가지..


그냥 permutation을 찾으면 된다.


void printpermutation(unordered_set<int> buffer, vector<int> 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());

maker.pop_back();

}

}


time complexity : N! 번 호출, 각각에 대해 N번씩 재귀하니까.. O(N!^2) 쯤 되는가

Programming Problems/Recursive

스트링 하나를 다른 한쪽에 끼워넣는 경우의 수 구하기

스트링 A를 순서를 유지한채 B 사이사이에 끼워넣는 모든 경우의 수를 출력하자.


ex) AB 와 CD의 경우


ABCD

ACBD

ACDB

CABD

CADB

CDAB


솔루션: 매 경우에 대해 둘중 한쪽의 첫 문자를 새로운 문자열에 끼워넣는다. 한쪽을 다 썼으면 나머지 한쪽을 전부 넣는다. 양쪽을 모두 썼으면 그걸 출력한다.


void printall(unordered_set<string> & 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){

printall(res,A,B,iA,iB+1,maker+B[iB]);

}

}


시간 복잡도 : O(조합의 갯수)

공간 복잡도 : O(조합의 갯수)


조합의 갯수 ? : 0과 1이 각각 m과 n개 있는데 이걸 배치하는 방법의 수

그니깐, 모두 다른거라고 생각하고 순열을 구한 다음에 같은 것들의 조합을 나눠주자.


time complexity : O((m+n)!/m!n!)

space complexity : O((m+n)!/m!n!)




Programming Problems/Recursive

종이 최소 갯수의 정사각형 조각으로 자르기

13 * 29  : 13*13 2개, 3*3 4개 1* 1 3개 = ans : 9



풀이 : 아무래도 짧은 변을 한 변으로 하는 정사각형을 긴 쪽으로 할 수 있는 만큼 만든 후에, 남은 길이를 재귀적으로 호출하면 된다.

base case는 한쪽 길이가 1이면 조각의 수는 긴 쪽 길이이다.


int findsquares(int M, int N){

// base case

if(N==1) return M;

// general case

int count = M/N;

return count + findsquares(N,M%N);

}


시간 복잡도 .. O(log 루트N) 쯤 되지 않을까? 작은 것 보다 작게 만드니까 작은 것으로 만든다고 가정하면 대략 logN이고.. 

Programming Problems/Recursive

행렬에서 붙어있는 연속한 숫자들 중 가장 긴 조합 찾기 Q

행렬에는 1 ~ N^2 의 서로 다른 숫자로 구성되어 있다..


ex)

1 5 9

2 3 8

4 6 7


>> ans : 6 7 8 9


풀이 : 각 점에 대해 연속된 숫자가 주위에 있는지 확인한다. 재귀적으로 따라간다. 길이가 최대보다 길면 기록한다.

크게 재귀가 많이 일어나지는 않을 것으로 보이고 풀고 나면 DP 캐핑이 될 것 같기는 하다.


참신한 최선 풀이

vector<bool>(N^2,false) 에다가 i이 i-1 과 붙어있는가? 의 값을 찾아서 채운다.

최종적으로 이 불리안 어레이의 true가 가장 긴 부분이 정답이다.


https://www.careercup.com/question?id=5147801809846272