[프로그래머스] 어서와! 자료구조와 알고리즘은 처음이지? 4,5강

4강 : 재귀 알고리즘 기초

• 재귀함수(recursive func.)
  • 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
• 종결 조건이 반드시 필요
• 예시 : 이진트리(binary trees)
• 예시2 : 자연수의 합 구하기

  #Recursive ver.
  def sum(n):
  	if n<=1:
  		return n
  	else :
  		return n + sum(n-1)
  
  #복잡도 O(n)
  #효율성 낮음
  
  
  #Iterative ver. (반복적인 버전)
  def sum(n):
  	s=0
  	while n>=0:
  		s+=n
  		n-=1
  	return s
  
  #복잡도 O(n)

  #더 효율성 좋은 버전
  def sum(n):
  	return n*(n+1)//2
  
  #복잡도 O(1) 상수시간
  

• 예시3 : n! (factorial)

def what(n):
	if n<=1:
		return 1
	else :
		return n * what(n-1)

 

• 연습 문제 : Fibonacci 순열

#Recursive ver. (재귀적인 버전)
def solution(x):
    if x<=1:
        return x
    else :
        return solution(x-2) + solution(x-1)

#Recursive ver. (재귀적인 버전)
def solution(x):
    if x<=1:
        return x
    else :
        return solution(x-2) + solution(x-1)

 

5강 : 재귀 알고리즘 응용

• 조합의 수 계산 ( nCm ) ⇒ 효율성 떨어짐
  • 항상 여러 조건 생각 (trival)
• 하노이의 탑

 

• 연습문제 : 재귀적 이진 탐색 구현

  def solution(L, x, l, u):
      if l>u:
          return -1
      mid = (l + u) // 2
      if x == L[mid]:
          return mid
      elif x < L[mid]:
          return solution(L, x, l, mid-1)
      else:
          return solution(L, x, mid+1, u)​

Reference

어서와! 자료구조와 알고리즘은 처음이지?