퇴각검색1 퇴각검색 알고리즘을 이용한 N-Queen 문제 “누워서 읽는 알고리즘” 책에서 소개된 N-Queen problem을 접하게 되었다. 첫 느낌은 어렵지 않을 것 같았으나 생각보다 쉽지 않았던 문제인 것 같다. 문제는 아래와 같다. 가로 세로 모두 N개의 칸이 있는 체스판 위에 N개의 여왕을 올려놓되 서로 공격해서 잡을 수 없도록 놓을 수 있는 방법은 모두 몇 개인가? 예를 들어 4X4라면 아래와 같이 4개의 Queen을 놓을 수 있다. “누워서 읽는 알고리즘” 책에서는 퇴각검색(BackTracking) 알고리즘과 함께 소개하고 있다. 퇴각검색이 무엇인지 먼저 소개하고 넘어가기로 한다. 퇴각검색이란 위키피디아에서는 아래와 같이 정의하고 있다. 퇴각검색(영어: backtracking, 한글: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. 선뜻 이.. 2016. 12. 21. 이전 1 다음