여왕말 문제라고... 체스판에 여왕(queen)을 서로 잡아먹히지 않도록 놓는 문제인데요.
우선 여왕은 가로 혹은 세로, 대각선으로 원하는 만큼 갈 수 있습니다. 따라서 여왕벌이 1행에 1열에 놓인다고 가정하면, 1행, 1열, 혹은 1행 1열의 대각선에 해당하는(ex) 2행 2열, 3행 3열) 곳에는 여왕을 놓을 수가 없는 것이죠.
근데 우선 조건은 여왕말과 같은 행에 놓이면 안된다는 조건 1개만 가지고서 볼 때요...
체스판 크기가 n X n이라고하면, 여왕벌을 1행의 아무곳에나 놓으면 그 다음에는 여왕말이 2행의 아무곳에 올 수 있잖아요.
이렇게 볼 때에 이걸 트리형태로 가정하면 루트에는 아무것도 없고(level 0), 레벨 1에는 n개의 가능한 여왕말의 위치가 있고, 각각의 레벨 1의 노드마다 n개의 자식 노드가 있는 것이 아닌가요???(즉 1행에 각각의 여왕말의 위치마다 2행에 가능한 여왕말의 위치가 n개가 있는 것 아닌가요?? 각 행에는 n개의 위치가 있으니까??)
근데 책에는 n^2의 자식 마디가 있다고 나와있는데 책이 잘못된 것인지요???
자식이 n개인 노드가 n개 있으니까 n^2라는거 아닌가
이 상태공간 트리에서 모든 마디는 장기판의 각 위치당 하나씩 n^2의 자식마디를 가지고 있다 라고 되어있는데요. 각 위치당 n개니까 틀린 것 같은데... 그리고 잎노드가 (n^2)^n개라고 되어있거든요 n^n개 아닌가요??? 총???
왜 첫줄에만 둔다고 생각하는거임?
저 책은 체스판 전체를 말하는거임
완전 백트래킹
그럼 임의의 자리에 여왕말을 놓고, 또 임의의 자리에 여왕말을 또 놓을 수 있는거임?? 같은 위치라도...???
같은 행, 열, 대각선 상관없이 둘 수 있는거임??? 같은 위치라도...???
그니까 자식 노드라는게 i번째 행에 놓았을 때 그 각각의 위치에 대해 i+1번째 행에서 가능한 여왕말의 위치(열)이잖아요. 여기서 열의 갯수가 n개니까 자식 노드가 n개 인것 같은데... 조건이 같은 행에 둘 수 없다는 조건이 있는거 아닌가요??? 처음에는 그렇게 설명되어있던데 다시 다른것인지...??
물론 첫줄에 안두더라도 n^2은 안되는게 예를 들어 처음에 n^2개의 체스 위치에서 선택한다고 해도 두 번째에서는 같은 행에서 둘 수 없다면 n X (n-1)개가 되는거 아닌가요??? 그리고 최소한 같은 위치에 둘 수 없다고 하면 n^2 -1개가 되는데...
게다가 여기서는 첫줄에 하나두고 두번째 줄에 하나두고 이런식으로 둬가는 것 같은데 그렇게 생각하면 n개가 맞는 것 같은데...
log(n!)은 nlogn으로 근사됨요. 따라서 O(n!)은 O(n^n)으로 근사가능
내가 예전에 log(n!) 효율가지고 지랄했다가 수학포럼에서 부등식으로 저명한 놈이 증명해줌요. log(n^n)>log(n!)>a*log(n^n)-b
a,랑 b가 뭔진 기억 안남
근데 그럼 체스판에 임의의 위치에 말을 하나 놓고 그 다음에 다른 위치에 또 둬야 되는데 같은위치에 두게되면 말이 안되잖아요...???
시간복잡도는 안나와있고요... 저 위에 임의의 노드에 대해서 자식노드의 갯수가 n^2이라는 말이 맞는지 아닌지만 알면되요.ㅜㅜ
제 생각엔 틀린 것 같은데요.ㅜㅜ
아, 내 정신 좀 보게. 에이시아//를 쓴다는게 이름에다가 치고 글 썼네
자식노드 갯수를 n^2으로 두고 풀수\"도\" 있음요.
니 말처럼 그냥 n으로 풀어도되고
그냥 풀이의 차이랑꼐
흠 그런가요.ㅜㅜ 답변 감사합니당~.
어떤 책은 체스판 칸 수 자체를 n으로 두기도함
체스판 칸 전체수는 n^2이고, 체스판 한 행이나 한 열의 수가 n인데... 그럼 n^2이 맞는건가요??
근데 같은 행에 둘 수 없거나 최소한 같은 자리에는 둘 수 없지 않나요..??? 체스 여왕말을 두고 또 그자리에 여왕말을 둔다는게 말이 안되잖아요
depth = 1에서 n개의 포지션
근데 자식노드라는 말 자체의 정의가 손자노드는 포함안되고 직속 자식만 포함되는거 맞죠??
그리고 자식노드가 n^2개일 때 잎 노드가 n^2^n이니까 직속 자식은 맞는 말 같은데요...
그 다음 행에 해당하는 depth = 2에서 n개의 포지션. 그래서 depth2까지 봤을때 가능한 모든 조합 n^n = n^2 라는 말인거 같은데 책에선?
차일드는 그래프에서 adjacent한거만 가능ㅇㅇ
각 위치당 n^2의 자식노드를 가지고있고 잎노드(레벨 n노드)가 n^2^n개라는데요...
책에서는 그냥 자식노드가 n^2이라는말밖엔 없네용.ㅜㅜ
각 위치당 n^2이면 잎노드 갯수는 n^2^n이 맞음. 근데 그럼 그리드가 n*n이 아니던가 혹은 매번 새로운 빈 체스판에 놓는다는 예긴데?
프로그래밍이란게 원래 그럼. 말도 안되는 현실적으로 결과값이 나오기도하고, 거기서 다시 필터링을 하지
예 근데 nXn인 체스판인것은 맞고요... 매번 새로운 체스판에 둘리가 없는게 같은 체스판에 여왕말이 서로 먹히지 않도록 하는 되추적(백트레킹)문제라서요 ...
책 앞부분에 보니까 이런 말도 있네요. 다른 방법으로 n^2 장기판 위치에 각각 모든 여왕말을 두어보는 상태공간 트리를 만들 수 있다. 이 경우에 자식 노드가 n^2이라는 말이니까 아마도 같은 위치라도 둘 수 있다는 말인듯요...?\"??
그거 같은 체스판이면 100% 책이 잘못나온거임.. 아무리 생각해도 그렇게 나올수가 없다. 에초에 n=4 이면, 차일드 갯수가 1 - 4 - 2,1,1,2 - 0,1,1,1,1,0 - 0,0,1,1,0,0 임 절대 n^2가 안나옴.
에이시아 // 그말이 매번 새로운 빈 체스판에 놓는다는 소리네. ㅡ ㅡ
매번 새로운 체스판에 놓는다는 말이 아니고 이런 말임 원래 우리 알고리즘은 한 줄에 하나씩 놓는 알고리즘인데, 다른 방법(그러니까 이런 다른 알고리즘도 있다.)도 있다는 말이죠. 새로운 체스판에 놓으면 안되죠. 그러면 문제자체가 풀리질 않죠. 문제가 여왕말을 잡아먹히지않게 하는건데요. 물론 책에도 나와있지만 이런식으로 모든 경우의수를 다 고려하는 것은 효과적이질 못하다고 나와잇네요.
백트레킹하는 횟수가 더 많아지고 검사해야되는 노드 갯수가 많아지겠지요.
아 그런.. 그냥 필자가 지나가다가 던진 말을 이렇게나 ㅜ ㅜ.. 음.. n퀸스 나도 대학교 2학년때 풀었던 기억이 난다..