이 필기내용은 프로그래머스 홈페이지의 어서와! 자료구조와 알고리즘은 처음이지? 강의를 들으면서 제가 필기한 내용입니다.
어서와! 자료구조와 알고리즘은 처음이지? 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)라던지, 하노이 탑 같은 반복적 알고리즘으로는 구현하기가 복잡한 경우에는
엄청난 위력을 발휘하기도 한다.
'Data Structure & Algorithm' 카테고리의 다른 글
파이썬으로 연결 리스트(Linked List) 구현해보기 (0) | 2020.03.25 |
---|---|
python 을 활용한 자료구조와 알고리즘 공부 - (5) (0) | 2020.03.10 |
python 을 활용한 자료구조와 알고리즘 공부 - (3) (0) | 2020.03.05 |
python 을 활용한 자료구조와 알고리즘 공부 - (2) (0) | 2020.03.05 |
python 을 활용한 자료구조와 알고리즘 공부 - (1) (0) | 2020.02.26 |