Twinparadox Factory

시간 제한 : 2초메모리 제한 : 128MB 입력첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다. 출력영상을 압축한 결과를 출력한다. 소스코드#include #include #include using namespace std; vector tree; void quadtree(int row, int col, int n) { if (n == 1) { cout input[i]; for (int i = 0; i < n; i++) { tree.push_back(vector(n, 0)); for (i..

이전 포스팅에서도 말했다시피, 일반적인 재귀 방법을 사용하는 건 시간이 오래 걸린다는 단점을 가지고 있다. 메모화재귀는 동적계획법을 재귀적으로 사용하는 것으로 동적계획법의 일종으로한 번 계산이 진행된 것은 추가로 진행하지 않는 것을 목표로 하기 때문에깊이 우선 탐색을 응용해 (1,1)에 하위에서 생성된 계산값을 미리 작성해두어만일 다시 접근이 이뤄지면 그 값을 반환시키는 것을 말한다. 깊이 우선 탐색을 통해서 일반적인 재귀 방법으로 접근했을 때 중복되는 작업들을 많이 걸러낼 수 있어서제한 시간 초과라는 문제를 극복할 수 있다. const int h = 5, w = 4; int Memo_recursion[h + 1][w + 1]; int dfs(int nowh, int noww) { if (nowh > h..

B A 아마 고교시절 순열조합 부분에서 자주 접하는 문제 중 하나로,A 지점에서 B 지점으로 갈 때 최단거리의 경우의 수가 얼마나 되는지 구하는 것이 목표인 문제다. 깊이우선탐색을 사용할 때, 모든 기점마다 경로를 선택해야 하고 이 경우 30번정도 그런 과정이 필요하다.따라서 Big O는 O(2^(w+h))가 되어 2^30인데 10억이 넘어가는 수치가 된다.연산 시간이 오래 걸려 썩 좋은 방법이 아니다. 우리는 이 문제를 고교시절 기계적으로 푸는 방법을 터득한 바 있다.바로 이항정리에 근거한 조합을 이용하는 방법이고9C4=126이라는 정답에 빠르게 근접할 수 있다.Big O 또한 O(w+h)로 계산량도 적어 매우 효율적으로 보인다.그러나, 이는 모든 지점을 통과할 수 있을 때나 가능하다는 제한적인 케이스..