from codeit
리스트 뒤집기
파라미터로 리스트 some_list를 받고,
뒤집힌 리스트를 리턴해 주는 재귀 함수 flip을 쓰세요.
# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
# 코드를 입력하세요.
# 테스트
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]
내 풀이
베이스 케이스는 리스트에 1개만 남았을 때,(1개는 뒤집어도 같은순서)
리컬시브 케이스는 부분문제를 풀어야 하는, 리스트에 요소가 1개 이상 남아있을 때로 나눔
부분 문제는
def flip(some_list):
if len(some_list) <= 1:
return some_list
return [some_list[-1]] + flip(some_list[0:-1]) 재귀함수가 구현될 때, 한번 씩 함수에 넣어준 뒤, 리턴 되는 값이 모여서 최종 결과값이 나오는 과정이 아직 헷갈림.
과정을 하나씩 보여주는 파이썬 튜터의 도움을 받음
1) flip(some_list[0:-1])
2) 베이스 케이스까지 도달. (== 리스트에 요소 한개 남음) some_list 리스트 자체를 리턴해줌.
3) some_list[-1]이 앞에서 부터 더해지기 시작함
해답
some_list의 길이가 0이거나 1인 경우에는 바로 답을 알고 리턴했지만, some_list의 길이가 1보다 큰 경우에는 바로 답을 알지 못하기 때문에 부분 문제를 풀어야 합니다.
예를 들어 some_list가 [1, 2, 3, 4, 5]인 경우를 생각해 봅시다. [1, 2, 3, 4, 5]를 뒤집기 위해서 우리가 풀어야 할 부분 문제는 무엇일까요?
우선 [1, 2, 3, 4, 5]를 두 리스트 [1, 2, 3, 4]와 [5]로 분리시켜봅시다. 여기서 [1, 2, 3, 4]를 뒤집고, 그것의 결과물 앞에 [5]를 붙이면 되겠죠? 그런데 [1, 2, 3, 4]를 뒤집는 문제는 뭔가 익숙한 형태입니다.
[1, 2, 3, 4]를 뒤집는 것은 바로 flip([1, 2, 3, 4])입니다. 바로 우리가 찾던 같은 형태의 더 작은 "부분 문제"인 거죠.
[5] 와 flip([1, 2, 3, 4])를 합쳐서 리턴해 주면 되는데요. 이것을 일반화하면 some_list[-1:]과 flip(some_list[:-1])을 더하는 것입니다.
def flip(some_list):
# base case
if len(some_list) == 0 or len(some_list) == 1:
return some_list
# recursive case
return some_list[-1:] + flip(some_list[:-1])시간복잡도
리스트 some_list의 길이를 n이라고 합시다.
일단 재귀 부분을 제외한 부분부터 평가해 봅시다.
우선 base case 부분은 그냥 O(1)입니다. Recursive case 부분은 재귀적 호출을 제외하면 some_list[-1:]과 some_list[:-1]에 대한 평가를 해야 하는데요. some_list[-1:]은 시간 복잡도가 O(1)이고, some_list[:-1]은 시간 복잡도가 O(n−1)입니다. 재귀적 부분을 제외한 flip 함수의 시간 복잡도는 O(n)인 거죠.
그렇다면 flip 함수는 몇 번 호출될까요? 매 호출마다 리스트의 길이가 1씩 줄기 때문에, flip 함수는 총 n번 실행됩니다.
flip 함수는 재귀적으로 n번 실행되고 각 호출은 O(n)이기 때문에 총 시간 복잡도는 O(n^2)입니다.
