고인물을 지양하는 블로그

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 올 2월 겨울방학 스터디 때 교수님이 backtracking 소개를 해주시며 처음 접하게 된 문제로, 가장 기본적인 backtracking 문제이다. brute force를 이용한 문제 해결의 시간 복잡도를 알아보면, 해당 위치에 퀸을 놓을 수 있는지 확인하는 possible 함수가 //(O(N^N)//) 번 호출되는데, 그 때마다 //(O(N)//) (혹은 //(O(N)//)) 시간을 들여 그 자리에 놓을 수 ..