Python 50 - 재귀 호출 / 스택(stack) / 유클리드 호제법

재귀 호출

1. 자기 자신을 다시 호출하는 기능

2. 함수 안에서 자신의 함수를 호출하는 기능

3. 반복문 + stack 구조 (뒤로가기, undo, ctrl+z)

def sum(n):
      if n == 0:
          return 0
      return sum(n-1)+n # sum(n-1)에 대한 값은 모르니까 stack에 쌓아놓는다. 
print(sum(5)) 

출력값 : 15

돌아가는 방식(stack이 쌓이는 모습)

print(sum(1)) ----->   1          				1이 아래로 넘어감

print(sum(2)) ----->   1 + 2
								3이 아래로 넘어감
print(sum(3)) ----->   3 + 3
								6이 아래로 넘어감
print(sum(4)) ----->   6 + 4
								10이 아래로 넘어감
print(sum(5)) ----->   10 + 5

print(sum(10)) ------>  55 출력

 

stack

한쪽 끝에서만 자료를 넣거나 뺄수있는 구조

바닥부터 데이터를 차곡차곡 쌓는 구조

LIFO(Last In First Out) : 후입선출, 마지막으로 들어온 데이터가 제일 먼저 나간다.

FILO(First In Last Out) : 선입후출, 처음에 들어온 데이터가 제일 마지막에 나간다.

 

stack 구조 용어

push : 마지막 데이터 위치에 데이터를 입력한다.

pop :  마지막 데이터 위치에 데이터를 꺼내는 작업(삭제)

top : 제일 최근에 들어간 데이터 즉 가장 위에 있는 데이터의 위치

 

push 함수 만들기 :

stack = []
def push(n) :
    global stack
    stack.append(n)

push(1)
push(2)
push(3)

print(stack)  출력값 : [1,2,3]

pop 함수 만들기 :    

def pop() :
     global stack
     if len(stack) == 0:
         return None
     return stack.pop()

pop()
print(stack)   출력값 : [1, 2]

재귀 호출을 사용한 유클리드 호제법

유클리드 호제법

2개의 자연수로 최대공약수를 구하는 알고리즘

호제법 : 두 수가 상대방 수를 나누어 우너하는 수를 얻는 알고리즘

이미지 출처 : https://www.inchcalculator.com/euclidean-algorithm-calculator/

최대 공약수 구하기 (유클리드 호제법 X)

def gcd(x,y):
    # x, y의 약수 구하기
    a = []
    b = []
    for i in range(1, int(x/2)+1):
        if x % i == 0:
            a.append(i)
    a.append(x) # a = x의 약수들 
    for i in range(1, int(y/2)+1):
        if y % i == 0:
            b.append(i)
    b.append(y) # b = y의 약수들
    
    # a, b의 교집합 구하기
    c = []
    for i in a:
        if i in b:
            c.append(i)
    
    # c의 max값 구하기
    c.sort()
    return c[-1]

print(gcd(100,50))   출력값 : 50

 

최대 공약수 구하기 (유클리드 호제법 O)

def gcd(x,y):
    if x < y :    
        x,y = y,x  # x와 y 스위칭
    elif x > y :
        while y != 0:
            x = y
            y = x%y
    else :
        return x
    return x
print(gcd(100,50))   출력값 : 50

최대 공약수 구하기 (유클리드 호제법 O + 재귀 호출)

def gcd(x,y):
    if y == 0:
        return x
    return gcd(y, x%y)
print(gcd(100,50))   출력값 : 50

*최대공약수 구하기 코드 비교*

유클리드 호제법 X	유클리드 호제법 O	유클리드 호제법 O + 재귀 호출

30줄의 코드가 6줄로 더욱 간소화된다.

 

 

 

 

 

 

작성자 : 엄코딩 eomcoding

 

파이썬 알고리즘 유클리드호제법 재귀호출 스택

python stack coding programming def codingtest