백트래킹

1. 문제 풀이 백트래킹 + 너비우선탐색으로 풀이함, 5 * 5 배열의 위치값을 선형 자료구조에 모두 저장한 다음 백트래킹으로 7개의 위치를 뽑은 뒤 flood fill 기법으로 모두 연결되어 있는지 확인하면서 이다솜파의 개수를 카운팅해 소문난 칠공주인지를 판별했습니다.  2. 코드// Authored by : chjh2129#include /* 5 * 5의 위치 (i, j)를 모두 벡터에 저장한 다음 백트래킹으로 7개의 위치 정보를 뽑아 가져온다. 뽑아온 7개의 위치가 서로 연결되어있고 이다솜파가 4명인지 너비우선탐색으로 확인 BFS는 최대 7개의 칸만 확인한다 O(7 * 4) = O(1) // memset 사용으로 O(n*n) 25개를 중복없이 7개를 뽑는 경우의 수는 25C7 = 48만..

1. 문제 풀이 메모리제한이 4MB이므로 에라토스테네스의 채로 풀 수 없음. 각 자릿수에 1~9 범위의 수를 순차적으로 추가해 소수인지 판별하는 백트래킹을 사용하여 문제를 풀이함. n자리의 숫자가 2, 3, 5, 7만 들어올 수 있므로 시간 내 해결될 것 같아는 추측을 하였음. 구현은 단순 백트래킹임. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector..

1. 문제 풀이 백트래킹의 well-known 문제인 N-Queen의 응용 set임. Queen 대신 비숍으로 대체 임의의 위치 (x, y)에 비숍이 위치할 때 어떤 대각선과 역대각선을 점유하는지 알아야 함, ( x, y ) 값을 가공해 대각선 정보들을 linear 하게 관리할 수 있음. 체스판의 크기가 N이고 임의의 위치 ( x, y )를 x + y, y - x로 대각선 정보와 역대각선정보를 linear 하게 관리할 수 있음 대각선 ( x + y ) = { 0, 1, 2, ..., 2*N-2 }역대각선 ( y - x ) = { -N + 1, -N + 2,..., 1, 0, 1,..., N-2, N-1 } 역대각선은 음수가 나오므로 +N-1를 통해 조정할 필요가 있음 역대각선( y - x + N - 1 ..