wonseok.log wonseok.log

N-Queen

• [Programmers] Lv2. N-Queen(kotlin)

  SW Test/Programmers 2022. 7. 26. 19:08

  문제 예시 풀이 N-Queen은 백트래킹의 대표적인 문제로 y축을 하나씩 내려가면서 x축을 한번 순회하여 Queen이 놓아질 수 있는 곳을 찾는 문제입니다. 하나씩 탐색하면서 찾아도 되지만 수학적으로 좌표를 활용하여 문제를 풀면 빠르게 풀 수 있습니다. 대각선끼리도 같은 라인에 Queen이 있으면 안되는데 좌표의 기울기나 규칙을 통해서 같은 대각선인지 아닌지 알 수 있습니다. 오른쪽 아래로 향하는 대각선에서 y-x 값이 동일한 좌표는 같은 대각선 상에 존재합니다. 마찬가지로 왼쪽 아래로 향하는 대각선끼리는 y+x 값이 동일합니다. 따라서 y좌표는 하나씩 내려가면서 x좌표만 0부터 n-1까지 순회하여 dlist (down list), rdlist(right down list) , ldlist(left do..

  Read More
• [Programmers] Lv3. N-Queen

  SW Test/Programmers 2020. 9. 7. 03:41

  이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.

  Read More