스파르타 코딩클럽
내일배움캠프 AI 웹개발자양성과정 2회차
알고리즘 강의 2주차 숙제
1. 링크드 리스트 끝에서 K 번째 값 출력하기
Q. 링크드 리스트의 끝에서 K번째 값을 반환하시오.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
# 링크드 리스트의 앞에서 k번째 노드를 반환하는 함수
def get_kth_node_from_front(self, k):
current_node = self.node
current_count = 1
while True:
current_count += 1
current_node = current_node.next
if current_count == k:
break
return current_node
# 끝에서 k번째 노드를 반환하는 함수
def get_kth_node_from_last(self, k):
count = 0
node = self.head
while node is not None:
count += 1
node = node.next
if k > count:
print('입력값이 현재 노드의 개수보다 큽니다.')
return
n = count - k
node = self.head
for _ in range(n):
node = node.next
return node
linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)
print(linked_list.get_kth_node_from_last(2).data) # 7이 나와야 합니다!2. 배달의 민족 배달 가능 여부
Q. 배달의 민족 서버 개발자로 입사했다.
상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다.
그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]
def is_available_to_order(menus, orders):
shop_menus.sort()
order_bool = True
for order in shop_orders:
order_bool = order_bool & find_binary_by_recursion(shop_menus, order, 0, len(shop_menus)-1)
return order_bool
def find_binary_by_recursion(array, target, start, end):
if start > end:
return False
mid = (start + end) // 2
if target == array[mid]:
return True
if target < array[mid]:
return find_binary_by_recursion(array, target, start, mid-1)
else:
return find_binary_by_recursion(array, target, mid+1, end)
result = is_available_to_order(shop_menus, shop_orders)
print(result)3. 더하거나 빼거나
Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.
numbers = [1, 1, 1, 1, 1]
target_number = 3
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target):
print("function is called", array, target)
if len(array) == 1:
if array[0] == target or -1 * array[0] == target:
return 1
else:
return 0
last = array[-1]
target_1 = target + last
target_2 = target - last
way_1 = get_count_of_ways_to_target_by_doing_plus_or_minus(array[:-1], target_1)
way_2 = get_count_of_ways_to_target_by_doing_plus_or_minus(array[:-1], target_2)
return way_1 + way_2
print(get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number)) # 5를 반환해야 합니다!Github
kimphysicsman