Back Tracking 문풀 개념 복습

#재귀로 완전탐색을 사용 하는 문제는 어떤문제인가? ( 백트래킹) 

완전탐색해야하는데

 

입력에따라

내가 선택해야하는 개수나 

조건이 달라질때 어떻게해야하는가

 

10개중 3개 이렇게 개수가 정해져있으면 반복문으로 가능하지만, 

그개수가 안정해져있고 가변적일때의경우..

 

재귀함수 사용하면 쉬워진다!

 

재귀함수를 이용해서 완전탐색을 하는방법: 백트래킹 

 

# 백트래킹의 3가지 요소 

1.종료조건

- 재귀호출은 한다는건 언젠가 멈춘다는건데... 언제멈출지를 정해주는게 중요하다.

 

2.현재상태 (파라미터 정하기) 

- 똑같은 함수가 호출 될건데.. 똑같은 함수가 호출되더라도... 다른 상태임을..표현해야하는데 그걸 파라미터로 표현함.

 

어떤 상태를 표현해야하는지 잘 정의하고

 그거에 맞게 파라미터를 정의해야한다.  

 

3. 재귀호출 조건

깊은 탐색을 진행할텐데.. 다음탐색을 어떻게 이어나갈지.. 재귀호출 조건 

 

이조건에 따라서 다양한 종류의 문제 접근가능