[알고리즘공부] [자료구조] 재귀함수 응용 - 거듭제곱 등 예제
[파이썬] [거듭제곱] [N까지의 합] [구구단] [팩토리얼]
재귀함수란?
재귀함수란, 어떤 함수 func(n)이 있다고 할 때, 이 함수의 내부에서 자기 자신을 호출하는 함수를 말한다. 보통의 재귀함수의 구성은 다음과 같다.
def solution(n):
if n == 5:
return
else:
print('자기자신 호출 {}'.format(n))
return solution(n+1)
solution(0)
결과
자기자신 호출 0
자기자신 호출 1
자기자신 호출 2
자기자신 호출 3
자기자신 호출 4
위 코드는 재귀함수의 동작에 대해 알아보기 위해 임의로 쓴 코드이다. 위 코드를 예로 들어서 재귀 함수의 생김새를 알아보자.
- 자기 자신을 호출하는 부분
- 일정 조건을 만족하면 호출을 정지하고 어떤 값을 return하는 부분
이 두 분으로 나뉘어진다.
그리고 함수 호출은 메모리의 스택 영역에 쌓이게 되는데,
스택은 후입선출(LIFO)방식으로 데이터를 저장하는 자료구조임을 우리는 알고 있다.
그럼, 재귀함수를 짜는 법을 알아보자
1. 자신을 호출하는 것을 정지시키는 조건을 만들어야 한다.
위의 경우에서는, n이 5가 되면 정지하고 return을 한다. 그러면, 그전에 호출된 함수(solution(4))에서 그 return값을 받아서, solution(3)의 결과를 만들수 있게 한다. 어느 순간 정지하는 조건을 만들지 않으면, 메모리에 함수가 무한히 쌓여서 스택 오버플로우 현상이 발생한다.
2. 한 동작마다 해야하는 것들을 정의해서, 함수 내부에 써넣는다.
위의 경우에서는 print문에 해당한다. 재귀라는것 또한 어떤 행동을 반복한다는 것인데, 그 반복에 해당하는 동작을 써넣는다.
3. 다음 함수를 호출할 때, 파라미터로 어떤 것들을 넘겨줘야 할 지 정해야 한다.
이는 생각보다 좀 어려운데, 매 동작마다 필요한 데이터를 넘겨줘야 한다. 그리고 계속 업데이트하면서 사용할 변수가 있는 경우는 전역변수를 쓰기도 해야 한다. 이런 저런 경우가 있으므로, 문제를 잘 읽고 판단하도록 하자.
여기까지, 재귀함수가 무엇인지, 어떻게 구성되어 있는지, 어떻게 흘러가는지, 어떻게 만들어야 할지 간략히 알아봤다. 이를 예제를 통해 실습해보자. 아래 예제들은, 충~~~분히 반복문으로 풀 수 있지만, DFS 등의 좀더 고차원적인 문제의 기본이 되는 재귀함수의 연습을 위해 실습하는 것이므로, 꼭 재귀로 풀길 바란다.
1. 재귀함수를 이용한 거듭제곱
똑같은 수나 문자를 여러 번 곱하는 것을 거듭제곱이라고 한다.
흔히 우리가 말하는 2의 4제곱(\(2^4=16\)), 5의 3제곱(\(5^3=125\)) 등은 거듭제곱을 표현한 것이다.
이를 코드로 구현해보자.
반복문 사용
a의 n제곱 값을 구하고 싶을 때, for문을 사용해 직관적으로 코드를 작성할 수 있다.
def power(a, n):
ans = 1
for _ in range(n):
ans = ans*a
return ans
print(power(4,5)) # 4의 5승
1. 예제 코테 문제: Softeer, 바이러스가 단순 반복문을 통해 해결할 수 있다.
그러나 a와 n이 아주 큰 수라면 반복문을 통해 해결 할 수 없다.
즉, for문의 경우 시간 복잡도가 O(N)이므로 n의 범위가 \(10^16\) 이라면 굉장히 긴 시간이 필요하게 된다. 이를 해결하기 위해 O(log N) 시간 복잡도를 갖는 재귀함수를 통해 풀어야 한다.
__재귀함수 사용__
a의 n제곱을 쭉 풀어보면 다음과 같다. \[a^n = \underbrace{a \times a \times a \times \cdots \times}_{n} a\]
위 식은 부분문제로 나눌 수 있다.
만약
실제 수에 대입해본다고 했을 때, 2의 4제곱(\(2^4=16\))을 구하기 위해선 2의 3제곱(\(2^3=8\))에 2를 한 번 더 곱해주면 되는 것과 같다.
이를 점화식으로 표현하면 \(a^n = a^{(n-1)} \times a\)가 된다.
예시 코드를 보면 n이 1일때 a를 return 하도록 할 수 있다.
def power(a, n):
if n == 1:
return a
return power(a, n-1) * a
그러나, 위에 살펴본 두 방식은 모두 n번만큼의 연산을 요구하므로 시간복잡도는 O(n)으로 표현할 수 있다.
분할정복 활용 - 지수법칙을 이용한 재귀함수
지수법칙을 잘 활용하면 a의 n제곱을 보다 효율적으로 구할 수 있다.
두 거듭제곱 간 밑인 a가 같을 때, a의 n제곱과 a의 m제곱을 곱한 수는 두 지수 n과 m을 더한 값을 지수로 취하는 \(a^{(n+m)}\)로 표현할 수 있다.
이를 활용하면, \(a^n\)을 \(a^{(n / 2)} * a^{(n / 2)}\)로 표현할 수 있다.
수식으로 표현해 한 눈에 들어오기 힘들다면 수를 직접 넣어서 살펴보자.
\(2^4\)은 \(2^2\) 와 \(2^2\)를 곱한 것이다.
즉, \(2^4 = 2^2 * 2^2\)인 것이다.
그렇다면 n이 2로 나누어 떨어지지 않는 홀수라면 어떻게 될까? 그냥 a를 한 번만 더 곱해주면 간단히 해결된다.
즉, \(a = 2\), \(n = 5\)라고 했을 때,
\(2^5 = 2^2 * 2^2 * 2\) 로 표현할 수 있다.
이는 즉, \(2^2, 2^2, 2^1\)을 모두 곱해준 것으로, 지수를 모두 더해주면 \(2 + 2 + 1 = 5\)로, \(2^5\)이 된다.
이러한 접근 방식은 n을 매번 2로 나눠 더 작은 문제로 만들어 해결하는 분할정복 방식이라고 할 수 있다.
분할 정복을 이용할 땐 n을 2로 나누는 과정에서 n이 1일 때, 다음 재귀함수에 들어가는 n은 0이 될 수 있으므로(즉, 1 // 2 = 0),
n이 0일 때 리턴해줄 값도 명시해준다.
def power(a, n):
if n == 0:
return 1 # a^0 = 1 이므로 1 리턴
if n == 1:
return a
if n % 2 == 0: # n이 짝수일 때
return power(a, n//2) * power2(a, n//2)
else: # n이 홀수일 때
return power(a, n//2) * power2(a, n//2) * a
무언가 훨씬 효율적이게 보이긴 하지만 아쉽게도 위 함수 역시 O(n)의 시간복잡도를 가진다.
그렇다면 분할정복 방식도 반복문이나 처음에 구현한 재귀함수와 비교해 별 다른 차이를 보이지 않는 것일까?
물론 그렇지 않다.
어차피 똑같은 값이 나오는 power(a, n//2)를 두 번 곱해주면 power함수의 호출을 반으로 줄일 수 있다.
이를 코드로 구현하면 다음과 같다.
def power(a, n):
if n == 0:
return 1
if n % 2 == 0:
res = power(a, n//2)
return res * res
else:
res = power(a, n//2)
return res * res * a
이것을 다시 더 간단하게 하면
def power(a, n):
if n == 0:
return 1
res = power(a, n//2)
if n % 2 == 0:
return res * res
else:
return res * res * a
사실 n이 0일때만 처리해주면 된다. n이 1이 될 때는 power(a, 1 // 2)가 호출되므로 이는 즉 power(a, 0)을 호출하기 때문이다.
이 방식은 O(logN)의 시간복잡도 안에 거듭제곱 연산을 수행할 수 있다.
그럼 이에 대한 문제를 풀어보자: 2. 예시 코테 문제: Softeer, 수퍼바이러스
2. N까지의 합
n이 주어졌을 때, 0부터 n까지의 수들을 더한 값을 출력하라
def solution(n):
if n == 0:
return 0
else:
return n + solution(n-1)
print(solution(4)) # 10
일단, 입력받은 n이 0이라면 호출을 멈춘다. 그렇지 않다면, n + solution(n-1)을 호출한다.
2.1 리스트의 모든 요소의 곱도 재귀함수를 이용해보자
주어진 리스트에서 모든 원소들 곱은 sum() 함수와 다르다.
위 문제의 답은 다음과 같다.
def mul(arr,i):
if i == len(arr):
return 1
else:
return arr[i] * mul(arr,i+1)
def solution(num_list):
if mul(num_list,0) < sum(num_list)**2:
return 1
else:
return 0
3. 구구단
재귀함수를 이용해서 n의 구구단을 출력해 보자.
def solution(n, count):
if count == 9:
print(n, "*", count, "=", n*count)
return
else:
print(n, "*", count, "=", n*count)
return solution(n, count+1)
print(solution(3, 1)) # 구구단 3단 출력
구구단은 9까지 있으니깐 count가 9일때 멈춘다.
count가 9가 아니면 1부터 9까지 증가시킨다.
4. 배열의 합
주어진 배열 arr의 요소들을 sum을 이용하지 말고 i번째부터 끝까지 더해본다.
def solution(arr, i):
if i == len(arr)-1:
return arr[i]
else:
return arr[i] + solution(arr, i+1)
arr=[1,2,3,4,5]
print(solution(arr,0)) # 15
이번엔 주어진 배열 arr의 요소들을 sum을 이용하지 말고 s번째부터 e번째까지 더해보자
def solution(arr, s, e):
if s == e:
return arr[s]
else:
return arr[s] + solution(arr, s+1, e)
arr=[1,2,3,4,5]
print(solution(arr,1,3)) # 1번째부터 3번째 (2+3+4)
5. 순차 탐색
주어진 배열 arr에서 target이 몇번째 있는지 찾는 재귀함수를 만들자.
def solution(arr, target, n):
if arr[n] == target:
return n
else:
return solution(arr, target, n+1)
arr = [1, 6, 10, 5, 2, 7]
target = 7
print('target의 arr의 {}번째에 있다.'.format(solution(arr, target, 0)))
6. 최대공약수 - 유클리드 호제법, 최소공배수
최대 공약수란, 숫자 a와 b가 주어졌을 때, 공통되는 약수 중에서 최대 값을 의미한다.
유클리드 호제법
숫자 a와 b가 주어졌을때, __a를 b로 나눈 나머지__와 __b__의
즉, 계속해서 a에 b를 대입하고 b로 나눈 나머지(a%b)를 b에 대입시켜서 a에 b를 나눈 나머지가 0이 될때까지 반복을 하며 나머지가 0이 될때 b가 바로 최대 공약수 이다.
def gcd(a, b):
if a < b:
a, b = b, a
if a % b == 0:
return b
else:
return gcd(b, a%b)
print(gcd(18, 12)) # 6
최소공배수
서로 다른 수 a, b의 배수중에서 공통되는 배수 중에 가장 작은 값을 의미한다.
최소공배수는 a, b의 곱을 a, b의 최대 공약수로 나누면 나오게 된다.
def lcm(a, b):
return int(a * b / gcd(a, b))
print(lcm(18, 12)) # 36
7. 이진수 변환
10진수를 이진수로 변환한다.
10진수를 2진수로 변환할때 2를 반복해서 나누고 그 나머지를 기억해둔다. 이것을 구현하면 된다
def solution(n, answer):
if n >= 2:
answer.append(n%2)
return solution(int(n/2), answer)
else:
answer.append(n)
return
answer = []
n = 10
solution(n, answer)
print(answer) # [1,0,1,0]
8. 팩토리얼
N의 수가 주어지면 1부터 N까지의 수를 다 곱한다.
예를 들어, 5가 주어지면 \(5 \times 4 \times 3 \times 2 \times 1\)이다.
즉, 반복해서 1을 뺀 값을 곱해주고 1이 되면 멈춘다.
def solution(n):
if n == 1:
return 1
else:
return n * solution(n-1) # 자신에 자신보다 1작은 수를 곱해준다.
n = 5
print(solution(n)) # 120
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
