유클리드 호제법과 재귀함수 : 백준 2609[최대공약수와 최소공배수] & 파이썬

오늘 재귀 함수를 공부하면서 전에 풀었던 백준 문제가 생각이 나서 같이 정리해보고자 가지고 왔다.

🔍 재귀함수(Recursion Function)

출처 : 재귀함수 위키피디아

재귀함수를 나타내는 gif

• 쉽게 말하면, 자기 자신을 호출하는 함수.
• 자세한 설명은 재귀함수 위키피디아 참고
• 수학적 귀납법과 비슷함
• 실체하지 않는 개념을 수학적 모델로 만들고, 그 수학적 모델을 하나씩 차감시켜가면서 호출하는 것만으로도 문제가 해결되게 하는 것

1 ) 재귀함수의 활용

• 재귀적으로 문제를 푼다는 것 : 같은 형태의 더 작은 문제^[각주:1]를 풀고, 부분 문제의 답을 이용해서 기존 문제를 푸는 것!
• 재귀적으로 풀기 위해서는 항상 아래와 같이 두 case를 나누어서 생각해야한다.
  1. Base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우
  2. Recursive case: 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우
• 예제 : 팩토리얼 문제

'''[팩토리얼]'''
# 재귀적 풀이
def factorial(n):
	# base case
    if n == 0:
        return 1
    # recursive case
    return factorial(n - 1) * n

print(factorial(3))

# 반복문 풀이
def factorial_loop(n):
    result = 1
    for i in range(1, n + 1):
        # print(i) # 1, 2, 3
        result *= i
    return result

print(factorial_loop(3))

  

위의 재귀함수 그림으로 이해하기

 

  

메모리값과 같이 보면서 느껴보기

2) 재귀함수 vs 반복문

위의 팩토리얼 예제에서도 알 수 있듯, 대부분의 재귀함수는 반복문(iteration, loop)과 변수를 이용하는 반복적 알고리즘으로 구현이 가능하고 그 역도 성립한다.

• 반복문은 코드에서 대놓고 '이 블록은 반복될 것임'하고 알려주는 것과 다르게 재귀는 별다른 표시 없이 혼자 돌게 되므로 코드 내에서 가독성이 떨어지고 흐름을 추적하기 어렵다.
• 재귀적으로 너무 많은 함수 호출이 있는 알고리즘(Call Stack^[각주:2]이 많이 쌓여 오류가 나는 알고리즘)일 것 같은 경우에는 과부하로 프로그램이 중단 될 수 있다.(stack overflow) 이러한 경우에는 반복문을 사용하는 것을 권장!
• 재귀함수 설계 시, 입력값이 종료 조건으로 수렴하는지를 꼭 검증해야 한다.
• 그럼에도 불구하고 재귀함수를 배워야 하는 이유는 단순히 기계적인 최적화 수준의 이야기를 넘어서, 알고리즘적 측면에서 보자면 재귀적 사고방식을 평소에 연습하는 것이 매우 중요하기 때문! 재귀적 사고 방식은 흔히 말하는 분할정복에 기초를 둔다.
• 어떤 리스트의 합을 구하는 경우를 생각해보자. 단순히 명령형 사고에 익숙해졌다면 이를 $O(n)$으로 구하고, 그 답에 만족했을 것이다. 하지만 이 문제는 재귀적으로 생각할 경우 $O(log n)$만에 해결할 수 있다. 이처럼 기계적 수준의 최적화가 아니라, 더 높은 수준의 생산성과 효율을 추구한다면 평소에 재귀적으로 사고하는 습관을 들여야 한다! 💪

3) Call Stack 1000개(기본 값) 이상으로 늘리는 방법

sys 라이브러리를 통해 현재 한계를 출력해서 확인이 가능하고, 값을 수정할 수도 있다. 🥕👍

import sys

# 기본 값 : 1000
print(sys.getrecursionlimit())

# 한계 늘리기
sys.setrecursionlimit(3000)

# 늘려진 한계 확인 : 3000
print(sys.getrecursionlimit())

---

🔍 유클리드 호제법(Euclidean algorithm)

• 2개의 자연수 또는 정식^[각주:3]의 최대공약수(GCD)를 구하는 알고리즘의 하나
• 호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 알고리즘을 말한다.
• 유클리드 호제법은 나눗셈만 반복해서 최대공약수를 구할 수 있다.
• 두 수가 아무리 커도 정해진 순서로 계산하면 효율적으로 최대공약수를 구할 수 있다.
• 방법 : 2개의 자연수 $x, y$에 대해서 $x$를 $y$로 나눈 나머지를 $r$이라고 하면, $x$와 $y$의 최대공약수는 $y$와 $r$의 최대공약수와 같다. 이 성질에 따라, $y$를 $r$로 나눈 나머지 $r'$를 구하고 다시 $r$을 $r'$로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 $x$와 $y$의 최대공약수이다.
• 예시를 보면 이해가 빠르다.
  • 19와 7의 최대공약수를 구해보자
  • 19와 7의 최대공약수는 7와 5의 최대공약수와 같다. 이 성질에 따라, 7를 5로 나눈 나머지 2를 구하고 다시 5을 2로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수인 1이 19와 7의 최대공약수이다.

19 = 7x2 + 5
7 = 5x1 + 2
5 = 2x2 + 1
2 = 1X2 + 0

---

백준 2609 [최대공약수와 최소공배수]

📎 Problem

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

📎 Note

• 공약수 : 두 수 사이에서 공통으로 존재하는 약수
• 최대공약수(GCD, Greate Common Divisor) : 공약수 중에 가장 큰 공약수
• 공배수 : 두 수의 공통적인 배수
• 최소공배수(LCM, Least Common Multiple) : 공배수 중에 제일 작은 공배수

'''
💻 code
1. gcd(a, b)
    계속해서 a를 b로 나누어서 b를 a에 나눈 나머지 b를 대입시켜서 b가 0이 될때까지 반복하면
    남는 a의 값이 최대공약수가 된다

def gcd(a, b):
    while b > 0:
    a, b = b, a % b
return a


2. lcm(a, b)
    a, b의 곱을 a, b의 최대공약수로 나눈 값이다.(몫 : //)

gcd * lcm= num1 * num2


def lcm(a, b):
    return a * b // gcd(a, b)
'''

📎 Submission Code

# case 1 : 이미 구현이 되어있는 math 모듈을 임포트해서 사용할 수 있다.
import math

num1, num2 = map(int, input().split())

print(math.gcd(num1, num2))
print(math.lcm(num1, num2))

# case 2 : 유클리드 호제법
num1, num2 = map(int, input().split())

def gcd(num1, num2):
    while num2 > 0:
        num1, num2 = num2, num1 % num2
    return num1

def lcm(num1, num2):
    return num1 * num2 // gcd(num1, num2)

print(gcd(num1, num2))
print(lcm(num1, num2))

📎 재귀함수와 최소공약수

def factor(num1, num2):
    # 유클리드 호제법
    remain = num1 % num2
    # check
    print(f"num1: {num1}, num2: {num2}, 나머지 : {remain}")

    # base case
    if remain == 0:
        return num2

    # recursive case
    return factor(num2, remain)
    
'''
출력 : 
num1: 7, num2: 19, 나머지 : 7
num1: 19, num2: 7, 나머지 : 5
num1: 7, num2: 5, 나머지 : 2
num1: 5, num2: 2, 나머지 : 1
num1: 2, num2: 1, 나머지 : 0
1
'''

---

📎 Reference

• 재귀함수 나무위키
• 유클리드 호제법 위키백과
• 파이썬 메모리 시각화하면서 코딩 가능한 사이트
• 재귀함수 심슨 gif 출처
• 코드잇 알고리즘의 정석 강의

 

 

 

 

1. (= 부분 문제, Subproblem) [본문으로]
2. 콜 스택 이란 컴퓨터 프로그램에서 현재 실행 중인 서브루틴에 관한 정보를 저장하는 스택 자료구조이다. [본문으로]
3. 《수학》 문자가 든 식으로, 더하기, 빼기, 곱하기에 한하고, 나누는 일이 없는 유리식.  [본문으로]