GW LABS

해당 문제는 이진 탐색을 연습할 수 있는 문제였다. 재귀함수를 이용해서 이진 탐색을 구현했지만 한 번에 구현하진 못했다. 탐색 범위를 잘 지정해주는 것이 이진 탐색 구현의 핵심인 것 같다. #include using namespace std; int container[1000000]; int question[100000]; int binarySearch(int startIdx, int endIdx, int target) { if (startIdx > endIdx) return -1; int middle = (startIdx + endIdx) / 2; if (target < container[middle]) { return binarySearch(startIdx, middle - 1, target); } ..

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

해당 문제는 백트래킹 방식으로 연속된 부분수열을 포함하지 않는 수열을 만들어내는 문제이다. 생각해내는데 많은 시간이 들었고, 수열을 체크하는 함수 디버깅에 많은 시간이 소요됐다. 집중할 수 있는 환경을 만들고, 내 알고리즘을 먼저 의사코드로 만들어 낸 후 작업을 진행하는 훈련을 계속 진행해야한다. 아래는 정답 소스이다. #include #include using namespace std; string numbers[3] = {"1", "2", "3"}; bool checkSeries(const string& series) { bool result = true; int sizeIdx = 2; int firstIdx = 0; int seriesSize = series.size(); if (seriesSize

1~N까지 차례대로 적힌 수열에서 연산자들을 선택하여 전체 계산결과가 0이 되도록 만드는 문제이다. 문제 분류가 백트래킹으로 되어 있는만큼 전형적인 백트래킹 기법으로 풀이가 가능하다. 시간을 많이 허비했는데 적절한 자료구조와 c++ 벡터에서 요소를 지우고 난 후에 인덱스를 어떻게 처리할 것인지 로직구성에 애를 먹었다. #include #include #include using namespace std; vector opers; char oper[3] = {' ', '+', '-'}; int calculate(int N) { vector tmp; vector eraseIdx; deque numbers; // 임시 숫자 배열생성 for (int i = 1; i

위의 그림처럼 2*n 그리드에에 2 * 1 크기의 블럭을 채울 수 있는 방법의 수를 구하는 문제이다. 처음에는 그리드에 대한 배열을 생성해서 브루트포스 방식으로 모든 방법을 탐색하려고 했다. 차분히 더 생각을 해보니 그런 배열은 필요가 없고 블럭을 세로로 배치하는 경우에는 1만큼 이동하고, 가로로 배치하는 경우에는 2만큼 이동했다고 생각하면 간단한 재귀함수로 풀이가 가능하다. 아래는 아이디어를 구현한 결과물이다. #include using namespace std; int answer = 0; void fillGrid(int idx, int len) { // 기저사례: 범위를 넘었다면 종료 if (idx > len) return; // 기저사례: 끝까지 채웠다면 종료 if (idx == len) { an..