재귀 알고리즘의 기본
여러가지 재귀 알고리즘과 분석 방법, 그리고 재귀 알고리즘을 비재귀적으로 구현하는 방법을 살펴보도록 하자
재귀 알아보기
어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀(recursion)이라고 한다. 재귀의 개념을 표현한 예로, 화면 가운데 계속해서 같은 화면이 반복해서 나타난다. 이러한 재귀의 개념을 사용하여 1,2,3,4,,,과 같이 무한하게 이어지는 자연수를 다음과 같이 정의할 수 있다.
자연수의 정의
- 1은 자연수이다.
- 어떤 자연수의 바로 다음 수도 자연수이다.
무한히 존재하는 자연수를 재귀적 정의(recursive definition)를 사용하여 위의 두 문장으로 정의했다. 재귀를 효과적으로 사용하면 이러한 정의뿐만 아니라 프로그램을 간결하고 효율성 좋게 작성할 수 있다.
팩토리얼 알아보기
재귀를 사용하는 대표적인 예로 양의 정수 곱을 구하는 팩토리얼(factorial)문제가 있다. 팩토리얼은 양의 정수를 순서대로 곱한다는 의미로 순차 곱셈이라고도 한다. 양의 정수 n의 팩토리얼(n!)은 다음과 같이 재귀적 정의를 할 수 있다.
팩토리얼 n!의 정의(n은 양의 정수)
- 0! = 1
- n > 0이면 n! = n x (n-1)!
예를 들어 10!은 10x9!로 구할 수 있고, 다시 9!은 9x8!로 구할 수 있다. 이러한 정의를 그대로 아래 프로그램 코드를 통해 살펴보자.
#양의 정수 n의 팩토리얼 구하기
def factorial(n:int) -> int:
#n > 0이면 n! = n x (n-1)!
if n > 0:
return n * factorial(n-1)
#0! = 1
else:
return 1
n = int(input("출력할 팩토리얼값을 입력해주세요."))
print(f'{n}의 팩토리얼은 {factorial(n)}입니다.')>>>
출력할 팩토리얼값을 입력해주세요.3
3의 팩토리얼은 6입니다.
factorial( ) 함수는 매개변수 n에 전달받은 값이 0보다 크면 n*factorial(n-1)의 값을 반환하고 그렇지 않으면 1을 반환한다.
math.factorial( ) 함수
파이썬에서는 팩토리얼값을 구하는 표준 라이브러리로 math 모듈에서 factorial( ) 함수를 제공한다. math.factorial(x)는 정수 x의 팩토리얼갓을 반환하고 이때, x가 정수가 아니거나 음수라면 valusError 예외 처리를 내보낸다. 이처럼 음수를 인수로 전달받으면 예외 처리를 내보내도록 하고 있다.
📄 재귀 호출은 '함수 자신'이 아니라 '자기 자신과 똑같은 '자기 자신과 똑같은 함수'를 호출한다고 이해하는 것이 자연스러우며, 함수가 자기 자신을 호출하면 끝없이 계속해서 자신을 호출하는 행위를 계속하기 때문이다.
직접 재귀와 간접 재귀
factorial( )함수는 내부에서 자신과 똑같은 factorial( ) 함수를 호출한다. 이와 같이 자신과 똑같은 함수를 호출하는 방식을 직접(direct) 재귀라고 한다. 이와 다르게 간접(indirect) ㅐ귀는 a( ) 함수가 b( )함수를 호출하고 다시 b( ) 함수가 a( ) 함수를 호출하는 구조이다. 이 2가지 재귀 방식을 살펴보자.
재귀 알고리즘은 풀어야 할 문제나 계산할 함수 또는 처리할 자료구조가 재귀적으로 정의되어 있는 경우에 적용된다. 이러한 점에서 재귀 과정으로 팩토리얼값을 구하는 문제는 재귀의 원리를 이해하기 위한 예제일 뿐 현실적으로는 적절하지 않다.
유클리드 호제법 알아보기
두 정숫값의 최대 공약수(GCD)를 재귀적으로 구하는 방법을 생각해보자. 2개의 정숫값을 직사각형 두 변의 길이라고 생생각하면 두 정숫값의 최대 공약수를 구하는 문제는 다음과 같이 바꿀 수 있다.
- 22 X 8 크기의 직사각형에서 짤은 변의 길이인 8을 한 변으로 하는 정사각형으로 나눈다.
- 그러면 8 x 8 크기의 정사각형 2개가 만들어지고 8 X 6 크기의 직사각형이 남게 된다.
- 남은 8 X 6 크기의 직사각형에서도 다음과 같은 과정을 수행하면 6 X 6 크기의 정사각형 1개가 만들어지고 6 X 2 크기의 직사각형이 남는다.
- 남은 6 X 2 크기의 직사각형에서도 다시 같은 과정을 수행한 결과가 2 X 2 크기의 정사각형이 3개 만들어진 것이다. 이렇게 얻은 정사각형의 변의 길이인 2가 8과 22의 최대 공약수가 되는 것이다.
정리하면 두 정숫값이 주어질 때 큰 값을 작은 것으로 나누어 떨어지면 작은 값이 최대 공약수가 된다. 나누어 떨어지지 않으면 작은 값과 나머지에 대해 같은 과정을 나누어 떨어질 때까지 재귀적으로 반복한다.
이 과정을 수학에선 아래와 같이 표현한다. 두 정수 x와 y의 최대 공약수를 gcd(x,y)로 표현하고. 예를 들어 x =az와 y = bz를 만족하는 정수 a,b와 최대의 정수 z가 존재할 때 z는 gcd(x,y)라고 할 수 있다.
- y가 0이면 .... x
- y가 0이 아니면 .... gcd(y, x%y)
이 알고리즘을 유클리드 호제법(euclidean algorithm)이라고 한다. 유클리드 호제법으로 두 정숫값의 최대 공약수를 구하는 코드를 아래를 통해 살펴보자
# 유클리드 호제법으로 최대 공약수 구하기
def gcd(x: int, y: int) -> int:
#정수값 x와 y의 최대 공약수를 반환
if y == 0:
return x
else:
return gcd(y,x%y)
print("두 정숫값의 최대 공약수를 구합니다.")
x = int(input("첫 번째 정숫값을 입력하세요.: "))
y = int(input("첫 번째 정숫값을 입력하세요.: "))
print(f'두 정숫값의 최대 공약수는 {gcd(x,y)}입니다.')math.gcd( ) 함수
파이썬에서는 최대 공약수를 구하는 표준 라이브러리로 math 모듈에서 gcd( ) 함수를 제공한다.
재귀 알고리즘 분석
하향식 분석과 상향식 분석을 살펴보고, 재귀 알고리즘을 비재귀적으로 구현하는 방법을 알아보도록 하자.
#순수한 재귀 함수 구현하기
def recur(n):
if n > 0:
recur(n-1)
print(n)
recur(n-2)
x = int(input('정수값을 입력하세요.: '))
recur(x)recur( ) 함수는 앞에서 다룬 factorial( ) 함수나 gcd( )함수와 달리 함수 안에서 재귀 호출을 2번 실행합니다. 이처럼 재귀 호출을 여러 번 실행하는 함수를 순수(genuinely)재귀라고 하는데 실제 동작은 복잡하다. recur( ) 함순는 1,2,3,1,4,1,2를 한 줄에 하나씩 출력한다. 만약 n이 3이나 5라면 어떤 결과를 출력할지는 간단하게 알 수 없다. 재귀 호출하는 recur( )함수를 하향식(top-down)과 상향식(bottom - up)방법으로 분석해 보도록 하자.
하향식 분석
매개변수 n에 4를 전달하면 recur( ) 함수는 다음과 같은 순서로 실행한다.
recur(4)의 실행 과정
- recur(3)을 실행한다.
- 4를 출력한다.
- recur(2)를 실행한다.
위의 과정 2에서 4가 출력되려면 recur(3)의 실행을 완료한 뒤이므로 먼저 과정 1에서 recur(3)이 무엇을 하는지 알아보야 한다. 각각의 상자는 recur( )함수의 동작을 나타낸다. 전달받은 값이 0이하면 recur( ) 함수는 아무 일도 하지 않으므로 비어있다는 의미로 상자 안에 -를 표시한다.
왼쪽 화살표를 따라 1칸 아래쪽 상자로 이동하고, 다시 원래 호출한 상자로 되돌아오면 노란 동그라미 안의 값을 출력한다. 이어서 오른쪽 화살표를 따라 1칸 아래쪽 상자로 이동한다. 를 하나의 단계로 생각해야 한다.
이런식으로 진행된다는 것을 이해하고 넘어가시길 바랍니다.
가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석 방법을 하향식 분석(top-down analysis)라고 한다. 그러나 recur(1), recur(2)를 여러 번 호출하고 있는 모습이 보이기 때문에 하향식 방식이 반드시 효율적이라고는 말할 수 없다.
상향식 분석
하향식 분석과는 반대로 아래쪽부터 쌓아 올리며 분석하는 방법을 상향식 분석(bottom-up analysis)이라고 한다. recur( ) 함수는 n이 양수일 때만 실행하기 때문에 먼저 recur(1)이 어떻게 처리되는지를 알아야 한다. 다음과 같은 순서로 recur(1)이 실행된다.
recur(1)의 실행 과정
- recur(0)을 실행한다.
- 1을 출력한다.
- recur(-1)을 실행한다.
recur(1)을 실행하면 과정 1의 recur(0)과 과정 3의 recur(-1)은 출력할 내용이 없으므로 결국 과정 2의 1만 출력하게 된다.
recur(2)의 실행 과정
- recur(1)을 실행한다.
- 2를 출력한다.
- recur(0)을 실행한다.
recur(2)를 실행하면 과정 1에서 recur(1)은 1을 출력하지만 과정 3의 recur(0)은 아무것도 출력하지 않는다. 결국 recur(1)과 recur(2)의 과정을 거쳐서 1과 2를 출력한다.
recur( ) 함수의 재귀 호출을 거꾸로 출력하기
#recur() 함수의 재귀 호출을 거꾸로 출력하기
def recur(n):
if n > 0:
recur(n-2)
print(n)
recur(n-1)
x = int(input('정수값을 입력하세요.: '))
recur(x)recur(4) 함수의 실행 결과는 2,1,4,1,3,2,1을 순서대로 출력한다. 이 프로그램을 상향식으로 분석하면 다음과 같이 할 수 있다.
recur(-1) : 아무것도 하지 않음
recur(0) : 아무것도 하지 않음
....................................................................................................................................
recur(1) : recur(-1) 1 recur(0) -> 1
recur(2) : recur(0) 2 recur(1) -> 2 1
recur(3) : recur(1) 3 recur(2) -> 1 3 2 1
recur(4) : recur(2) 4 recur(3) -> 2 1 4 1 3 2 1
재귀 알고리즘의 비재귀적 표현
꼬리 재귀를 제거하기
recur( ) 함수의 맨 끝에서 재귀 호출하는 꼬리 재귀 recur( n -2 ) 함수의 의미는 '인수로 n-2의 값을 전달하고 recur( ) 함수를 호출하는 것'이다. 따라서 이 호출은 다음 동작으로 바꿀 수 있다.
n의 값을 n - 2로 업데이트하고 함수의 시작 지점으로 돌아갑니다.
# 비재귀적으로 재귀 함수 표현하기(꼬리 재귀를 제거)
def recur(n):
while n > 0:
recur(n-1)
print(n)
n = n - 2
x = int(input("정수값을 입력하세요.:"))
recur(x)recur( ) 함수의 맨 끝에서 실행된 재귀 호출인 꼬리 재귀(tail recursion)를 쉽게 제거할 수 있다.
재귀를 제거하기
꼬리 재귀와 달리 맨 앞에서 호출하는 recur(n-1) 함수는 제거하기가 쉽지 않다. 왜냐 n값을 출력하기 전에 recur(n-1)이 실행되어야 하기 때문이다. 예를 들어 n값이 4인 경우 재귀 호출 recur(3)의 처리가 완료되기 전까지 4를 어딘가에 저장해놔야 한다. 다시 말해서 재귀 호출 recur(n-1)을 제거하려면 다음과 같이 간단히 바꿀 수는 없다.
n값을 n-1로 업데이트하고 함수의 시작 지점으로 돌아간다. 🙅♂️(X)
why? 현재의 n값을 임시로 저장할 필요가 있기 때문에 위와 같이 바꿀 순 없다. 이 문제는 n값을 출력할 때 임시로 저장했던 n을 꺼내 그 값을 출력해야 한다. 이러한 문제는 스택(Stack)으로 해결할 수 있다.
#스택으로 재귀함수 구현하기(재귀를 제거)
from stack import Stack #Stack.py에서 스택 클래스 임포트
def recur(n):
#재귀를 제거한 recur()함
s = Stack(n)
while True:
if n > 0 :
s. push(n) # n값을 푸시
n = n - 1
continue
if not s.is_empty(): # 스택이 비어 있지 않으면
n = s.pop() # 저장한 값을 n에 팝
print(n)
n = n - 2
continue
break
x = int(input("정수값을 입력해주세요.: "))
recur(x)
1. n의 값을 푸시하고 왼쪽 아래 화살표를 따라 간다 (n <- n-1)
2. 돌아오면 팝한 ㅁ 안의 값을 출력한다.
3. 오른쪽 아래 화살표를 따라 간다 (n <- n-2)
하노이의 탑
쌓아 놓은 원반을 최소 횟수로 옮기는 알고리즘인 하노이의 탑
하노이의 탑 알아보기
하노이의 탑(towers of Hanoi)은 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제다. 먼저 크기가 다른 원반이 첫 번째 기둥에 쌓여있는 상태로 시작한다. 이상태서 모든 원반을 세 번째 기둥에 최소 횟수로 옮기면 된다. 원반은 1개씩 옮길 수 있고 큰 원반은 작은 원반 위에 쌓을 수 없다는 규칙을 지켜야 한다.
#하노이의 탑 구현하기
def move(no, x, y):
if no >1:
move(no -1,x,6-x-y)
print(f"원반 [{no}]을(를) {x}기둥에서 {y}기둥으로 옮깁니다.")
if no >1:
move(no -1, 6-x-y, y)
print("하노이의 탑을 구현합니다.")
n = int(input("원반의 개수를 입력하세요."))
move(n,1,3)📌 매개변수 no은 옮겨야 할 원반의 개수, x는 시작 기둥의 번호, y는 목표 기둥의 번호
>>> 하노이의 탑을 구현합니다. 원반의 개수를 입력하세요. 3
원반 [1]을(를) 1기둥에서 3기둥으로 옮깁니다.
원반 [2]을(를) 1기둥에서 2기둥으로 옮깁니다.
원반 [1]을(를) 3기둥에서 2기둥으로 옮깁니다.
원반 [3]을(를) 1기둥에서 3기둥으로 옮깁니다.
원반 [1]을(를) 2기둥에서 1기둥으로 옮깁니다.
원반 [2]을(를) 2기둥에서 3기둥으로 옮깁니다.
원반 [1]을(를) 1기둥에서 3기둥으로 옮깁니다.
8퀸 문제
8퀸 문제 알아보기
8퀸(8 -Queen problem) 문제는 재귀 알고리즘을 설명할 때 자주 나오는 예제이다.
8개의 퀸이 서로 공격하여 잡을 수 없도록 8X8 체스판에 배치하라.
퀸 배치하기
8개의 퀸을 배치하는 조합이 모두 몇 가지이니 알아보도록 하자. 체스판은 64칸(8X8)이므로 첫 번째 퀸을 배치할 때는 64칸 중 아무 곳이나 선택할 수 있다. 그리고 두 번째 퀸을 배치할 때는 나머지 63칸 중에서 임의로 선택한다. 이렇게 계속해서 8번째 퀸을 배치할 곳을 생각하면 다음과 같이 조합의 수가 만들어진다.
64 X 63 X 62 X 61 X 60 X 59 X 58 X 57 = 178,462,987,637,760
이 조합을 나열한 뒤 각 조합이 8퀸 문제의 조건을 만족하는지 조사하는 것은 비현실적이다. 퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있기 때문에 다음과 같은 규칙을 세울 수 있다.
규칙 1 각 열에 퀸을 1개만 배치한다.
이렇게 하면 퀸을 배치하는 조합의 수가 아주 많이 줄어들지만 여전히 그 수는 많다. (8 X 8 X 8 X 8 X 8 X 8 X 8 X 8)
규칙 2 각 행에 퀸을 1개만 배치한다.
분기 작업으로 문제 해결하기
배열 pos는 퀸의 배치를 나타낸다. i열에 배치한 퀸의 위치가 j행에 있다면, pos[i]의 값을 j로 한다. 예를 들어 pos[0]의 값이 0이라면 퀸이 0열 0행에 배치되었다는 것을 의미한다. 또 pos[1]의 값이 4라면 퀸은 1열 4행에 배치되어있다.
| ⚫(0행 0열) | |||||||
| ⚫ | |||||||
| ⚫ | |||||||
| ⚫ | |||||||
| ⚫(1행 4열) | |||||||
| ⚫ | |||||||
| ⚫ | |||||||
| ⚫ |
0 1 2 3 4 5 6 7
행 = pos[i] / 열 = j(값)
# 각 열에 퀸을 1개씩 배치하는 조합을 재귀적으로 나열하기
pos = [0] * 8
def put():
#각 열에 배치한 퀸의 위치 출력
for i in range(8):
print(f'{pos[i]:2}', end=" ")
def set(i):
#i열에 퀸을 배치
for j in range(8):
pos[i] = j
if i == 7:
put()
else:
set(i+1) #다음 열에 퀸 배치
set(0) #0열에 퀸을 배치16,777,216가지 조합을 모두 나열한다.
차례대로 가지가 뻗어 나가듯이 배치 조합을 열거하는 방법을 분기(branching)작업이라고 하고 하노이 탑이나 8퀸 문제처럼 큰 문제를 작은 문제로 분할하고, 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법을 분할 정복법(divid and conquer)이라고 한다.
이때 주의할 점은 문제를 분할할 때 작은 문제 풀이법에서 원래의 문제 풀이법을 쉽게 도출할 수 있도록 설계해야 한다.
한정 작업과 분기 한정법
분기 작업으로 퀸을 배치하는 조합을 나열할 수는 있지만 8퀸 문제의 최종 답을 얻을 수는 없다. 다음은 앞에 분기를 한정할 때 정했던 규칙이다.
규칙 2 각 행에 퀸을 1개만 배치한다.
# 각 열에 퀸을 1개씩 배치하는 조합을 재귀적으로 나열하기
pos = [0] * 8 # 각 열에 퀸의 위치
flaf = [False] * 8 #각 행에 퀸을 배치했는지 체크
def put():
#각 열에 배치한 퀸의 위치 출력
for i in range(8):
print(f'{pos[i]:2}', end=" ")
def set(i):
#i열에 퀸을 배치
for j in range(8):
if no flag[j]:
pos[i] = j
if i == 7:
put()
else:
flag[j] =True
set(i+1) #다음 열에 퀸 배치
flag[j] = False
set(0) #0열에 퀸을 배치배열은 같은 행에 중복하여 퀸을 배치하지 않기 위한 표시로 사용된다. j행에 퀸을 배치하면 flaf[j]를 True로, 배치하지 않으면 False로 한다.
'자료구조와 알고리즘 > 자료구조와 함께 배우는 알고리즘' 카테고리의 다른 글
| [자료구조와 함께 배우는 알고리즘][정렬 알고리즘] - 셸 정렬 (0) | 2021.10.06 |
|---|---|
| Python - 정렬 알고리즘(부제: 정렬 알고리즘의 종류와 사용방법을 알아보자.) (0) | 2021.08.03 |
| Phython - 스택과 큐(부제: 스택과 큐를 알아보며 예외처리가 무엇 인지를 살펴보자!) (0) | 2021.07.05 |
| Python - 검색 알고리즘(부제: 검색 알고리즘이 무엇인지 살펴보고, 선형 검색, 이진 검색, 해시법을 알아보자) (0) | 2021.06.26 |
| Python - 자료구조와 배열 (0) | 2021.05.31 |