[자료구조와 알고리즘] #2. 재귀 알고리즘

프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?'를 학습하며 정리한 내용입니다. 

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

 

 

문제1. 피보나치 순열 구현하기 

문제 : 인자로 0, 혹은 양의 정수 x가 주어질때 피보나치 순열의해당 값을 구하여 반환하는 함수 

참고 : 피보나치 순열 

• F0 = 0
• F1 = 1
• F2 = F0 + F1 = 0+1 = 1 
• F3 = F1 + F2 = 1 + 1 = 2 
• F4 = F2 + F3 = 1 + 2 = 3  

def solution(x):
    answer = 0
    
    if x <=1:
        return x
    else: x = solution(x-2)+solution(x-1)
    
    answer = x 
    
    return answer

 

문제2. 재귀적 이진 탐색 구현 

문제 :리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어지고, 또한 탐색의 대상이 되는 리스트 내에서의 범위 인덱스가 l 부터 u 까지로 (인자로) 정해질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

 

def solution(L,x,l,u):        #L:리스트, x:찾는 원소, l:lower, u: upper 
	if l > u :                #해당 리스트에 x가 없음
    	return -1 
    
    mid = (l+u)//2            #중간 값 정의 
    
    if x == L[mid]:
    	return mid 
    
    elif x < L[mid] :        #x가 왼쪽에 있다고 가정 
    	return solution(L,x,l,mid-1) #끝값을 mid 앞의 값으로 정해서 반띵 
    elif x > L[mid] :        #x가 오른쪽 
    	return solution(L,x,mid+1,u) #시작값을 mid 다음 값으로 정해서 반띵

 

+ 왜 해당 리스트에 x가 없을 때 lower > upper라고 가정할까? 

L = [ 1,3,4,6] , x = 8이면  시작 전   l = 0, u = 3  첫번째 탐색 이후  mid = 1 → solution(L,x,2,3) 반환  두번째 탐색 이후  l = 2, u = 3, mid = 2 → solution(L,x,3,3)반환  세번째 탐색 이후  l=3, u = 3, mid = 3 → solution(L,x,4,3)반환  네번째 탐색  l > u 가 되어 -1 반환