재귀 함수 연습 - 2

guava·2021년 9월 24일

알고리즘 코드잇

알고리즘의 정석

목록 보기

7/13

코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.

이전 글에 이어서 재귀 함수를 연습하도록 하겠다. 마찬가지로 아래 두가지 요소를 도출해보며 문제를 풀어나가도록 한다.

재귀 함수의 두가지 요소

Recursive case: 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우
Base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우

리스트 뒤집기

문제

파라미터로 리스트 some_list를 받고, 뒤집힌 리스트를 리턴해주는 재귀 함수 flip을 작성하라.
반복문을 사용해서는 안된다.

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    d = len(some_list)
    if d <= 1:
        return some_list
    return some_list[-1:] + flip(some_list[:-1])

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

# 콘솔 출력
[9, 8, 7, 6, 5, 4, 3, 2, 1]

풀이

리스트의 길이를 d라고 하자.
먼저 base case를 생각해보자.
d=1일 때는 뒤집혀도 동일한 값을 반환하므로 언제나 flip(some_list)=some_list이다.

이제 recursive case를 생각해보자.
만약 d=5인 리스트 [1, 2, 3, 4, 5]를 뒤집는다고 하자. 이 때 [1, 2, 3, 4]와 [5]로 리스트를 쪼개고 [5]와 [1, 2, 3, 4]를 뒤집은 리스트를 합쳐서 반환하면 된다. 이 때 [1, 2, 3, 4]를 뒤집는 부분 문제가 발생하며, 이를 재귀적으로 해결하면 된다.

코드

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    d = len(some_list)
    if d <= 1: # base case
        return some_list
    # recursive case
    return some_list[-1:] + flip(some_list[:-1])

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

# 콘솔 출력
[9, 8, 7, 6, 5, 4, 3, 2, 1]

이진 탐색 재귀로 구현해보기

문제

이진 탐색 알고리즘을 재귀 함수로 구현하라.


def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    # 코드를 작성하세요.

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]))

# 콘솔 출력
0
None
2
1
4

풀이

먼저 base case를 생각해보자.
base case는 두가지로 생각해볼 수 있다.
1. 찾고자 하는 엘리먼트가 존재하지 않을 경우에 None을 반환한다.
2. 엘리먼트를 찾았을 경우 해당 인덱스를 반환한다.
첫번째로 존재하지 않을 경우는 여러번 이진 탐색이 반복되고 start_index<end_index일 때에는 값이 존재하지 않다고 판단할 수 있다.
두번째로 엘리먼트를 찾았을 경우에는 인덱스를 반환한다. start_index와 end_index를 기준으로 중간값이 엘리먼트와 같을 경우가 된다.

코드


def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1
    mid = (start_index + end_index + 1) // 2
    if start_index > end_index:
        return None
    if some_list[mid] == element:
        return mid
    if some_list[mid] > element:
        end_index = mid - 1
    elif some_list[mid] < element:
        start_index = mid + 1
    return binary_search(element, some_list, start_index, 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]))

# 콘솔 출력
0
None
2
1
4

하노이의 탑

문제

하노이의 탑 해답을 출력해주는 함수 hanoi를 작성하라. hanoi는 파라미터로 원판 수(num_disks), 게임 시작 기둥 번호(start_peg), 목표 기둥 번호(end_peg)를 입력받는다. 재귀적으로 풀어서 원판을 옮기는 순서를 모두 출력하라.

하노이의 탑 규칙

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안된다.

이 게임의 목표는 왼쪽 기둥에 있는 원판을 모두 오른쪽 기둥으로 옮기는 것이다.

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):
    # 코드를 입력하세요.

# 테스트 코드 (포함하여 제출해주세요)
hanoi(3, 1, 3)

# 콘솔 출력
1번 원판을 1번 기둥에서 3번 기둥으로 이동
2번 원판을 1번 기둥에서 2번 기둥으로 이동
1번 원판을 3번 기둥에서 2번 기둥으로 이동
3번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 1번 기둥으로 이동
2번 원판을 2번 기둥에서 3번 기둥으로 이동
1번 원판을 1번 기둥에서 3번 기둥으로 이동

풀이

base case를 찾아라.

원판의 개수가 0개일 때이다. 아무것도 할 필요가 없다.

if num_disks == 0:
    return

recursive case를 찾아라.

원판이 하나일 때 - 부분문제1

1번 기둥에서 3번 기둥으로 원판을 옮긴다.
(start_peg에서 end_peg로 원반을 옮긴다.)

if num_disks == 1:
    move_disk(num_disks, start_peg, end_peg)

원반이 두개일 때 - 부분문제2

1번 원반을 1번기둥에서 2번기둥으로 옮긴다.
(start_peg에서 other_peg로 원반을 옮긴다.)
2번 원반을 1번기둥에서 3번기둥으로 옮긴다.
(start_peg에서 end_peg로 원반을 옮긴다.)
1번 원반을 2번기둥에서 3번기둥으로 옮긴다.
(other_peg에서 end_peg로 원반을 옮긴다.)

1, 2, 3 모두 원판이 하나일 때 부분문제1과 같다.

if num_disks == 2:
    other_peg = 6 - start_peg - end_peg
    # 원반1를 기둥1에서 기둥2로 옮긴다.
    hanoi(num_disks-1, start_peg, other_peg)  # num_disks-1=1이므로 부분문제1을 푸는걸로 볼 수 있다.
    # 원반2를 기둥1에서 기둥3으로 옮긴다.
    move_disk(num_disks, start_peg, end_peg)
    # 원판1을 기둥2에서 기둥3으로 옮긴다.
    hanoi(num_disks-1, start_peg, other_peg)  # num_disks-1=1이므로 부분문제1을 푸는걸로 볼 수 있다.

원반이 세개일 때

가장 큰 원반(3번 원반)을 제외하고 나머지 원판(1, 2번 원반)들을 1번 기둥에서 2번 기둥으로 옮긴다.
(start_peg에서 other_peg로 원반을 옮긴다.)
가장 큰 원반(3번 원반)을 1번기둥에서 3번기둥으로 옮긴다.
(start_peg에서 end_peg로 원반을 옮긴다.)
가장 큰 원반을 제외한 나머지 원반(1, 2번 원반)들을 2번기둥에서 3번기둥으로 옮긴다.
(other_peg에서 end_peg로 원반을 옮긴다.)

1, 3번 모두 두개의 원반을 옮겼다. 원반이 두개일 때 부분문제2와 같다고 볼 수 있다.

if num_disks == 3:
    other_peg = 6 - start_peg - end_peg
    # 가장 큰 원반을 제외한 나머지 원반을 기둥1에서 기둥2로 옮긴다.
    hanoi(num_disks-1, start_peg, other_peg)  # num_disks-1=2이므로 부분문제2를 푸는걸로 볼 수 있다.
    # 가장 큰 원반인 원반3을 기둥1에서 기둥3으로 옮긴다.
    move_disk(num_disks, start_peg, end_peg)
    # 가장 큰 원반을 제외한 나머지 원반을 기둥2에서 기둥3으로 옮긴다.
    hanoi(num_disks-1, start_peg, other_peg)  # num_disks-1=2이므로 부분문제2를 푸는걸로 볼 수 있다.

이후로 반복해서 따져보면 풀이 방법이 원반이 세개일 때와 동일하다.
작성된 코드를 확인해보면 원반이 두개일 때와 세개일 때의 코드는 동일함을 알 수 있다. 또한 설명을 위해 원반이 하나일 때에도 별도로 작성하였지만 사실 원반이 더 많을때와 동일하게 작성하여도 된다.(base case가 작성되어 있어야 한다.) 따라서 재귀적인 코드 작성이 가능하다. 전체 코드를 확인해보자.

코드

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
    # recursive case
    other_peg = 6 - start_peg - end_peg
    hanoi(num_disks-1, start_peg, other_peg)
    move_disk(num_disks, start_peg, end_peg)
    hanoi(num_disks-1, other_peg, end_peg)
    

# 테스트 코드 (포함하여 제출해주세요)
hanoi(3, 1, 3)

# 콘솔 출력
1번 원판을 1번 기둥에서 3번 기둥으로 이동
2번 원판을 1번 기둥에서 2번 기둥으로 이동
1번 원판을 3번 기둥에서 2번 기둥으로 이동
3번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 1번 기둥으로 이동
2번 원판을 2번 기둥에서 3번 기둥으로 이동
1번 원판을 1번 기둥에서 3번 기둥으로 이동

guava

이전 포스트

재귀 함수 연습 - 1

다음 포스트