가취공부하자

1. 문제 https://www.acmicpc.net/problem/9663 2. 풀이 BackTracking 알고리즘을 사용한다 1. 퀸이 공격할 수 있는 방향을 체크해야 한다. 퀸이 갈 수 있는 방향 같은 행 같은 열 (왼쪽 ->오른쪽 기준) 올라가는 대각선 (왼쪽 ->오른쪽 기준) 내려가는 대각선 이와 같은 방향으로 퀸이 갈 수 있으므로 배열을 사용해 퀸이 갈 수 없는 곳을 체크해 놓는다. 같은 행 같은 행에 하나씩 놓는다고 가정하므로 1번 조건은 확인하지 않는다. 같은 열 used1[]은 열을 체크함으로써 같은 열에 퀸을 놓을 수 없도록 한다. (왼쪽->오른쪽 기준) 올라가는 대각선 위의 그림을 살펴보면 올라가는 대각선이 지나는 칸의 행렬을 더한 값은 항상 같다 0+3 = 1+2 = 2+1 = 3..

1. Backtracking 이란? 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 즉, 백트래킹은 조건이 만족할 때의 모든 조합의 수를 살펴보는 방법입니다. BackTraking에 대한 설명은 예제를 통해 설명하겠습니다. 2. 예제 1) N과 M(1) 문제 입력 : N, M 출력 : 1~N까지 자연수 중에서 중복 없이 M개를 고른 순열들을 출력 생각해야 하는 조건 1~N개의 원소가 반복되면 안 된다. 길이가 M일 경우 해당 순열을 출력한다. BackTracking 코드 void BackTracking(vector v, int arr[]) { if (v.size() == m) { //길이가 M일 경우 for (int i = 0; i < m; i++) {..