4 - 재귀용법, 백트래킹

재귀용법 (recursive call)

재귀함수는 함수 내에서 자기 자신을 불러내는 것을 의미한다.

재귀를 이용하는 대표적인 예시로 피보나치 수열이 있다.
간단한 경우부터 생각해 보자.

2! = 2 * 1
3! = 3 * 2 * 1 
4! = 4 * 3 * 2 * 1 
5! = 5 * 4 * 3 * 2 * 1

이다.
이를 조금 변형해 보면

2! = 2 * 1
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!

으로 표현할 수 있다.
즉, 함수(n)dms return n * 함수(n - 1) 로 표현할 수 있다.(n > 1)
이를 파이썬으로 표현해 보자.

def factorial(n):
  if n > 1:
    return n * factorial(n - 1)
  return n

재귀호출의 일반적인 형태를 분석해 보면

def solution(입력):
 if 입력 > 일정값:
   return solution(입력 - 1) # 입력보다 작은 값
 return 일정값 or 특정값 # 재귀호출 종료

의 모습을 가지는 것을 알 수 있다.
이는 스택의 모습과 굉장히 비슷한 모양을 띤다.

참고적으로 파이썬에서는 재귀함수를 사용했을 시 효율이 좋지 않아
깊이가 1000 이하일 경우에만 사용한다.

백트래킹 (backtracking)

백트래킹은 기본적으로 모든 경우의 수를 탐색하는 알고리즘이다.
조건을 점진적으로 체크하다가 제약 조건을 만족하지 못한다고 판단되면, backtrack (다시는 해당 후보군을 고려하지 않음) 하여 다음 후보군으로 넘어가는 방법을 채택한다.

즉, 백트래킹은 조건문을 통해 가지치기를 얼마나 잘 하였는가 에 따라 효율이 결정된다.

실제 구현 시, 모든 경우의 수(후보군)를 상태 공간 트리를 통해서 표현하며 DFS 방식으로 확인한다.

- Promising : 해당 루트가 조건에 맞는지를 검사하는 기법
- Prunig (가지치기) : 조건에 맞지 않으면 더이상 탐색하지 않고 다른 루트로 이동한다.
  탐색의 시간을 줄여주는 주요 기법이다.

정리하면 백트래킹은 트리 구조를 기반으로 DFS 방식으로 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(promising), 해당 트리에서 조건을 만족하지 않는 노드는 더 이상 탐색을 진행하지 않고 가지치기(pruning) 한다.

N Queen

N Queen 은 대표적인 백트래킹 문제이다.

- n * n 의 체스판 위에 n 개의 퀸을 서로 공격할 수 없도록 배치하는 문제.
- 한 행에 하나의 퀸만 존재할 수 있다.

문제를 정리해 보면

• 상위 행부터 퀸을 배치한 후, 다음 행에 해당 퀸이 이동할 수 없는 위치를 찾아 퀸을 배치한다.
• 앞선 행에 배치한 퀸으로 인해, 다음 행에 해당 퀸이 이동할 수 없는 위치가 없을 경우에는 백트랙하여 다음 퀸의 위치로 이동한다.
  ➡️ 맨 위의 행부터 퀸의 배치가 가능한 경우를 상태 공간 트리 형태로 만들고 DFS 방식으로 접근.
• promising 으로는 수직 체크, 대각선 체크 가 필요하다.

  

출처
잔재미코딩, https://www.fun-coding.org/Chapter21-backtracking-live.html