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 = (..
리스트 파이썬 리스트는 굉장히 활용 범위가 큰 자료형입니다. 프로그래밍을 할 때 사실상 리스트만 사용하면 대부분의 경우 필요한 기능을 모두 사용할 수 있죠. 너무 사용 가능 범위가 넓다 보니까 어떤 다른 자료형을 사용할지 생각하지 않고 바로 리스트를 사용해 버리는 경우가 많은데요. 무조건 리스트를 사용해버리면 효율적으로 프로그래밍을 하기 힘듭니다. 이게 무슨 말인지 안 와닿을 수도 있는데요. 코드 예시를 하나 볼게요. 바로 리스트를 사용할 때 여러 개의 데이터(정확히는 0부터 999999까지의 정수)를 저장한 후, 특정 데이터를 탐색하는 코드를 써볼 건데요. 대부분의 상황과 비슷하게 동적 배열로 구현돼 있는 파이썬 리스트를 사용하면 원하는 코드를 쓸 수 있습니다. 바로 해볼게요. # 예시를 위해 사용할 ..
