-
JUNGOL...138일지 2021. 9. 16. 01:51
N Queen > 문제은행 | JUNGOL : 정보올림피아드&알고리즘
JUNGOL
www.jungol.co.kr
이상의 문제에서 새롭게 파악해야 할 용어가 존재하는데 크게 세 가지를 확인할 필요가 있어 보인다.
- 백트래킹 모든 경우의 수를 전부 파악하기 위한 알고리즘으로 상태 공간을 나타낼 수 있을 때 적합한 방식
- 상태 공간 특정 시스템에서 가능한 모든 구성의 집합
- DFS 깊이 우선 탐색(Depth First Search)의 약자로 트리를 탐색할 때 가장 깊은 노드를 탐색한 뒤 다시 돌아가 루트에서 다음 노드의 탐색을 진행하는 탐색 방식
- N Queen 문제 n 개의 퀸과 n * n 크기의 판이 주어질 때 모든 퀸이 서로를 공격하지 못하는 상태의 수를 구하는 문제
※ 이 문제를 해결하기 위해 상태 공간 트리를 구성할 수 있어야 하고 DFS를 구현할 수 있어야 한다.
- 백트래킹 모든 경우의 수를 전부 파악하기 위한 알고리즘으로 상태 공간을 나타낼 수 있을 때 적합한 방식