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

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

 

어서와! 자료구조와 알고리즘은 처음이지?  https://programmers.co.kr/learn/courses/57

어서와! 자료구조와 알고리즘은 처음이지? | 프로그래머스

---

재귀 알고리즘의 응용과 효율성

 

> 저번 파트 마지막에서 잠깐 다룬 재귀 알고리즘의 효율성을 예제로 다뤄보려고 한다.

> 재귀알고리즘은, 그것의 counterpart(반대의 경우) 인 반복적 알고리즘보다 효율성이 떨어지는 경우가 상당히 많다.

> 하지만, 반복적 알고리즘으로는 구현하기가 상당히 복잡하거나, 인간의 두뇌로는 간단히 이해하기에 어려운 알고리즘들을 생각보다 쉽게 풀어내고 구현해 내는 경우가 꽤나 존재하기 때문에 종종 사용된다.

---

ex) 조합의 수를 재귀적인 알고리즘으로 접근!

> 조합의 수는, n개의 서로 다른 원소들 중에서 m개를 선택하는 경우의 수이다.

 

> 이것을 재귀적인 알고리즘으로 접근하자면,

n개에서 m개를 택하는 경우의 수 = n-1개에서 m개를 택하는 경우의 수 + n-1개에서 m-1개를 택하는 경우의 수   

이다.

 

n-1개에서 m개를 택하는 경우의 수 를 1번이라 하고,

n-1개에서 m-1개를 택하는 경우의 수 를 2번이라 하자.

 

> 특정한 원소 한개의 입장에서 바라봤을때,

1번은 그 원소를 포함하지 않고(고르지 않고) 나머지 n-1개 중에서 m개를 고르는 것이고,

2번은 그 원소를 반드시 포함시키면서(반드시 고르면서) 나머지 n-1개 중에서 m-1개를 고르는 것이다. 

         2번에서 m개를 고르는 것이 아닌 m-1개를 고르는 이유는, 이미 그 원소는 골랐기 때문에, 

         그것을 제외한 m-1개를 고르는 것이다.

 

조합

> 고등학교 순열과 조합 파트에서 나오는 방법을 알고리즘으로 그대로 옮긴 것이다.

---

 

ex) 4개의 원소 [1,2,3,4]에서 2개를 고르는 경우의 수를 구하시오.

(단, (1,2)와 (2,1)은 서로 같은 것으로 한다.)

def combination(n,m):
    if (n == m or m == 0): return 1
    else: return combination(n - 1, m - 1) + combination(n - 1, m)
 
 
print(combination(4,2))   
# 6가지가 나온다! 
# (1,2) (1,3) (1,4) (2,3) (2,4) (3,4)

> n과 m이 같은 경우와, m이 0인 경우에만 탈출조건(trivial case)를 설정해주면 된다.

나머지는 재귀 알고리즘에 맡기면 알아서 해결된다!

---

> 앞에서도 언급했지만, 재귀 알고리즘은 일반적으로 효율성 측면에서는 반복적 알고리즘(loop 사용)

보다 떨어진다. 하지만, 트리(tree)라던지, 하노이 탑 같은 반복적 알고리즘으로는 구현하기가 복잡한 경우에는

엄청난 위력을 발휘하기도 한다.