GW LABS

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