해나의 컴공생존기

1. 문제정의 위 모양의 퍼즐을 1234 순서대로 만드는것이다. 빈칸의 상하좌우 숫자들은 빈칸과 자리를 바꿀 수 있다. 2. State Space 상태공간이란, 문제가 처할 수 있는 모든 상태를 모아놓은 것이다. 모든 상태가 다 solve가능한 상태일까? 아니다. 퍼즐 두개를 뽑아서 자리를 바꾸면 풀수 없는 상태가된다. 하지만 또 두개를 뽑아서 자리를 바꾸면 풀 수 있는 상태가 된다. state가 될 수 있는 모든 경우의수를 생각해보면 16!이다. 매우 큰 숫자이다..! 이 퍼즐에는 Invariant가 있다. Permutation과 빈칸과 코너의 거리를 더한 값이 유지된다는 것이다. 먼저 빈칸을 16으로 생각하고 배열을 만든다. 각 숫자에 자신보다 오른쪽 중 자신보다 작은수의 개수를 적는다(Permuta..

1. 문제 정의 N x N 크기의 체스판이 있을 때 N개의 퀸을 서로가 공격할 수 없도록 올려놓는 경우의 수를 구하는 문제이다. 2. idea N이 4일 때를 기준으로 생각해 보겠다. 2.1 다해본다 16C4 * 16 2.2 겹치는 경우는 뺀다. 한 열에 하나 씩 배치 4^4 2.3 cut off (1,1) 에 퀸을 배치하고 그 퀸이 갈 수 있는데를 다 표시한다. 표시되지 않은 칸들 중 하나에 퀸을 배치하고 또 그 퀸이 갈 수 있는데를 다 표시한다. 이런식으로 (1,1) 부터 (1,n)까지 시도해본다. 사실 오른쪽과 왼쪽은 대칭이기 때문에 왼쪽 반만하고 곱하기 2를 해줘도된다.