컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 알고리즘 대표적인 백트래킹 문제 아래의 링크에 푸는 방법이 있습니다. https://kimmessi.tistory.com/86?category=871925 [알고리즘] 백트래킹 - n-Queens, 해밀턴회로 되추적 (Back Tracking) 틀린 답에 접근했을 때, 틀리기 전의 상태로 돌아가서 다른 선택을 하는 알고리즘 만약 답이 나올 때까지가 시간 복잡도가 엄청 복잡하게 나올 수도 있지만, 이 답..

분기한정법이란? 분기한정 설계전략은 상태공간트리를 사용해 문제를 푼다는 사실이 되추적과 매우 비슷하다. 차이점으로 분기한정법은 (1) 트리 횡단방법에 구애받지 않고, (2) 최적화 문제를 푸는데만 쓰인다. 분기한정 알고리즘은 어떤 마디가 유망한지를 결정하기 위해서 그 마디에서 수(한계값)를 계산한다. 이 수는 그 마디 아래로 확장해 구할 수 있는 해답의 한계(bound)를 나타낸다. 그 한계값이 그때까지 찾은 최고 해답값보다 더 좋지 않으면 그 마디는 유망하지 않다. 최적값은 문제에 따라서 최대값이 될 수도 있고, 최소값이 될 수도 있으므로 여기서 "좋다"란 문제에 따라서 더 작다는 의미도 되고 더 크다는 의미도 된다. https://kimmessi.tistory.com/74?category=871925..

되추적 (Back Tracking) 틀린 답에 접근했을 때, 틀리기 전의 상태로 돌아가서 다른 선택을 하는 알고리즘 만약 답이 나올 때까지가 시간 복잡도가 엄청 복잡하게 나올 수도 있지만, 이 답이 유망했는지 아닌지를 판별하면서 불필요한 노력을 절감할 수 있다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. 깊이 우선 탐색 (depth - first search) 부모 마디 우선(preorder) 트리 검색은 트리의 깊이 우선 검색이다. 이는 뿌리마디(root)를 먼저 방문한 후, 그 뿌리마디(node)의 후손들을 모두 방문한다. 예시로는 왼쪽에서 오른쪽의 순서로 마디의 자식을 방문한다. 다음은 깊이우선검색을 하는 간단한 재귀 알고리즘을 쓰는 프로시저이다. void depth_first_tree_se..