지난 시간에는 재귀 함수의 간단한 예제들을 함께 봤습니다. 이번 시간에는 난이도를 좀 더 높여 다양한 재귀 함수의 예제들을 추가적으로 만나보도록 합시다.
👩👩👧👦 리스트 뒤집기
flip은 파라미터로 리스트 my_list를 받고, 뒤집힌 리스트를 리턴해주는 재귀 함수입니다. 반복문 사용 없이 재귀 호출 개념을 이용하여 함수를 작성해봅시다.
먼저, base case부터 생각해보죠. 리스트를 뒤집는 과정 중, 바로 답을 구할 수 있는 경우는 무엇일까요? 바로 리스트의 요소가 딱 하나만 있을 때입니다. 리스트의 요소가 딱 하나라면 그 리스트를 그냥 반환하면 되니까요. 이를 코드로 구현해봅시다.
if len(my_list) == 1:
return my_list다음으로 recursive case를 구해봅시다. 이전 챕터에서 접한 간단한 재귀 함수 사례들은 대부분 연산을 활용해서 만들어졌었죠? 그래서 일반화된 수식이 recursive case를 일반화한 것과 같았고 따라서 재귀 호출 부분에 이 내용이 들어갔습니다.
리스트의 경우는 조금 다릅니다. 수식으로 일반화할 수 있는 개념이 아니기 때문이죠. 이런 경우에는 예시를 떠올리고 그 안에서 반복되는 과정을 찾아 부분 문제로 정의하는 방향으로 recursive case를 정의하면 되겠습니다.
my_list가 [1, 2, 3, 4]인 경우를 예로 들어보겠습니다. base case 즉, 요소가 1인 상태에서 [1, 2, 3, 4]가 되려면 재귀 호출을 거침에 따라 요소가 하나씩 늘어야겠죠? 따라서 이 경우를 [1, 2, 3]과 [4]로 분리해서 생각해볼 수 있습니다.
쉽게 생각하면 [1, 2, 3]을 먼저 뒤집고 그 앞에 [4]를 붙여주면 우리가 원하는 결과가 나옵니다. 그런데 [1, 2, 3]을 뒤집는 건 flip([1, 2, 3])과 동일합니다. 따라서, flip([1, 2, 3])은 재귀 함수의 부분 문제가 될 수 있죠.
이제 이를 일반화 해봅시다. 수식은 아니지만 리스트를 뒤에서부터 가져오고 리스트의 끝을 구하는 등의 과정 또한 일반화된 형태로 나타낼 수 있습니다.
먼저, [1, 2, 3]과 [4] 중에 [1, 2, 3]을 리스트 슬라이싱으로 표현해볼 수 있습니다. my_list[:-1]로 말이죠. 이는 마지막 수를 제외하고 리스트의 요소를 불러오는 방법입니다.
그럼 [4]는 어떻게 일반화할 수 있을까요? 거꾸로 my_list[-1:]을 하면 됩니다. 이렇게 하면 리스트의 끝 요소만 불러올 수 있기 때문이죠.
이제 이 두 슬라이싱 결과를 붙이기만 하면 됩니다. 그럼 recursive case를 다음과 같은 코드로 나타낼 수 있죠.
return flip(my_list[:-1]) + my_list[-1:] 전체 코드와 문제 풀이 예시를 봅시다.
def flip(my_list):
if len(my_list) == 1:
return my_list
return flip(my_list[:-1]) + my_list[-1:]my_list = [2, 4, 6, 8, 10]
my_list = flip(my_list)
print(my_list)[10, 8, 6, 4, 2]❗ 시간 복잡도
리스트 my_list의 길이를 n이라고 합시다. 재귀 부분을 제외한 부분만 우선 평가해보도록 하죠.
먼저, base case 부분은 O(1)입니다.
recursive case 부분은 재귀적 호출 부분을 제외하면 my_list[-1:]과 my_list[:-1] 부분으로 나눌 수 있죠? 전자의 경우 O(1)이지만 리스트의 요소가 늘어나는 후자의 경우는 O(n-1)입니다. 따라서, 재귀 부분을 제외한 flip 함수의 시간 복잡도는 O(n)이 되죠.
그렇다면 flip 함수는 총 몇 번 호출될까요? 매 호출 때마다 리스트의 길이가 1씩 줄어들기 때문에 flip 함수는 총 n번 실행된다고 볼 수 있습니다.
정리하자면 flip 함수는 재귀적으로 n번 실행되고 각 호출은 O(n)이기 때문에 결과적으로 총 시간 복잡도는 O(n^2)이 됩니다.
👩👩👧👦 이진 탐색
앞서 이진 탐색을 for 반복문을 통해 구현해 봤는데요. 이번에는 재귀 함수를 활용하여 구현해봅시다.
이진 탐색 알고리즘은 탐색을 이어갈 때마다 리스트의 길이가 반으로 줄었었죠? 따라서, 재귀 호출을 통해 구현이 가능합니다.
base case를 구하기 앞서 이진 탐색을 실행하는 재귀 함수 binary_search에 대해 설명해 드리겠습니다. 이 함수는 무려 4개의 파라미터가 필요한데요. 요소를 나타내는 element, 리스트를 나타내는 my_list, 그리고 첫 인덱스와 마지막 인덱스를 나타내는 start_index, end_index가 있습니다.
첫 인덱스와 마지막 인덱스는 각각 0과 None으로 초기화해 둔 상태로 함수를 작성해야 합니다. 그런 다음 만약 end_index가 따로 주어지지 않으면 리스트의 마지막 인덱스가 변수에 들어간다는 조건을 추가해줘야 합니다.
위 내용을 코드로 구현하면 다음과 같습니다.
def binary_search(element, my_list, start_index=0, end_index=None):
if end_index = None:
end_index = len(some_list) - 1이제 base case를 구하면 됩니다. 사실 이진 탐색에는 두 가지 base case가 존재합니다. 하나는 my_list 안에 element가 없다는 것이 확실한 경우이고 다른 하나는 my_list에서 찾으려는 element를 발견한 경우입니다.
전자의 경우에는 element를 my_list 안에서 찾지 못했다는 것을 알리기 위해 None을 리턴해야 하고 후자의 경우에는 즉시 탐색을 종료하고 element의 인덱스를 리턴하면 됩니다.
먼저, 첫 번째 base case를 구체적으로 생각해봅시다. my_list 안에 element가 없는 상황을 어떻게 표현할 수 있을까요?
탐색을 거듭하여 my_list의 길이가 점차 줄어들면서 1이 될 때를 가정해보죠. 만약 이러한 상황에도 찾으려는 값이 리스트에 없다면 어떻게 될까요? 또 다시 탐색 범위를 줄이면서 결국 start_index가 end_index보다 커지게 됩니다.
따라서, 리스트에 찾으려는 값이 없다는 것을 다음과 같이 표현할 수 있습니다.
if start_index > end_index:
return None이제 두 번째 경우를 봅시다. 이진 탐색에서 원하는 값을 찾는 경우는 언제였죠? 바로 원하는 값과 중간 값이 일치할 때였습니다. 이를 한 단계씩 코드로 구현해보도록 합시다.
제일 먼저 필요한 코드는 중간 인덱스 변수를 선언하는 것입니다. 중간 인덱스를 구하는 방법은 첫번째 인덱스와 마지막 인덱스의 합을 2로 나누면 됐었죠?
middle_index = (start_index + end_index) // 2그 다음 middle_index 값을 기준으로 여러 조건을 설정해줘야 하는데요. 필요한 세 가지 조건 중 base case에 해당하는 경우는 단 하나입니다. 지금은 해당 조건만 작성해봅시다.
middle_index 값이 element와 일치하면 원하는 값을 찾은 것이므로 탐색을 종료하고 middle_index를 리턴하면 됩니다.
if my_list[middle_index] == element:
return middle_index이제 recursive case를 생각해보면 됩니다. 이진 탐색에서 바로 구할 수 없는 커다란 문제는 뭐였죠? 이진 탐색 과정부터 다시 생각해보죠.
중간 값을 기준으로 찾는 값보다 중간 값이 작으면 중간 값의 오른쪽 반만 탐색하고 반대로 중간 값이 더 크면 중간 값의 왼쪽 반만 탐색합니다. 원하는 값을 찾을 때까지 이 과정은 반복됩니다.
파라미터가 여러 개라서 많이 헷갈릴 것입니다. 하지만 element와 my_list는 재귀적으로 호출되더라도 꼭 필요한 항목이므로 변하지 않습니다.
중요한 것은 start_index와 end_index인데요. 왼쪽 반만 탐색, 오른쪽 반만 탐색이라는 말을 자세히 생각해보면 index 값의 설정을 통해 구현이 가능하다는 걸 알 수 있습니다.
예컨대, 왼쪽 반만 필요하다면 start_index부터 middle_index를 제외한 범위 즉, 'middle_index - 1'이라는 파라미터가 필요할 것입니다.
elif my_list[middle_index] > element:
binary_search(element, my_list, start_index, middle_index - 1)오른쪽 반도 이와 마찬가지로 구하면 됩니다.
elif my_list[middle_index] < element:
binary_search(element, my_list, middle_index + 1, end_index)이제 전체 코드와 문제 풀이 예시를 봅시다.
def binary_search(element, my_list, start_index=0, end_index=None):
if end_index = None:
end_index = len(some_list) - 1
middle_index = (start_index + end_index) // 2
if my_list[middle_index] == element:
return middle_index
elif my_list[middle_index] > element:
binary_search(element, my_list, start_index, middle_index - 1)
elif my_list[middle_index] < element:
binary_search(element, my_list, middle_index + 1, end_index) print(binary_search(2, [2, 4, 6, 8, 10]))
print(binary_search(4, [2, 4, 6, 8, 10]))
print(binary_search(3, [2, 4, 6, 8, 10]))
print(binary_search(8, [2, 4, 6, 8, 10]))
print(binary_search(10, [2, 4, 6, 8, 10]))0
1
None
3
4❗ 시간 복잡도
이진 탐색의 시간 복잡도는 앞선 알고리즘 평가법 챕터에서 설명해드린 적이 있습니다. 따라서, 아주 간단하게만 짚고 넘어가겠습니다.
반복문에서와 마찬가지로 탐색 범위가 반씩 줄어들기 때문에 이진 탐색의 시간 복잡도는 O(lg(n))입니다.
이번 시간에는 연산을 활용한 재귀 함수보다는 좀 더 난이도 있는 사례들을 함께 봤습니다. 여기까지 잘 따라오셨나요?
다음 시간에는 재귀 함수의 마지막 문제, 하노이의 탑이 남아 있습니다. 지금까지 본 사례들보다 조금 더 복잡하지만 할 수 있습니다. 마지막 산을 넘고 재귀 함수를 정복해봅시다! 💪
* 이 자료는 CODEIT의 '알고리즘의 정석' 강의를 기반으로 작성되었습니다.