용어
-
recursion(재귀): 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우
-
direct recursion(직접재귀): 자신과 똑같은 함수를 호출하는 방식
-
indirect recursion(간접재귀): a->b->a순으로 다시 호출하는 방식
-
유클리드 호제법: 두 정수에서, 큰 값을 작은 값으로 나누는 과정을 재귀적으로 반복해 최대공약수을 구하는 방식
-
재귀 알고리즘의 하향식(top-down) 분석: 로직의 상단부터 차례로 분석해나가는 방법
-> 같은 함수를 여러번 호출할 수 있어 효율적이지 않을 수 있음 -
재귀 알고리즘의 상향식(bottom-up) 분석: 로직의 하단부터 쌓아 올리며 분석해나가는 방법
-> 같은 함수를 여러번 호출할 필요가 없음 -
재귀 함수의 재귀성 제거: Stack을 활용하면 가능
-
branching(분기작업): 가지를 뻗어나가듯 배치 조합을 열거하는 방법
-
분할 정복법=분할 해결법: 큰문제를 작은문제로 분기하여 작은 문제 풀이법을 결합해 큰 문제를 푸는 방법
-
bounding(한정작업): 필요하지 않은 분기를 제거해 한정하는 작업
-
분기 한정법: 분기 작업과 한정 작업을 조합하여 문제를 푸는 방법
실습
유클리드 호제법을 활용한 최대공약수 구하기
def greatest_common_divisor(x: int, y: int) -> int:
a, b = (x, y) if x > y else (y, x)
if b:
return greatest_common_divisor(b, a % b)
else:
return a
print(f"36과 72의 최대공약수는 {greatest_common_divisor(36, 72)}입니다.")
print(f"36과 48의 최대공약수는 {greatest_common_divisor(36, 48)}입니다.")
print(f"108과 24의 최대공약수는 {greatest_common_divisor(108, 24)}입니다.")
print(f"27과 72의 최대공약수는 {greatest_common_divisor(27, 72)}입니다.")
print(f"18과 45의 최대공약수는 {greatest_common_divisor(18, 45)}입니다.")
# 실행결과 ==========================================
36과 72의 최대공약수는 36입니다.
36과 48의 최대공약수는 12입니다.
108과 24의 최대공약수는 12입니다.
27과 72의 최대공약수는 9입니다.
18과 45의 최대공약수는 9입니다.하노이의 탑
"""
아이디어
- 어떤 형태의 탑이더라도 맨 아래 1개층과 나머지 부분으로 이루어져있다고 가정
- 이 관점에서 재귀적으로 탑을 이동시킴
"""
def move(num: int, start: int, target: int) -> None:
if num > 1:
move(num-1, start, 6-start-target)
print(f"원반 {num}을(를) {start}에서 {target}으로 옮깁니다.")
if num > 1:
move(num-1, 6-start-target, target)
n = int(input("하노이의 탑 층수를 입력해주세요: "))
move(n, 1, 3)
# 실행결과 ==========================================
하노이의 탑 층수를 입력해주세요: 4
원반 1을(를) 1에서 2으로 옮깁니다.
원반 2을(를) 1에서 3으로 옮깁니다.
원반 1을(를) 2에서 3으로 옮깁니다.
원반 3을(를) 1에서 2으로 옮깁니다.
원반 1을(를) 3에서 1으로 옮깁니다.
원반 2을(를) 3에서 2으로 옮깁니다.
원반 1을(를) 1에서 2으로 옮깁니다.
원반 4을(를) 1에서 3으로 옮깁니다.
원반 1을(를) 2에서 3으로 옮깁니다.
원반 2을(를) 2에서 1으로 옮깁니다.
원반 1을(를) 3에서 1으로 옮깁니다.
원반 3을(를) 2에서 3으로 옮깁니다.
원반 1을(를) 1에서 2으로 옮깁니다.
원반 2을(를) 1에서 3으로 옮깁니다.
원반 1을(를) 2에서 3으로 옮깁니다.8퀸 문제
"""
아이디어
배열에 퀸의 위치를 저장하고 분기 조건을 따져가며 알고리즘 전개
열/행/대각선 중복여부를 따져 분기한정법 진행
"""
row_positions = [0] * 8
column_checker = [0] * 8
diagonal_checker_1 = [0] * 15
diagonal_checker_2 = [0] * 15
def set(i: int) -> None:
for j in range(8):
if not column_checker[j] \
and not diagonal_checker_1[i+j] \
and not diagonal_checker_2[i-j + 7]:
row_positions[i] = j
if i == 7:
for y in range(8):
for x in range(8):
print('■' if row_positions[x] == y else '□', end='')
print()
print()
else:
column_checker[j] = diagonal_checker_1[i+j] = diagonal_checker_2[i-j + 7] = 1
set(i+1)
column_checker[j] = diagonal_checker_1[i+j] = diagonal_checker_2[i-j + 7] = 0
set(0)
# 실행결과 ==========================================
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□□□□□■
□□□□□■□□
□□□■□□□□
■□□□□□□□
□□□□■□□□
□□□□□■□□
□□□■□□□□
□■□□□□□□
□□□□□□□■
□□□□■□□□
□□□□□□■□
■□□□□□□□
□□■□□□□□
□□□□□■□□
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□■□□□□
□□□□□□□■
■□□□□□□□
□□□□■□□□
□□□□□■□□
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□□□□□■
□□□□■□□□
■□□□□□□□
□□□■□□□□
□□□■□□□□
□□□□□□■□
□□■□□□□□
□□□□□□□■
□■□□□□□□
□□□□■□□□
■□□□□□□□
□□□□□■□□
□□□■□□□□
□■□□□□□□
□□□□□□■□
□□■□□□□□
□□□□□■□□
□□□□□□□■
□□□□■□□□
■□□□□□□□
.
.
.정리
기껏해야 몇주 남짓이지만
CS공부를 시작한 이래로 가장 흥미로웠다.
현실과 동떨어져있다고 느끼기 쉬운
자료구조, 알고리즘 등의 따분한 개념이
외려 현실의 문제를 너무도 간단하게
해결하고 있었기 때문이다.
특히 이 재귀 파트가 더 흥미로웠던 이유는
분기의 수가 사람이 예측할 수 있는 범주를
벗어나있기 때문이지 않나 싶다.
하노이의 탑에서, 누구나 3개~4개의
탑 정도는 그 해법을 쉽게 예상할 수 있겠지만,
그 이상부터는 복잡해 한번에 해결하기 어렵다.
그 복잡성을 간단한 아이디어(층을 묶는다는 개념)와
재귀를 적용한 몇줄의 코드로 풀어내다니..
좀 이상해 보일 수 있겠지만 '아름답다'고 느낄 정도였다.
'8퀸 문제'의 해법은 솔직히 아직도 확실하게
이해하지는 못했다.. 몇 번 정도는 더 읽어보고
내 것으로 만든 뒤, 다른 문제에도
재귀의 개념을 활용한 알고리즘을 써보고 싶다.
