본문 바로가기

Dev/coding

백트래킹

백트래킹

N-Queen 문제 ==CSP(Constrain satisfaction problems)문제

Backtracking CSP를 해결 하는 방법론! 개념!

왜냐하면 조건이 만족하는 경우라는 조건이 있기 때문이다.

응용 사례:

조합의 숫자를 셀 때, 어떠한 조건들을 가지고 있다면, 모든 조합이 아닌 특정조건에 한정해서 조합을 카운트 할 수 있다. 검색 성능은 향상된다.

트리상황을 예를 들면, DFS BFS 할때마다 invalid()해서 원하는걸 체크하는데 이게 은근히(매우) 중요하다는 것

일반적으로 백트래킹 구현 방법은 DFS,BFS 가 있다.

DFS(깊이 우선탐색)을 통하여 구현하는데 BFS(넓이 우선탐색)의 경우 상대적으로 많은 메모리가 필요하기 때문이다. 다 가지고 있어야하니깐 시작부터..

'Dev > coding' 카테고리의 다른 글

그리디  (0) 2019.09.04
백트래킹  (0) 2019.09.04
동적계획법  (0) 2019.09.04
[python] python searching string within list  (0) 2019.08.24
[python] **dictionary  (0) 2019.08.24
[python] string format  (0) 2019.08.24