카테고리 없음
[코딩테스트 합격자 되기 스터디] 7주차 - 백트래킹
매지깅
2024. 8. 25. 18:48
✅ 백트래킹의 개념
- 가장 최근에 방문했던 노드로 다시 돌아감 (ex. DFS)
- 완전 탐색하지 말고, 내가 찾는 답일 가능성이 있는 경우에만 탐색한다.
✔️ 백트래킹 알고리즘의 핵심은 "해가 될 가능성을 판단하는 것" 이며, 그 가능성은 "유망 함수" 를 정의하여 판단한다.
✅ 백트래킹을 푸는 과정
- 상태 정의 : 문제의 각 단계에서 가능한 상태를 정의
- 유망 함수(isPromising) : 현재 상태가 유망한지 판단, 유망하지 않으면 더 이상 탐색하지 않음
- 해결책 확인(isSolution) : 현재 상태가 문제의 해결책인지 판단
- 재귀 호출 : 유망한 상태로 이동하면서 문제 해결
✅ 백트래킹 예시 - 부분합
✔️ 문제 : {1,2,3,4} 로 이루어진 집합에서 숫자를 뽑아서 합이 5인 조합 구하기
- 완전탐색으로 풀기 - 각 집합은 뽑거나 뽑지 않을 수 있으므로 아래와 같다
- 시간복잡도 O(2^n)
- 모든 경우의 수 탐색 - 총 16번
- 백트래킹으로 풀기
- 상태 정의 : 현재까지 선택한 숫자들의 합
- 유망 함수 : 현재 부분 합이 목표 값을 초과하면 유망하지 않다고 판단
- 해결책 확인 : 현재 부분 합이 목표 값과 일치하는 지 확인
- 재귀 호출 : 다음 숫자를 선택하여 부분합 갱신
유망 함수 설계
✔️ 현재 조합으로 합이 5가 되면 더 이상 탐색할 필요가 없음 (isSolution == true)
✔️ 해당 숫자를 조합하여 합이 K 이상이 되면 탐색할 필요가 없음 (isPromising == false)