백트래킹이란?백트래킹은 가능한 모든 경우의 수를 따라 들어가면서 탐색하는 알고리즘이다.답이 될 수 없는 경우 더 이상 탐색하지 않고 뒤로 돌아간다.주로 재귀 함수를 사용해 구현한다.시간 복잡도는 O(N!)으로 매우 큰 편이다. 그렇기 때문에 백트래킹 관련 문제에서는 N이 작게 주어진다. 백트래킹 구현에서 가장 중요한 점은 방문 상태 변화 & 상태 원상 복구 두 가지다. 로직을 작성할 때 항상 염두에 두자.백트래킹과 순열, 조합순열과 조합을 구할 때, 가능한 모든 경우의 수에 대해 검사하기 때문에 백트래킹을 사용할 수 있다.아래에서 설명하는 순열과 조합은 오름차순으로 정렬된 집합을 기준으로 한다. 아래 코드에서 공통적으로 나오는 변수들은 다음을 나타낸다.isUsed[i]: i번째 수가 사용되었는 지 여부를..

문제https://www.acmicpc.net/problem/9663 해당 문제에 대한 풀이는 다음 블로그 글을 참고함https://blog.encrypted.gg/945 [실전 알고리즘] 0x0C강 - 백트래킹이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는blog.encrypted.gg 백트래킹과 브루트 포스를 이용하는 문제다.코드// 위아래, 대각선에 대해 isUsed 배열 3개를 사용// isUsed_vertical: 같은 열에 퀸이 있는지 여부// isUsed_leftDown_rightUp: 왼쪽 아래-오른쪽 위 대각선 상에 퀸이 있는지 여부// isUsed_leftU..