by
Oct 04. 2020
Python 재귀함수, 피보나치수열
백트래킹, 피보나치수열
코딩테스트 단골 출제 문제 몇 가지를 풀어보려고 한다.
우선 재귀호출, 깊이우선탐색(DFS)를 통해 모든 경우의 수를 다 찾아야 하는 문제를 풀어보자.
시작하기에 앞서 잠시 파일 입출력에 대해 설명하겠다. open 함수의 인자로 파일경로를 주면 파일 객체를 반환한다. 두번째 인자로 무엇을 할지(r: 읽기전용, w: 쓰기. a:이어서 쓰기)를 지정해주면 데이터를 읽다가 써버리는 불상사를 예방할 수 있다.
백준이라는 코딩테스트를 공부하는 사이트에서 1182번 문제를 함께 풀어보자
https://www.acmicpc.net/problem/1182
문제는 다음과 같다.
숫자 N개 중 몇 개를 뽑아 합이 S가 되는 조합의 개수를 찾아라
예를 들어 다음과 같이 문제가 주어진다면?
N = 6
S = 0
제공된 N(6)개의 숫자: -7 -3 -2 5 8 2
합이 S(0)이 되는 숫자의 조합은?
(-7, -3, 8, 2), (-3, -2, 5), (-2, 2), (-7, 5, 2)
이렇게 4가지가 존재한다.
우선 값을 입력받는 방법을 알아보자. 여러 방법이 있지만 내 컴퓨터에서 해결하기 쉬운 방법은 다음과 같다.
백준에 제출할 때는 f = sys.stdin 주석을 풀고 f = open('data.txt', 'r')에 주석 처리하면 된다.
여기에서 map을 사용한 이유는 readline이라는 함수가 데이터를 읽으면 문자로 읽기 때문에 읽은 값을 다시 숫자로 변경시켜주기 위함이다.
이 문제를 해결하는 방법은 간단하다. 입력받은 숫자들을 하나씩 탐색해보는 것이다.
(-7)을 확인
(-7 + -3), (-3) 을 확인
이제 위의 [ (-7), (-7 + -3), (-3) ]에 -2를 더 추가해서 확인해본다.
[ (-7 + -2), (-7 + -3 + -2), (-3 + -2), (-2)] 을 확인
...
이런 식으로 앞에서 조사한 값에 추가적으로 다음 수를 확인해보는 것이다.
맞을 경우 count를 1씩 올려준다. 우선 결과를 먼저 말하자면 다음과 같이 해결할 수 있다.
여기서 보면 앞에서 구했던 수를 구하기 위해 calc함수가 다시 calc함수를 호출하고 있다. 이게 가능할까?
가능하다! 함수 호출을 위해 할당되는 메모리만 추가적으로 늘어날 뿐!
자기 함수를 호출하는 것이 이상하지 않은가?
우선 재귀호출이 무엇인지 알고 재귀호출로 구할 수 있는 피보나치수열에 대해 공부해보겠다.
재귀호출
호출한 함수에서 다시 그 함수를 호출하는 것을 말한다.
예를 들어 숫자 10부터 0까지 출력하는 프로그램을 만들어보겠다.
for문으로 출력해도 괜찮지만 위 처럼 출력해도 문제없다. 대신 멈춰주는 조건을 꼭 넣어주어야 한다.
메인에서 recursiveFunc(10) 함수를 호출하면 이 함수가 recursiveFunc(9)를 다시 호출한다. 그리고 i가 0이되면 그만 호출하면 프로그램은 종료된다.
재귀호출함수의 가장 큰 문제는 메모리이다. 함수를 호출하면 함수에 필요한 메모리를 미리 할당해 놓는다
그런데 recursiveFunc(10) -> recursiveFunc(9) -> ... -> recursiveFunc(0) 이런식으로 호출하게 되면
recursiveFunc(0)이 종료되기 전까지 recursiveFunc(10)은 끝난게 아니므로 메모리가 해제되지 않아서 계속 쌓이게 된다.
피보나치수열
0, 1, 1, 2, 3, 5, 8, ...
이렇게 앞에 있는 두 수의 합이 다음의 수가 되는 수열이다.
구하는 알고리즘은 여러 가지가 있겠지만 3가지 방법을 소개하겠다. 맨 마지막 방법은 수학(행렬)을 공부해할 수 있으므로 단순히 소개만 하고 끝내겠다.
#1 재귀함수
함수에서 다시 자기 자신을 호출해서 문제를 해결하는 방법이다.
코드를 통해 이해하는 것이 빠르다. 예를 들어
피보나치[0]: 0 = 0
피보나치[1]: 1 = 1
피보나치[2]: 1 = 1
피보나치[3]: 2 = 1 + 1
피보나치[4]: 3 = 2 + 1
피보나치[5]: 5 = 3 + 2
피보나치[6]: 8 = 5 + 3
이라고 할 때 "피보나치[5]"를 구해보자
피보나치[5] = 피보나치[4] + 피보나치[3] 으로 표현할 수 있다. 그럼 4번째와 3번째 값이 무엇인지 찾아야 한다
피보나치[4] = 피보나치[3] + 피보나치[2] 로 표현할 수 있다.
피보나치[3] = 피보나치[2] + 피보나치[1] 로 표현할 수 있다.
그럼 앞에 있는 수열을 또 찾아야 한다. 피보나치 함수가 다시 피보나치 함수를 호출해서 계속 앞에 있는 숫자를 찾아나가는 방법이다. 호출한 함수가 다시 그 자기 함수를 호출하는 방법을 재귀함수라과 한다.
이때 재귀함수의 필수는 꼭 마지막에 대한 조건이 있어야 한다는 것이다. 여기에서는 n이 1보다 작거나 같을 경우 더 이상 자기자신을 호출하지 않고 그냥 n을 반환해서 마무리한다.
# 메모이제이션을 이용한 접근
그런데 여기서 보면 피보나치[5]를 찾기 위해
피보나치[4] = 피보나치[3] + 피보나치[2] 와
피보나치[3] = 피보나치[2] + 피보나치[1] 를 구해야 한다.
보면 피보나치[2]를 두 번 찾아야 하는 문제가 있다. 한 번 구한 뒤 어딘가에 저장해 놓으면 굳이 찾아야 할 필요가 없을 것이다.
# 행렬을 이용한 접근
맨 마지막 방법은 수학을 좋아한다면 충분히 따라갈 수 있는 접근이다.
하지만 굳이 여기에서는 깊이 있게 설명하지 않겠다.
D[i] = 1 * D[i-1] + 1 * D[i-2]
D[i-1] = 1 * D[i-1] + 0 * D[i-2]
이 공식을 행렬로 푼 방법이다.
D[6] = 8 + 5
D[5] = 5 + 3
이렇게 하면 단순 제곱의 연산으로 피보나치수열의 값을 구할 수 있다. 추가적으로 더 성능을 향상시킬 수 있는데 이 부분은 더 어려워지므로 패스하겠다.
난 재귀함수를 좋아하지 않는다. 적은 수를 구할 때는 굉장히 빠르지만 데이터가 기하급수적으로 늘어날 경우 프로그램이 종료될 수도 있기 때문이다.
지금 문제에서는 입력받는 수 개수(N)가 최대 20이기 때문에 가능했다.
재귀 함수는 스택이라는 자료구조로 해결할 수 있다. 우리는 아직 스택을 배우지 않았으므로 list를 이용해 풀어보겠다. 앞에서 재귀함수로 풀이한 방법과 비교해보자
