재귀
-
[Python]이진탐색 재귀함수로 구현해보기(recursion binary search)프로그래밍/알고리즘 2022. 9. 20. 20:24
이번 글에서는 파이썬 언어를 사용하여 재귀함수 기반 이진탐색을 구현합니다. 1. 이진탐색으로 같은 값 찾기 문제 리스트와 목표값이 주어졌을 때 값이 존재한다면 인덱스를 반환하고 없다면 -1을 반환해라. 이때 리스트는 정렬되어 있다. def binary_search(lst,start_p,end_p,target): mid_p = (start_p+end_p)//2 # 중앙 포인트 생성 #전체 탐색후 값이 없다면 -1 반환 if start_p>=end_p: return -1 # 중앙값이 목표값이라면 해당 인덱스 반환 if lst[mid_p] == target: return mid_p # 목표값보다 중앙값이 크다면 시작값부터 중앙값 이전까지 다시 탐색 elif target < lst[mid_p]: return b..
-
[Python]피보나치수열 구현 및 방법 비교: 재귀 함수,동적 프로그래밍 활용(Fibonacci numbers, recursion and dynamic programming)프로그래밍/알고리즘 2022. 9. 20. 16:16
이번 글에서는 파이썬 언어로 피보나치수열을 구현합니다. 이때, 재귀함수 및 동적 프로그래밍 방법을 모두 구현하여 실행시간을 비교합니다. 1. 재귀 함수로 구현(Recursion) def Fibo_recursion(n): if n == 0: return 0 elif n == 1: return 1 else: return Fibo_recursion(n-1) + Fibo_recursion(n-2) 2. 동적 프로그래밍으로 구현(Dynamic programming) def Fibo_dynamic(n): arr = [0]*(n+1) arr[1] = 1 for i in range(2,n+1): arr[i] = arr[i-1] + arr[i-2] return arr[n] 3. 실행시간 비교 # 재귀함수 실행 start..