def fib_optimized(n): current = 1 previous = 0 # 반복적으로 위 변수들을 업데이트한다. for i in range(1, n): current, previous = current + previous, current # n번재 피보나치 수를 리턴한다. return current # 테스트 코드 print(fib_optimized(16)) print(fib_optimized(53)) print(fib_optimized(213))
def fib_tab(n): # 여기에 코드를 작성하세요 fib = [0, 1, 1] for i in range(3, n+1): fib.append(fib[i-1] + fib[i-2]) return fib[n] # 테스트 코드 print(fib_tab(10)) print(fib_tab(56)) print(fib_tab(132))
def fib_memo(n, cache): # 여기에 코드를 작성하세요 # base case if n < 3: return 1 # 이미 n번째 피보나치를 계산했으면: # 저장된 값을 바로 리턴한다 if n in cache: return cache[n] # 아직 n번째 피보나치 수를 계산하지 않았으면: # 계산을 한 후 cache에 저장 cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache) # 계산한 값을 리턴한다 return cache[n] def fib(n): # n번째 피보나치 수를 담는 사전 fib_cache = {} return fib_memo(n, fib_cache) # 테스트 코드 print(fib(10)) print(fib(50)) prin..
def merge(list1, list2): # 지난 실습의 코드를 여기에 붙여 넣으세요 i = 0 j = 0 # 정렬된 항목들을 담을 리스트 merged_list = [] # list1과 list2를 돌면서 merged_list에 항목정렬 while i list2[j]: merged_list.append(list2[j]) j += 1 else: merged_list.append(list1[i]) i += 1 # list2에 남은 항목이 있으면 정렬 리스트에 추가 if i == len(list1): merged_list += list2[j:] # list1에 남은 항목이 있으면 정렬 리스트에 추가 elif j == len..
# 두 요소의 위치를 바꿔주는 helper function def swap_elements(my_list, index1, index2): temp = my_list[index1] my_list[index1] = my_list[index2] my_list[index2] = temp # 퀵 정렬에서 사용되는 partition 함수 def partition(my_list, start, end): # 리스트 값 확인과 기준점 이하 값들의 위치 확인을 위한 변수 정의 i = start b = start p = end # 범위안의 모든 값들을 볼 때까지 반복문을 돌린다 while i < p: # i 인덱스의 값이 기준점보다 작으면 i와 b 인덱스에 있는 값들을 교환하고 b를 1 증가 시킨다 if my_list[i]
num_list = [3, 7, 5, 6, 10] target_num = 10 found = False index_num = -1 for i in range(len(num_list)): if target_num == num_list[i]: found = True index_num = i break print(f"{target_num}의 위치는 {index_num + 1}입니다.")
# 두 요소의 위치를 바꿔주는 helper function def swap_elements(my_list, index1, index2): # 여기에 코드를 작성하세요 temp = my_list[index1] my_list[index1] = my_list[index2] my_list[index2] = temp # 퀵 정렬에서 사용되는 partition 함수 def partition(my_list, start, end): # 여기에 코드를 작성하세요 i = start b = start p = end # 범위안의 모든 값들을 볼 때까지 반복문 돌림 while i < p: # i 인덱스의 값이 기준점보다 작으면 i와 b 인덱스에 있는 값들을 교환하고 b를 1 증가 시킨다 if my_list[i]
def merge(list1, list2): # 여기에 코드를 작성하세요 list3 = sorted(list1 + list2) return list3 # 테스트 코드 print(merge([1],[])) print(merge([],[1])) print(merge([2],[1])) print(merge([1, 2, 3, 4],[5, 6, 7, 8])) print(merge([5, 6, 7, 8],[1, 2, 3, 4])) print(merge([4, 7, 8, 9],[1, 3, 6, 10])) # merge 모법답안 list1 = [4, 7, 8, 9] list2 = [1, 3, 6, 10] i = 0 j = 0 # 정렬된 항목들을 담을 리스트 merged_list = [] # list1과 list2를 돌..
# divide and conquer def consecutive_sum(start, end): # 여기에 코드를 작성하세요 sum = 0 for start in range(end+1): sum += start return sum # 테스트 코드 print(consecutive_sum(1, 10)) print(consecutive_sum(1, 100)) print(consecutive_sum(1, 253)) print(consecutive_sum(1, 388)) # 분할정복 코드 def consecutive_sum(start, end): # base case if end == start: return start # 부분 문제를 반으로 나눠주기 위해서 문제의 정중앙을 정의한다 (Divide) mid = (..
출근하는방법I.py # 시간 복잡도 O(n) def staircase(n): # 여기에 코드를 작성하세요 a, b = 1, 1 for i in range(n): temp = a a = b b = temp + b return a # 테스트 코드 print(staircase(0)) print(staircase(6)) print(staircase(15)) print(staircase(25)) print(staircase(41)) 해결과정 계단의 높이가 4인 경우를 생각해보면 0 → 1 → 2 → 3 → 4 0 → 1 → 2 → 4 0 → 1 → 3 → 4 0 → 2 → 3 → 4 0 → 2 → 4 매번 오를 수 있는 계단의 수는 1 또는 2이다. 따라서 계단으로 가기 위해선 결국 3번째 계단 또는 2번째 계단..
