[Algorithm] 백트래킹 학습

백트래킹이랑?

• 완전탐색 + 가지치기

• 모든 경우를 트리 형태로 탐색

• “답이 될 수 없는 가지”를 중간에 잘라냄

• DP처럼 저장해서 줄이는 것이 아닌 중간부터 내려가지 않는 것이 핵심

백트래킹 유형 파악 방법

1. 선택지

2. 제약 조건

3. 종료 조건

위 3개가 안보이면 다른 유형인지 생각해볼 것.

백트래킹 기본 구조 (암기 대상)

def backtack(depth):
	if 종료조건:
    	처리
        return

    for 선택 in 선택지:
    	if 제약조건 위반:
        	continue

        선택 적용
        backtrack(depth + 1)
        선택 되돌리기

위의 구조를 암기 후 변형시켜서 다른 기출 문제 해결할 것