python 자료구조 1.2 순환 알고리즘을 통한 시간 복잡도 분석

순환 알고리즘

• 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
• 정의 자체가 순환적으로 되어 있는 경우에 적합

재귀 호출 작동 방식의 이해

숫자 합계 내기

# 반복문 구현

# 숫자 합계 내기

sumvalue = 0
for i in range(10,0,-1):
    sumvalue += i

print(sumvalue)
# 55 출력

# 재귀 함수를 이용한 구현

def addnumber(num):
    if num <= 1:
        return 1
    return num + addnumber(num-1)

print(addnumber(10))
# 55 출력

# 참고 코드
def addnumbers(start, end):
    if start > end:
        start, end = end, start

    if start== end:
        return start

    return start + addnumbers(start+1, end)

start= int(input("시작 숫자를 입력하세요: "))
end= int(input("끝 숫자를 입력하세요: "))

result = addnumbers(start, end)
print(result)

팩토리얼 구하기

# 재귀 호출을 통해 팩토리얼 구하기
def factorial(num):
    if num <= 1:
        return num
    
    else:
        return num * factorial(num-1)

print(factorial(10))

피보나치 수열

# 피보나치 수열

def fib(n):
    if n == 0 :
        return 0
    elif n == 1:
        return 1
    
    else:
        return fib(n-1) + fib(n-2)

# 우주선 발사 카운트 다운

def countDown(n):
    if n == 0:
        print('발사')
    
    else:
        print(n)
        countDown(n-1)

countDown(8)

# 별 모양 출력을 재귀함수로 구현
def printstar(n):
    if n == 1:
        print('*')
    else:
        printstar(n-1)
        print('*' * n)
printstar(6)

# 구구단 출력을 재귀함수로 구현

def gugu(dan,num):
    print('%d x %d = %d' %(dan,num, dan*num))
    
    if num < 9 :
        gugu(dan,num+1)

for dan in range(2,10):
    print('### %d단 ###' %dan)
    gugu(dan,1)

# 회문 판단하기

def palindrome(pStr):
    if len(pStr) <= 1:
        return True
    
    if pStr[0] != pStr[-1]:
        return False
    
    return palindrome(pStr[1:len(pStr)-1])

palindrome('주유소의소유주')

재귀함수 구현이 정말 쉬울 때도 있지만, 시간 복잡도 계산이 중요한 점은 항상 인지하고 있어야한다.

코딩테스트 합격을 위한 그날까지!