nqueen
NQueen 문제 파이썬과 자바스크립트 풀이
백준 9663번 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ✏️ 구상 N*N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치해야한다. 퀸의 움직임은 직선방향, 대각선방향이다. 그렇다면 생각나는 기본적인 로직은 우리는 퀸을 한줄에 하나씩만 배치할 수 있다는 것이다. 우선 배치한다고 생각해보고 하나씩 손으로 배치를 해보자. 두 번째 줄에선는 1,2번째 칸에 퀸을 배치할 수 없다. 두번째 줄에도 배치했으니 이제 세번째로 넘어간다. 세번째줄에 배치가 불가능하다. 따라서 다시 두번째 줄로 돌아가 4번째 칸에 배치한다. (3번..
백트랙킹 기법 정리
백트랙킹(backtracking)이 무엇인가? 뭐 탐색을 하면서 그냥 필요없는 경로는 손절치고 가지치기하는 알고리즘이다. DFS랑 유사하다 이정도로 대충 알고있었다. 따라서 이번에 공부하면서 정리해보려한다. ✏️ Backtracking 정의는 이렇다. '해를 찾는 도중에 해가 아니어서 막히면 다시 되돌아가서 다시 해를 찾는 기법.' 이걸 가지치기(pruning)이라고 하는데 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. 구현방식? DFS등으로 모든 경우의수를 탐색하는 과정에서 조건문등으로 답이 절대 될 수 없는 상황을 정의하고 그런 상황에서는 탐색을 중지시키고 다시 처음으로 가서 다른 경우를 탐색하게끔 구현할 수 있다. 트리에 대해서 DFS 실시 각 노드가 유망한지(promising) 점검 해당 ..