재귀 함수 Ⅱ

시뮬레이션

얕은 복사와 재귀 함수

알고 있어야 하는 내용

  • C언어 - 포인터, 함수 전달 방식(Call by value, Call by reference)

  • 얕은 복사, 깊은 복사

def A(arr, t):
    if t == 4: return
    arr.append(1)
    A(arr, t+1)
    print(arr)

A([], 0)

위와 같은 코드가 있다고 합시다. 이 코드를 실행할 경우 5줄에 적은 print()함수에 의해 어떤 출력이 나올까요?

[1]
[1, 1]
[1, 1, 1]
[1, 1, 1, 1]

이렇게 순서대로 나온다고 생각하는 사람이 있을 것이고

[1, 1, 1, 1]
[1, 1, 1]
[1, 1]
[1]

재귀 함수는 스택을 이용하는 것이니까 이렇게 역순으로 출력한다고 생각하는 사람이 있을 것입니다.

둘 다 틀렸습니다.

정답은 아래와 같이 모든 배열이 [1, 1, 1, 1]을 출력하게 됩니다.

[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]

C언어 수업에서 함수 인자 전달 방식 2가지에 대해 배웠을 것입니다. Call by value는 값 그대로 복사하여 가져가는 것이고, Call by reference는 메모리 주소 값으로 가져가는 것입니다.

파이썬은 둘 다 사용하는 Call by assignment라는 전달 방식을 사용합니다. 이것은 불변 객체는 Call by value로 인자를 전달하고, 가변 객체는 Call by reference로 인자를 전달하게 됩니다. 불변 객체와 가변 객체는 8주차 얕은 복사, 깊은 복사에서 설명하였습니다.

def A(arr, t = 0):
    if t == 4: return
    arr.append(1)
    A(arr, t+1)
    print(arr)

A([])

파이썬에서는 리스트를 매개 변수로 넣으면 Call by reference로 얕은 복사가 되기 때문에 현재 실행 중인 arr 리스트는 전부 똑같은 메모리 주소 값을 가지게 됩니다. 그래서 모든 arr배열이 1을 추가하게 되는 것입니다.

[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1]

def A(arr, t = 0):
    if t == 4: return
    arr.append(1)
    A(arr, t+1)
    print(id(arr))

위 코드처럼 이렇게 id(arr)을 출력하게 만들면 전부 똑같은 값이 나오는 것을 알 수 있습니다.

그래서 리스트를 인자로 사용하려면 같은 메모리 주소를 참조하지 않도록 문제를 풀어야 합니다.

def A(arr, t = 0):
    if t == 4: return
    A(arr + [1], t+1)
    print(arr)

A([])

첫 번째 방법은 arr + [1]을 해주어서 새로운 객체를 만드는 것입니다.

def A(arr, t = 0):
    if t == 4: return
    arr.append(1)
    A(arr.copy(), t+1)
    arr.pop()
    print(arr)

A([])

두 번째 방법은 copy() 메소드를 사용하는 것입니다. 이 코드에서는 append와 pop을 사용하기 때문에 코드가 조금 길다는 단점이 있습니다. 저는 그래서 보통 첫 번째 방법을 사용하는 편입니다.

연습 문제

BOJ 14650

0, 1, 2 가지고 n의 자리 숫자를 만들어서 3의 배수를 만들 방법의 수를 구하라고 합니다. 0으로 시작하는 숫자는 아니라고 하므로 일단 재귀를 시작할 때 1과 2로 시작하면 되겠습니다.

n = int(input())
ans = 0

재귀 함수는 처음에 우리가 직접 1과 2를 선택하여 실행 시키고, 그 이후에는 for문을 이용하여 숫자를 추가하는 방식을 해주면 될 것 같습니다.

숫자를 추가하는 방법은 [(원래 숫자) * 10 + 추가할 숫자]로 넣으면 될 것 같네요. 그러다가 N의 자리 숫자가 된다면 3으로 나눈 나머지를 확인하여 출력하면 됩니다.

def go(val):
    for x in range(3):
        go(val * 10 + x)

n = int(input())
ans = 0
go(1)
go(2)

이렇게 하면 계속 1의 자리에 값을 넣어줄 수 있습니다. 이것은 리스트로 해도 상관없고, 스택으로 해도 상관없습니다.

이제 N의 자리일 때 멈춰야 하므로 if문을 이용해주고, 숫자가 3의 배수이면 ans에 1을 더해주면 됩니다. go()함수 바깥에 있는 변수에 1을 더해주는 것이므로 global 키워드를 사용해야 합니다. 그리고 N의 자리임을 확인하는 방법은 str형으로 바꾸어서 len()함수를 사용하면 됩니다.

def go(val):
    global ans
    if len(str(val)) == n:
        if val % 3 == 0: ans += 1
        return
    for x in range(3):
        go(val * 10 + x)

n = int(input())
ans = 0
go(1)
go(2)
print(ans)

참고로 이 문제는 Large 버전 문제도 있는데, 이건 재귀 함수로 풀지 못합니다.

백트래킹 알고리즘(Backtracking)

퇴각 검색 기법이라고도 부르는 알고리즘입니다. 모든 경우의 수를 구하는 완전 탐색 알고리즘과 비슷한 알고리즘입니다. 살짝 다른 점은 가지치기(purning)를 통하여 조건에 위배되는 경우의 수는 바로 버리고, 뒤로 되돌아가서 다시 다른 방법을 찾아보는 알고리즘입니다.

백트래킹 알고리즘, 가지치기라고 해서 뭔가 새로 배워야 하는 알고리즘처럼 보이긴 하는데 사실 우리가 그동안 풀었던 재귀 함수 문제들 전부가 백트래킹 알고리즘입니다.

우리가 문제 조건에 맞는 경우의 수만 확인하게 코드를 짠 것 자체가 가지치기에 해당하며, 뒤로 되돌아가는 것은 재귀 함수 코드 자체가 해당 재귀 함수가 끝나게 되면 이전 재귀 함수로 돌아가게 됩니다. 이것이 마치 뒤로 되돌아가는 것처럼 보이는 것이죠.

백트래킹 문제로 제일 유명한 문제는 N-Queen이라는 문제입니다. N x N 체스판에서 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 모든 경우의 수를 구하는 문제입니다.

풀어볼 문제

Previous추가 문제Next그래프 알고리즘 소개

Last updated