2020.05.13 수요일

오늘 한 일

• 오늘은 nQueens알고리즘에 대해서 풀기 시작했다
  • 이미 어느 정도 코드가 짜여있는 상태라 생각보다 어렵지 않았다.  
  • for문의 작동 범위를 주대각, 반대 각선 비교에서 중요하다는 사실을 알게 되었다. 
  • 숫자끼리의 연산에서 undefined가 있는 경우에는 NaN이 나와서 에러를 찾는데 애먹었다.
  • 백 트레킹에 대해서 알게 되었다. 
    • 깊이 우선 탐색의 경우 필요 없는 부분이 말단 노드가 아닌, 중간 노드에서 발견되는 경우 그 노드의 자식도 필요 없는 경우이다. 
    • 위 경우에서 필요 없다고 판단되는 노드의 자식 노드까지 탐색하는 것은 낭비이기 때문에 가지치기를 한다(해당 노드가 필요 없다고 판단되는 경우( 조건에 부합하지 않는 경우) 해당 노드의 부모 노드로 돌아가 계속한다 (가지치기)
  • DFS와 BFS에 대해서 좀 더 자세히 알게 되었다. 
    • DFS 깊이 우선, Stack 사용
    • BFS 너비 우선, Queue 사용