패스트캠퍼스 챌린지 24일차

---

Part 2. 알고리즘 이론

Ch 21. 백 트래킹

02. 백 트랙킹 알고리즘 이해 (2)

---

백 트래킹(backtracking): 크루스칼 알고리즘이나 프림 알고리즘처럼 특정 문제를 풀기 위한 특정 알고리즘이 아니라 일반적으로 문제를 푸기 위한 전략 중 하나. 제약조건 문제에서 해를 찾기 위한 전략. 모든 경우의 수를 상태 공간 트리(State Space Tree)로 표현하고 각 후보군을 깊이 우선 방식(DFS)으로 확인

 

 

백 트래킹을 코드로 구현하는 NQueen 클래스는 상태 공간 트리를 깊이 우선 방식으로 탐색하는 dfsFunc메소드와 계속 다른 후보군을 탐색해야 하는지 판단하는 isAvailable 메소드, 총 두 개의 메소드로 구성되어 있다. dfsFunc 메소드는 재귀를 이용하여 다음 행에서 최적의 해를 찾는다. isAvailable 메소드에서는 현재의 행과 열을 비교하여 탐색 여부에 대해 반환한다.

 

오늘 강의를 끝으로 알고리즘에 대해 배우는 파트가 끝났다. 얼레벌레 듣다보니 벌써 이론 부분이 끝났다는 게 신기하다. 강의 내용이 온전히 내 머릿속에 남아있지 않은 것 같아 수많은 회차의 복습이 필요할 것 같다. 하지만 강의 교안에 남겨주신 내용에 감동하였다. 강의 내용을 그대로 옮기지 말라고 하셨지만 이정도는 되지 않을까 싶어서 올려본다. `여기까지 들어주신 분들은 어려운 과정을 극복하실 만큼의 의지가 있으시므로, 결국 코딩 테스트를 정복하실 것입니다.` 요즘 강의를 들으면서, 그리고 IT계열을 꿈꾸는 사람들의 오픈 카톡방에 참여 중에 내가 부족하다는 생각을 많이 했다. 이 실력으로 코딩테스트를 보는 곳, 자체 서비스를 하는 곳을 도전하는 게 무리가 아닐까? 뭐 이런 생각을 자주 했다. 하지만 강의 끝에 나의 의지를 칭찬해주는 한 마디에 감동하였다. 감사한 마음과 자신감을 한가득 품고간다.

 

 

 

---

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

 

- 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.-