[알고리즘] 문제3 - 재귀 함수

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다.

 

재귀 함수(Recursive Function) : 자기 자신을 호출하는 함수

재귀적으로 문제를 푼다는 것 : 부분 문제(같은 형태의 더 작은 문제)의 답을 이용해서 기존 문제를 푸는 것

---

 

 1. 피보나치 수열 구현하기 

 

 조건 

-함수명 : fib

-매개변수명 : 받을 자연수(n)

-10번째 항까지 출력하기

---

풀이

# 시간 복잡도 : O(2^n)

def fib(n):
    # base case
    if n < 3:
        return 1

    # recursive case
    return fib(n-1) + fib(n-2)


# 테스트
for i in range(1, 11):
    print(fib(i))

 

 

---

 

 2. 숫자 합 구하기

 

 조건 

-함수명 : triangle_number

-매개변수명 : 받을 자연수(n)

-1부터 n까지의 합을 리턴해주는 재귀함수 구현하기

-1부터 10까지 합을 출력하기 

---

풀이

# 시간 복잡도 : O(n)

def triangel_number(n):
    # base case
    if n == 1:
        return 1

    # recursive case
    return n + triangel_number(n-1)


# 테스트
for i in range(1, 11):
    print(triangel_number(i))

 

 

---

 

 3. 자릿수 합 구하기 

 

 조건 

-함수명 : sum_digits

-매개변수명 : 받을 자연수(n)

-n의 각 자릿수의 합을 리턴해주기

---

풀이

# 시간 복잡도 : O(d) (d는 n의 자릿수)

def sum_digits(n):
    # base case
    if n < 10:
        return n

    # recursive case
    return (n % 10) + sum_digits(n // 10)


# 테스트
print(sum_digits(22541))
print(sum_digits(92130))
print(sum_digits(12634))
print(sum_digits(704))
print(sum_digits(3755))

 

---

 

 4. 리스트 뒤집기 

 

 조건 

-함수명 : flip

-매개변수명 : 받을 리스트(some_list)

---

풀이

# 시간 복잡도 : O(n^2)

def flip(some_list):
    # base case
    if len(some_list) <= 1:
        return some_list

    # recursive case
    return some_list[-1:] + flip(some_list[:-1])


# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(list(flip(some_list)))

 

'''
더 알아보기
'''

# 리스트의 덧셈 연산 + 슬라이싱 사용
return some_list[-1:] + flip(some_list[:-1])

# 리스트의 덧셈 연산
a = [1]
b = [2]
print(a+b) # 출력 결과 : [1,2]

# 리스트의 슬라이싱
# -1은 역순으로
# [-1:]은 역순의 첫번째(마지막요소)부터 끝까지
# [:-1]은 처음부터 역순의 첫번째(마지막요소)까지
some_list = [1, 2, 3, 4, 5]
print(some_list[-1:]) # 출력 결과 : [5]
print(some_list[:-1]) # 출력 결과 : [1, 2, 3, 4]

 

---

 

 5. 재귀 함수로 이진 탐색 구현하기 

 

 조건 

-함수명 : binary_search

-매개변수명 : 탐색할 값(element), 받을 리스트(some_list), 시작 번호(start_index), 마지막 번호(end_index)

-시작번호는 0, 마지막번호는 None으로 매개변수 지정하기

-end_index가 None일 경우, 리스트의 인덱스 마지막 번호로 지정하기

---

풀이

# 시간 복잡도 : O(log n)

def binary_search(element, some_list, start_index=0, end_index=None):

    if end_index == None:
        end_index = len(some_list)-1

    # base case
    if start_index > end_index:
        return None

    index = (start_index + end_index) // 2

    # recursive case
    if element == some_list[index]:
        return index
    elif element < some_list[index]:
        return binary_search(element, some_list, start_index, index-1)
    else:
        return binary_search(element, some_list, index+1, end_index)


# 테스트
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

 

---

 

 6. 하노이의 탑 구현하기

 

 조건 

1. 해답을 출력해주는 함수 구현

-함수명 : hanoi

-매개변수명 : 원판 수(num_disks), 게임을 시작하는 기둥 번호(start_peg), 목표로 하는 기둥 번호(end_peg)

 

2. 이동 경로를 출력해주는 함수 구현

-함수명 : move_disk

-매개변수명 : 이동한 원판 번호(disk_num), 처음 위치(start_peg), 이동한 위치(end_peg)

---

풀이

# 시간 복잡도 : O(2^n)

def move_disk(disk_num, start_peg, end_peg):
    print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk_num, start_peg, end_peg))


def hanoi(num_disks, start_peg, end_peg):

    # base case
    if num_disks == 0:
        return 0

    # recursive case
    else:

        # 0. 나머지 기둥 계산 (첫번째 기둥(1)+두번째 기둥(2)+세번째 기둥(3)=6)
        other_peg = 6 - start_peg - end_peg

        # 1. 가장 큰 원판을 제외하고 나머지 원판들을 시작 기둥에서 나머지 기둥으로 이동
        hanoi(num_disks-1, start_peg, other_peg)
        
        # 2. 가장 큰 원판을 시작 기둥에서 목표 기둥으로 이동
        move_disk(num_disks, start_peg, end_peg)

        # 3. 나머지 원판들을 나머지 기둥에서 목표 기둥으로 이동
        hanoi(num_disks-1, other_peg, end_peg)


# 테스트
hanoi(3, 1, 3)