본문 바로가기

Python/알고리즘9

[ Python_알고리즘 ] 동적 프로그래밍 # 피보나치 수열 def fib(n) : if n == 1 or n == 2 : return 1 start = fib(n-2) middle = fib(n-1) end = start + middle return end print(fib(15)) [ 동적 프로그래밍 ] 동적 프로그래밍은 한번 계산 된 결과를 재활용 하는 방식 * 재귀 : 부분 문제의 답을 이용해서 기존 문제의 답을 구하는 방식으로 함수 스스로를 다시 사용 즉, 똑같은 함수를 중첩해서 사용 * 분할 정복 : 부분 문제로 전체적인 큰 문제 해결하기 분할 정복은 부분 문제를 해결한다기 보다는 문제를 2개 이상으로 나누고 합치는 방법이라면 동적 프로그래밍은 큰 문제의 부분문제를 해결해서 큰 문제를 해결하는 방법이다. 동적 프로그래밍은 상향식 접근과.. 2021. 12. 22.
[ Python_알고리즘 ] 분할정복법 ② 퀵 정렬 [ 퀵 정렬 ] Pivot을 기준으로 Pivot 보다 작은 값들을 왼쪽으로, Pivot 보다 큰 값들은 오른쪽으로 정렬 Pivot을 기준으로 값들을 새롭게 배치 왼쪽에 있는 값들은 오른쪽에 있는 값들 보다 작기 때문에 크기 비교없이 각각 정렬해주면 전체 리스트가 정렬됨 def swap_elements(my_list, index1, index2): temp = my_list[index1] my_list[index1] = my_list[index2] my_list[index2] = temp return my_list def partition(my_list, start, end): index = start #모든 index를 체크하기 위한 start index count = start #Pivot 값보다 큰 .. 2021. 12. 21.
[ Python_알고리즘 ] 분할정복법 ① 합병 정렬 #1부터 n까지의 합 def n_sum(start, end): sum_value = 0 if start < end : for i in range( start, end+1 ) : sum_value += i return sum_value print(n_sum(1,100)) #분할 정복법 def n_sum(start, end): if start == end : return start mid = ( start + end ) // 2 return n_sum(start, mid) + n_sum(mid+1, end) [ 합병 정렬 ] 리스트를 왼쪽, 오른쪽 반반 나누어주고 각각의 리스트를 각각 정렬한 후 하나의 리스트로 합병 def merge(list1, list2): i,j = 0,0 final_list = lis.. 2021. 12. 20.
[ Python_알고리즘 ] 배열의 최대곱 & 거리 구하기 ( sqrt ) # 두 배열의 최댓값 구하기 def max_value(left_array, right_array); new_list = list() for i in left_array : for j in right_array : new_list.append(i*j) #maxvalue = max(maxvalue, i*j) #max 함수에 두가지 파라미터를 넣어서 두 값을 비교해 더 큰 값 구하기 return max(new_list) #return maxvalue print(max_value([9,-6,5],[-4,3,8]) #두 지점 사이의 최소 거리 구하기 #sqrt함수 from math import sqrt def distance(store1, store2): return sqrt((store1[0] - store2[.. 2021. 12. 20.
[ Python_알고리즘 ] 이진 탐색 재귀 함수 [ 이진 탐색 ] 이진 탐색 : 리스트를 1회 비교를 거칠 때마다 탐색 범위가 절반으로 줄어든다. # 이진 탐색 반복문 def binary_search( element, my_list ) : start = 0 end = len(my_list)-1 while start my_list[middle] start = middle + 1 return None print( binary_search( 6, [2,3,5,6,8,9,10,11] ) d.. 2021. 12. 18.
[ Python_알고리즘 ] 리스트 뒤집기 [ 리스트 뒤집기 ] # 리스트 슬라이싱을 이용한 reverse # 문자열 뒤집기 => [::-1] def list_reverse(my_list) : return my_list[::-1] my_number_list = [1,2,3,4,5,6,7,8,9] print( list_reverse(my_number_list) # 리스트 슬라이싱을 이용한 reverse 2 def list_reverse(my_list) : if len(my_list) == 0 or len(my_list) == 1 : return my_list return my_list[-1:] + list_reverse(my_list[:-1]) # my_list[-1:] => 9 ( 인덱스 -1 ~ 0 ) # my_list[:-1] => [ 1,2.. 2021. 12. 18.
[ Python_알고리즘 ] 자릿 수 합 파라미터 n을 받고 n의 자릿 수의 값들을 모두 더하는 함수 # 반복문 def sum_number(n): my_str = str(n) my_number = 0 for i in range(len(my_str)) : my_number += int(my_str[i]) return my_number print(sum_number(13579)) # 재귀함수 def sum_number(n): if n < 10 : return n return n % 10 + sum_number(n//10) print(sum_number(13579)) # 슬라이싱을 이용한 재귀함수 def sum_number(n): my_str = str(n) if len(my_str) == 1 : return int(n) if len(my_str) .. 2021. 12. 17.
[ Python_알고리즘 ] 삼각수 [ 삼각수 ] n번째 삼각수는 자연수 1부터 n까지의 합 파라미터로 n값을 받고 n번째 삼각 수를 리턴해주는 재귀함수 def triangle_number(n): if n == 1 : return 1 result = n + triangle_number(n-1) return result #triangle_number(1)부터 triangle_number(10)까지 출력 for i in range(1, 11): print(triangle_number(i)) 2021. 12. 17.
[ Python_알고리즘 ] 피보나치 수열 #팩토리얼 재귀함수 def factorial(n) if n == 0 : return 1 return factorial(n-1)*n print(factorial(4)) [ 피보나치 수열 ] 첫번째 항과 두번째 항이 1이고, 세번째 항부터는 바로 앞의 두 항의 합으로 정의된 수열 def fib(n): if n == 1 or n == 2 : return 1 elif n > 2 : start = fib(n-2) middle = fib(n-1) end = start + middle return end # 몇번째 항인지 출력 for i in range(1, 11): print(fib(i)) def fib(n): if n == 1 or n == 2 : return 1 start = fib(n-2) middle = f.. 2021. 12. 17.

티스토리툴바