[Section 4] 백트래킹(Backtracking)이란? _ 이항 계수 예제

파이썬 목차 보기

[Intro] 파이썬 미리보기

0. INTRO

재귀 함수의 일종으로 백트래킹(Backtracking)이란 용어가 존재한다. 이전에 배운 재귀 함수의 개념은 함수를 재호 출하여 반복적으로 문제를 해결하는 방식이었다. 만약 백트래킹 또한 재귀 함수라면, 도대체 무엇이 다른 것인가? 백트래킹에 대해 자세히 알아보자.

1. 백트래킹(Backtracking)의 개념 _ 조건이 달린 재귀 함수

재귀 함수는 자기 자신을 참조하는 개념의 함수이다. 재귀 함수에 어떤 값을 넣는다면, 스택 오버플로우가 발생하지 않는 선에서 함수는 자기 자신을 계속해서 참조한다. 그리고  종료 조건에 도달한다면, 함수는 차례대로 값을 반환하기 시작한다. 다음의 그림을 참고하자.

 

재귀함수의 동작 개요

 

만약 종료 조건만이 아니라, 입력되는 데이터에 조건을 달면 어떻게 될까? 조건에 따라 출력 결과가 달라질 것이다. 이렇게 입력되는 데이터에 조건을 다는 기법을 백트래킹이라고 한다. 이 백트래킹 기법은 가능한 모든 경우의 수를 고려해야 하는 알고리즘에 적합하며, 다양한 응용문제에 사용된다. 여기에서는 수학적 연산을 프로그래밍하는 예제에 백트래킹을 적용해보고자 한다. 

2.  백트래킹 예제 _ 이항 계수 공식과 파스칼 삼각형의 관계 이해하기

다음과 같은 그림의 파스칼의 삼각형에 대해 접해본 적이 있는가? 그렇다면 이항 계수(Binomial coefficient)가 무엇인지 이해하기 쉬울 것이다. 왜냐하면 파스칼의 삼각형에서 나타나는 수 규칙이 이항 계수의 표와 동일하기 때문이다.

 

파스칼의 삼각형

 

이항 계수는

 

이항 계수 공식

 

여기에서 n은 자연수, k는 정수를 의미한다.  조건에 따라 k와 n은 0보다 커야 한다. 얼핏 보기에 왜 이게 이항 계수가 되는지 이해하기 힘들 수 있는데, 다음의 그림을 참고하면, 이해하기 쉽다.

 

파스칼의 삼각형과 이항계수 공식의 관계

3.  백트래킹 기법 응용 _ 이항 계수를 구하는 함수

이항 계수 공식을 파이썬 함수로 만들기 위해서 변수가 두 개 필요하다. 그리고 변수는 n과 k라고 명명하자. 이항 계수 표를 보면, n 변수는 파스칼 삼각형의 층 번호를 의미한다. 따라서 함수에는 따로 계수는 몇 층에 존재한다는 것을 print() 함수를 이용하여 나타내기로 하자.

 

다음의 예시 코드를 참고하자.

 

예시 코드:

 

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

def Pascal(n,k):
    if n < k or k>n:
        Ans=0
    if 0 <= k <=n:
        print("Floor is ",n,"level!")
        print("And it is on",k+1,"th coefficient!!")
        numerator = factorial(n)
        denominator= factorial(k)*factorial(n-k)
        Ans=int(numerator/denominator)
    return Ans

n=3
k=0
Pascal(n,k)

n=3
k=1
Pascal(n,k)

n=3
k=2
Pascal(n,k)

n=3
k=3
Pascal(n,k)

 

* 맞는지 확인해보기 위해 파스칼 삼각형의 3번째 층의 결과를 확인해보았다. 코드 결과는 다음과 같다.

 

이항 계수 파이썬으로 구현

 

3층의 결과는 1 3 3 1 이 맞다!!!