8월 3일 (월)_N-Queens

1. Toy Problem

  8월로 넘어오면서 이제부터는 매일 아침 Toy 문제를 푸는 과제가 생겼다. 위 문제의 경우 처음에는 Delete를 사용하여 중복을 제거하면 되지 않을까? 생각하였지만 그렇게 하면 문제가 더 복잡해질 것 같아 포기하였다. 

  이후 생각한 것은 재귀함수를 이용하면 쉽게 풀 수 있을 것이라 생각하였고 결국 재귀를 사용하여 풀었다. 첫 번째 문자를 두번째 문자부터 비교하여 같지 않은 값들을 결과값에 배열로 넣고 그 배열에서 중복이 있는지 없는지 검사하여 만약 중복이 있다면 또 한번 재귀로 함수를 돌려 최종적으로 중복 값을 다 없앤 배열을 만든 후 그 중 첫번째 값을 리턴하는 함수로 과제를 해결하였다.

2. N-Queens

  알고리즘에 대해 더욱 공부하기 위한 과제로 N-Queens라는 체스 Sprint를 진행하게 되었다. 코드스테이츠에서도 아직 우리가 해결하기 힘든 과제라 힌트도 많이 주고 못풀더라도 좌절하지 말고 알고리즘을 해석하고 구성하는 능력을 기를 수 있는 시간이 되었으면 한다고 전했다. 우선 어려운 과제인만큼 Team을 구성해서 전략적으로 이 알고리즘 문제를 어떻게 하면 풀 수 있을지 하는 시간을 가졌다. 이 시간을 통해 Sprint에서 원하는 요구사항을 정리하고 우리가 해결해야할 문제들의 접근 방법에 대해 공부 할 수 있었다.

1) 깊이 우선 탐색 DFS(Depth-First Search) vs 너비 우선 탐색 BFS(Breadth First Search)

2) 백트래킹(Backtracking)

  백트래킹에서 알아야 할 것은 유먕성에 대해서이다. 백트래킹은 유망하지 않은 자식에 대해서는 탐색을 하지 않는다. 오직 유망성이 있는 자식에 대해서만 깊이 있게 탐색을 진행한다. 백트래킹 자체는 개념이고 우리는 과제를 통해 이 백트래킹을 구현하는 과정도 해야할 것으로 예상하고 있다.

 

출처 : https://thd0011.tistory.com/19

[알고리즘] 백트래킹 (Backtracking) 알고리즘

  위의 개념을 알고 현재 함수들을 작성 중이다. 내일까지 완성하는 과제이지만 아무래도 50%정도 완성하면 잘한 것으로 예상한다. 그렇다고해도 100% 할 수 있도록 노력하는 자세로 끝까지 해보도록 하겠다. 아자!