GW LABS

나는 C++와 같은 unmanaged 언어를 실무에서 다뤄볼 수 있는 기회가 지금까지 없었다. 컴퓨터 공학의 기본기를 익히기 위해서 C/C++같은 언어를 꾸준히 수련하는 것이 필요하다고 생각되어 이 포스팅을 시작해보려고 한다. C++로 기본적인 자료구조를 구현해보면서 컴퓨터 공학의 기본기를 수련해보자! 1. ArrayList (동적배열) 오늘의 주제는 동적배열이다. 동적배열은 크기가 가변적으로 늘어나는 배열이다. 초기화한 배열의 크기가 모자르게 되면 현재 배열보다 2배 큰 배열을 할당하고, 기존에 있던 값을 복사한다. 이렇게 배열크기를 조정하면 삽입과 인덱스 접근에서 시간복잡도 O(1)을 보장할 수 있다. 여기서 중요하게 볼 점은 동적배열의 크기가 입력에 비례해서 커진다는 점이다. 그렇기 때문에 입력과 ..

해당 문제는 이진 탐색을 연습할 수 있는 문제였다. 재귀함수를 이용해서 이진 탐색을 구현했지만 한 번에 구현하진 못했다. 탐색 범위를 잘 지정해주는 것이 이진 탐색 구현의 핵심인 것 같다. #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); } ..

자료구조에 익숙해지기 위해 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..