python 을 활용한 자료구조와 알고리즘 공부 - (3)

이 필기내용은 프로그래머스 홈페이지의 어서와! 자료구조와 알고리즘은 처음이지? 강의를 들으면서 제가 필기한 내용입니다.

 

어서와! 자료구조와 알고리즘은 처음이지?  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이 커질수록 (재귀함수를 많이 호출해야할수록) 효율성 부분에서는 불리할수밖에 없다.

> 다시 말해, 항상 재귀적인 알고리즘이 효율적인 것만은 아니다!