백트래킹이란?

재귀이긴 한데, 완전탐색 등에서 한번 갔던 길을 다시 되돌아와서 다른 길을 탐색해나가는 식의 방법을 이야기한다. 그렇기에 상태를 업데이트 하면서 재귀를 돌리되, 재귀가 끝이 나면 다시 원래대로 돌리는 내용이 필요하다. 이렇게 말이다.

def func(a):
	for i in range(n):
    	answer.append(i)#상태를 저장하는 모습
        func(a+i)
        answer.pop() 	#원래대로 돌리는 모습

재귀함수에서 중요한 요소들

재귀함수를 작성하는데 있어서 강사님은 중요한 요소가 3개 있다고 하셨다. 내가 생각하던 것과 다르기도 하고, 주석을 어떻게 쓰는 것이 좋은지에 대해서도 잘 설명해 주셔서 여기에 기록으로 남겨본다.

재귀 함수에서 중요한 세가지 요소

1. 현재 상태를 나타내는 파라미터

파라미터는 한개일 수도 있고, 여러개일 수도 있다. 이건 그냥 문제에서 고려해야 하는 요소들이 많으면 많을수록 파라미터가 늘어난다고 생각하면 좋다. 또한, 파라미터를 기준으로 이전까지는 어떠한 일이 전제되어있고, 이 파라미터를 받은 후 어떤 일을 하는지에 대해서 자세히 묘사할 수 있어야 한다.

def func(idx):
	"""
    0~idx-1: 중복되지 않는 랜덤한 숫자들을 채움
    idx~n: idx-1 까지 사용한 숫자들 중에 없는 숫자들로 채움
    -----
    idx = 현재 채워야 하는 수의 위치
    """
    ...

이런 식으로 작성하면 된다.

2. 종료 조건

이건 뭐 당연하니까 패스...
나나 강사님이나 제일 앞에 종료 조건을 단다는 것만 알게 되었다.

3. 재귀 호출

재귀 함수니까 당연하게도 재귀 호출을 해야 한다.

문제 풀기