GW LABS

굉장히 재미있는 문제였다. 로직 자체는 간단하다. 숫자에 369가 몇 개가 들어가 있는지 세기만 하면 된다. 그러나 이 문제에서는 1억개의 범위가 주어질 수 있고 제한시간은 2초 이내이다. #include using namespace std; int cache[100000003]; int getClab(const int& number) { if (cache[number]) { return cache[number]; } else { int clab = 0; int target = number; while (target) { if (cache[target]) { clab += cache[target]; break; } else { int tmp = target % 10; if (tmp != 0 && tmp ..

동적계획법이 필요한 문제들에서 return 값이 있도록 재귀함수를 설계하는 연습을 진행 중이다. 해당 문제는 전형적인 동적계획법과 재귀함수를 이용해서 간단하게 풀이가 가능한 문제였다. #include using namespace std; unsigned long cache[100000]; unsigned long dfs(short number) { if (number == 0) { return 1; } if (cache[number]) { return cache[number]; } else { unsigned long sum = 0; for (int idx = 1; idx > number; cout

조합을 구하는 동적계획법 알고리즘을 조합을 구하는 동적계획법 알고리즘을 사용하면 간단하게 풀 수 있는 문제였다. 조합의 n값이 40 이상만 되도 int 자료형으로 표현할 수 없는데 이런 경우를 방지하기 위해 unsigned long으로 캐스팅해주면 문제는 없다. #include using namespace std; unsigned long combCache[100][100]; unsigned long comb(int n, int r) { if (n == r || r == 0 || n == 0) { return 1; } else { if (combCache[n][r]) { return combCache[n][r]; } else { return combCache[n][r] = comb(n - 1, r - 1..

#include #include using namespace std; #define SIZE 1001 #define SIZE_T 1000 int table[SIZE][SIZE]; int main() { int origin = (SIZE * SIZE); int row = 0, col = SIZE_T; int trigger = 0; // 0: 좌측, 1: 하단, 2: 우측, 3:상단 long long unsigned int answer = 0; int step = SIZE * SIZE; while (step--) { if (abs(row - col) == 0 || abs(row + col) == SIZE_T) answer += origin; table[row][col] = origin; origin--; /..

피보나치 수열을 구할 때 보통 재귀호출과 동적계획법 등을 통해서 구하는 문제들이 많다. 그러나 이 문제는 1000자리 까지 구해야하기 때문에 unsigned long long 자료형으로도 표현할 수 없다! 이 문제도 마찬가지로 동적배열을 통해서 숫자를 표현해야한다. #include #include using namespace std; int main() { vector fibo; fibo.push_back(1); vector num; num.push_back(1); vector tmp; unsigned int idx = 2; while (true) { tmp = fibo; for (int i = 0; i < num.size(); i++) { fibo[i] += num[i]; } for (int i = 0..

해당 문제의 경우 boolean 배열 통해서 초과수를 저장해 두는 것이 효율적이다. 동적 배열에 무식하게 초과수를 넣어두기 시작하면 다시 찾아야하는 오버헤드가 발생한다! #include #include #include using namespace std; bool bignumTable[28200]; bool isBignum(int n) { int divisorSum = 0; for (int i = 1; i n) { return true; } else { return false; } } int main() { // 1 - 28123 까지의 초과수를 구한다. for (int i = 1; i

해당 문제는 단순히 동적계획법 패턴만으로는 메모리 초과가 발생하기 때문에 다른 방법을 사용했다. 분할과 정복 알고리즘을 사용하면 비교적 쉽게 풀 수 있다. 여기에 동적계획법을 적용하면 만족할 만한 실행속도도 확보할 수 있다. #include using namespace std; unsigned int cache[50000]; unsigned int mul(unsigned int n, unsigned int k) { if (k == 0) { return 1; } else if (k == 1) { return n; } else { unsigned int oddTrigger = 0; if (k % 2 == 1) oddTrigger = 1; unsigned long long left, right; if ((k ..

20번, 21번 문제는 이전에 풀었던 방식을 20번, 21번 문제는 이전에 풀었던 방식을 적용하면 빠르게 풀 수 있는 문제였다. 친화수 문제인 21번은 주먹구구식으로 풀이해도 0.2초 풀이시간이 나오므로 어렵지 않은 문제다. 단순히 약수를 구해서 더하고 친화수인지 아닌지 판단하는 로직으로 풀이했다. 아래에 코드를 첨부한다. #include using namespace std; int divisorSum(int n) { int sum = 0; for (int i = 1; i < n - 1; i++) { if (n % i == 0) sum += i; } return sum; } int main() { int answer = 0; for (int num = 1; num