백트래킹이란?백트래킹(Backtracking)이란, 현재 상태에서 가능한 모든 후보를 탐색하여 정답을 찾도록 하는 알고리즘을 말한다.이때 일반적인 브루트포스(Brute Force) 알고리즘과 백트래킹의 차이점은, “정답을 찾는 도중 정답이 될 가능성이 없는 경우, 그 즉시 되돌아가 다른 경로를 탐색하여 답을 찾는다”는 것이다. 백트래킹이 작동되는 방식은 크게 다음과 같다:현재 상태에서 가능한 후보 중 하나를 고른다.해당 후보에서 재귀적으로 다음 단계를 탐색해 나간다.탐색하는 중, 정답이 될 수 없는 경우 탐색을 종료한다.주어진 조건을 모두 만족하는 경로인 경우, 해당 경로를 정답으로 처리한다.탐색이 끝나면, 상태를 원래대로 되돌린 후, 다른 후보를 골라 반복한다.문제를 풀기 위해서 위와 같은 상태 공간 ..

문제 링크Question스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.1번2번3번4번5번1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다. CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다. CCTV는 회전시킬 수 ..

문제 링크Question총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.화합과 ..

문제 링크Question바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을..