GW LABS

자료구조에 익숙해지기 위해 HackerRank 문제들을 공부중이다. 그 중 미디움 난이도 트리문제를 보면서 재미있었던 문제가 바로 이 문제이다. 허프만 디코딩 문제는 트리를 순회하면서 이진 문자열을 디코딩하는 문제이다. 문제를 접근한 전략은 간단했다. 이진 문자열을 부분으로 자르면서 대응되는 문자가 있는지 없는지 찾아보는 것이다. 부분 문자열의 길이를 늘려가면서 트리를 순회하면 비교적 간단하게 풀이할 수 있는 문제였다. void decode(String s, Node root) { String answer = ""; String target = ""; while (s.length() > 0) { for (int idx = 1; idx

굉장히 재미있는 문제였다. 로직 자체는 간단하다. 숫자에 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 ..