알고리즘문제

queens problem이란? - 체스판에서 대각선, 상하좌우에 말이 없도록 겹치지 않게 놓는 문제를 말한다. - 문제를 해결하기 위해서 '상태공간트리'를 활용해보자. 상태공간트리란? - 위와 같이 해를 찾기 위해 정답을 향해 나아가는 트리를 말한다. - 즉, 해가 존재한다면 그것은 반드시 이 트리의 어느 한 노드에 해당한다. - 따라서 이 트리를 체계적으로 탐색한다면 해를 구할 수 있다!- 하지만 상태공간트리의 모든 노드를 탐색할 필요는 없다. - 다음과 같이 깊이 우선으로 탐색하여 해를 찾는 알고리즘도 있다.- 이번 문제를 해결 할 때엔 "그 노드가 이미 infeasible한지, 즉 non-promising (꽝)인지"를 확인하면 된다. 코드를 구성해보자. 1. 변수 정하기 - 매개변수는 내가 현재..

recursion을 응용하여 "미로찾기" class와 코드를 짜보자. 현재 위치에서 출구까지의 경로가 있기 위한 IDEA 1. 현재 위치가 출구여야 한다. 또는 2. 이웃한 셀들 중 하나에서 현재위치를 지나지 않고 출구까지 간다. 1. Decision Problem 답이 yes or no인 문제로 표현해보자. bool findPath(x, y) { if (x, y) is the exit return true; else for each neighbouring cell(X, Y) of(x, y) do if (X, Y) is on the pathway if findPath(X, Y) return true; return false; } -> 이 코드는 X,Y에서 인접한 x,y로 다시 갈 수 있기 때문에, 무한루..