GW LABS

영어 기수로 수를 샜을 때, 몇 개의 영어 기수로 수를 샜을 때, 몇 개의 문자를 사용했는지 계산하는 문제이다. 처음 문제를 보고 겁을 먹었지만, 해쉬 테이블을 사용하면서 규칙을 유추해보니 생각보다 쉬운 문제였다. #include #include #include using namespace std; map cardinal = { {1, 3}, {2, 3}, {3, 5}, {4, 4}, {5, 4}, {6, 3}, {7, 5}, {8, 5}, {9, 4}, {10, 3}, {11, 6}, {12, 6}, {13, 8}, {14, 8}, {15, 7}, {16, 7}, {17, 9}, {18, 8}, {19, 8}, {20, 6}, {30, 6}, {40, 5}, {50, 5}, {60, 5}, {70, 7..

처음에 이 문제를 접근할 때 long double을 이용해서 해결을 하려고 했지만 숫자가 너무 컸기 때문에 자리수를 모두 구할 수 가 없었다. 자료형의 최대치를 넘어가는 숫자를 연산하려면 어떻게 해야할까? 단순히 동적배열에 연산을 하고 자리수에 해당하는 숫자를 연속적으로 할당하면 해결할 수 있다. #include #include #include using namespace std; int main() { vector a; a.push_back(2); int cases = 999; while (cases--) { for (int idx = 0; idx < a.size(); idx++) a[idx] *= 2; for (int idx = 0; idx = 10) { if (idx == a.size() - 1) ..

해당 문제는 백트래킹 방식으로 연속된 부분수열을 포함하지 않는 수열을 만들어내는 문제이다. 생각해내는데 많은 시간이 들었고, 수열을 체크하는 함수 디버깅에 많은 시간이 소요됐다. 집중할 수 있는 환경을 만들고, 내 알고리즘을 먼저 의사코드로 만들어 낸 후 작업을 진행하는 훈련을 계속 진행해야한다. 아래는 정답 소스이다. #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..

처음 접근할 때에는 모든 분해합을 구하면서 가장 작은 생성자를 구하려고 했다. 이럴 경우 숫자가 커지면 커질수록 생성자를 계산하는 과정이 늘어나게 된다. 해법은 입력으로 들어온 숫자에서 자리수 * 9를 빼주면 범위를 상당히 좁힐 수 있다. 아래는 해당 구현법을 적용한 C++ 소스이다. #include using namespace std; int cntPos(int number) { int cnt = 0; while (number) { number /= 10; cnt++; } return cnt; } int sumPosNumbers(int number) { int sum = 0; while (number) { sum += number % 10; number /= 10; } return sum; } int ..

코딩 인터뷰 문제를 풀면서 테스트 케이스는 통과해도, 시간 초과로 통과하지 못해 좌절해본 경험이 있는가? 어떻게든 실행시간을 줄여보려고 코드를 튜닝하지만 제한된 시간의 압박과 초조함이 코드를 더 엉망으로 만든다. 코드를 쓰기 전에 내 알고리즘의 성능을 대략적으로 판단할 수 있다면 이런 불상사를 막을 수 있을 것이다. 이번 포스팅에서는 시간 복잡도를 빠르게 판단할 수 있는 방법을 정리한다. 순서대로 내 알고리즘에 적용해보자. 1. 반복문 가장 먼저 봐야할 부분은 반복문이다. 반복문이 몇 번 중첩되어 있는지부터 확인해보자. 중첩되어 있지 않은 반복문은 심플하게 N회를 순회하니까 O(N)이라고 판단할 수 있을 것이다. N번을 반복하는 반복문이 한 번 중첩되어 있다면 N * N회, O(N^2)이라고 판단할 수 ..