코테/특강
Back Tracking 문풀 개념 복습
포포252
2023. 7. 30. 18:28
#재귀로 완전탐색을 사용 하는 문제는 어떤문제인가? ( 백트래킹)
완전탐색해야하는데
입력에따라
내가 선택해야하는 개수나
조건이 달라질때 어떻게해야하는가
10개중 3개 이렇게 개수가 정해져있으면 반복문으로 가능하지만,
그개수가 안정해져있고 가변적일때의경우..
재귀함수 사용하면 쉬워진다!
재귀함수를 이용해서 완전탐색을 하는방법: 백트래킹
# 백트래킹의 3가지 요소
1.종료조건
- 재귀호출은 한다는건 언젠가 멈춘다는건데... 언제멈출지를 정해주는게 중요하다.
2.현재상태 (파라미터 정하기)
- 똑같은 함수가 호출 될건데.. 똑같은 함수가 호출되더라도... 다른 상태임을..표현해야하는데 그걸 파라미터로 표현함.
어떤 상태를 표현해야하는지 잘 정의하고
그거에 맞게 파라미터를 정의해야한다.
3. 재귀호출 조건
깊은 탐색을 진행할텐데.. 다음탐색을 어떻게 이어나갈지.. 재귀호출 조건
이조건에 따라서 다양한 종류의 문제 접근가능