GW LABS

피보나치 수열을 구할 때 보통 재귀호출과 동적계획법 등을 통해서 구하는 문제들이 많다. 그러나 이 문제는 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