이 필기내용은 프로그래머스 홈페이지의 어서와! 자료구조와 알고리즘은 처음이지? 강의를 들으면서 제가 필기한 내용입니다.
어서와! 자료구조와 알고리즘은 처음이지? https://programmers.co.kr/learn/courses/57
재귀 알고리즘
> 하나의 함수 또는 알고리즘에서 자신을 다시 호출하여 작업을 수행하는 것을 재귀 알고리즘이라 한다.
> 이 알고리즘을 사용하는 이유? 생각보다 많은 종류의 문제들이 재귀적인 방법으로 해결 가능하기 때문이다.
때로는 너무나도 간단하게 재귀함수를 이용하여 복잡한 문제들을 해결하는 경우도 있다.
> 같은 종류의 문제지만, 난이도 측면에서 보다 쉬운 문제의 답과 해결과정을 이용하여 풀 수 있는 성질을 이용하여,
그 성질을(알고리즘을) 반복적으로 적용하여 문제를 풀어내는 방법이다.
> 일반적으로 재귀알고리즘을 이용한 예시로는,
이진 트리, 피보나치 순열, 하노이 탑, 팩토리얼이나 자연수의 연속된 합 구하기 등등이 있다.
재귀 알고리즘을 이용한 다양한 예시들
1. 이진 트리
> 이진 트리 안에서 재귀적인 성격을 가진 구조를 알아보자.
이미지 출처 : https://terms.naver.com/entry.nhn?docId=3407403&cid=40942&categoryId=32841
> 이진트리는 일단 맨 위쪽 노드인 루트 노드가 주어지며, 그 다음에 들어올 숫자들은 루트노드와 대소비교를 거치게 된다. 루트 노드보다 작은 숫자는 왼쪽으로, 큰 숫자는 오른쪽으로 분류된다. 이 과정을 반복한다. 여기서 재귀적인 반복이 일어나게 된다.
> 그 이후에 들어올 노드들 역시, 본인과 맞닥뜨린 노드들의 대소비교를 통해 차례차례 자리를 찾아간다.
> 이진 트리를 탐색할때에도 같은 원리로 탐색하여 원하는 값을 찾아낼 수 있다.
2. 자연수의 합
> 자연수의 합을 구하는 알고리즘도 재귀 알고리즘을 이용할수있다.
def sum(n):
return n+sum(n-1)
> 뭔가 이렇게만 하면 제대로 작동될것 같지만, 여기서 중요한 포인트가 나오게 된다.
종결조건(trivial case) 이라는 것을 지정해주지 않으면, 위의 코드는 반복되는 알고리즘을 빠져나올수 없다.
그러므로 비정상적으로 작동이 될 수 밖에 없는 것이다.
if n <= 1:
return n
이런 종결조건(종료조건)이 필요하다.
> 즉 완성된 코드는 이러하다.
def sum(n):
if n <= 1: #종결조건
return n
else:
return n+sum(n-1)
3. 팩토리얼
> 팩토리얼 구하는 알고리즘도 재귀 알고리즘을 이용할 수 있다.
def fact(n):
if n <= 1:
return 1
else:
return n * fact(n-1)
4. 피보나치 순열
> 또한 피보나치 순열도 재귀 알고리즘을 이용할 수 있다.
def solution(x):
if x == 0:
return 0
elif x == 1:
return 1
elif x > 1:
return solution(x-1) + solution(x-2)
재귀 알고리즘의 효율성
> 우리는 재귀 알고리즘의 효율성에 대해서도 생각해 볼 필요가 있다.
과연 모든 재귀 알고리즘이 항상 높은 효율성을 자랑하게 될까?
다음의 예시를 보면 항상 그런것도 아니라는 것을 알게된다
(재귀 알고리즘) (recursive version)
def sum(n):
if n<=1:
return n
else:
return n+sum(n-1)
vs
(반복 알고리즘) (iterative version)
def sum(n):
s = 0
while n >= 0:
s += n
n -= 1
return s
> 1부터 n까지의 자연수의 합을 구하는 알고리즘이다. 이 경우에 둘다 시간 복잡도는 똑같이 O(n)이다.
하지만 효율성 측면에서는 재귀알고리즘으로 구현한 것이 더 떨어진다.
> 왜냐하면 재귀 알고리즘으로 구현한 것은 else문이 실행될때마다 다시 sum함수를 호출해야하는 번거로움이 생기기 때문이다.
> 즉 n이 커질수록 (재귀함수를 많이 호출해야할수록) 효율성 부분에서는 불리할수밖에 없다.
> 다시 말해, 항상 재귀적인 알고리즘이 효율적인 것만은 아니다!
'Data Structure & Algorithm' 카테고리의 다른 글
파이썬으로 연결 리스트(Linked List) 구현해보기 (0) | 2020.03.25 |
---|---|
python 을 활용한 자료구조와 알고리즘 공부 - (5) (0) | 2020.03.10 |
python 을 활용한 자료구조와 알고리즘 공부 - (4) (0) | 2020.03.09 |
python 을 활용한 자료구조와 알고리즘 공부 - (2) (0) | 2020.03.05 |
python 을 활용한 자료구조와 알고리즘 공부 - (1) (0) | 2020.02.26 |