[C++] 백트래킹

백트래킹이란?

브루트 포스와 같이 완전 탐색을 하는 알고리즘이 있는데, 여기서 조건에 해당되지 않는 경우를 가지치기 하여 경우의 수를 줄여나가는 방법을 백트래킹이라고 한다. 백트래킹을 이용하면 탐색 시간이 줄어든다.

 

백트래킹에서는 주로 재귀함수를 이용한다. 이때, 재귀함수의 종료조건이 중요하다.

백트래킹은 주로 N의 값이 20보다 작을 때 이용한다.

 

백트래킹을 정리하자면

1. 종료 조건을 잘 설정하자

2. 입력 범위가 작을 때 (N<20) 사용하자

3. 재귀함수를 사용하자

3. 원래 상태로 돌려주는 것을 잊지 말자

정도가 된다.

 

 

 

 

 

[C++] 백준 알고리즘 15649 N과 M (1) (백트래킹) (tistory.com)

[C++] 백준 알고리즘 15649 N과 M (1) (백트래킹)