알고리즘 2주차 - 숙제

Q1. 링크드리스트 끝에서 k번 째 값 출력하기

❓

Q. 링크드 리스트의 끝에서 K번째 값을 반환하시오.

[6] -> [7] -> [8] # 이런 링크드 리스트가 입력되었을 때, 
                  # 끝에서 2번째 값은 7을 반환해야 합니다!

# 코드 스니펫
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)

    def get_kth_node_from_last(self, k):
        # 구현해보세요!
        return self.head


linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)

print(linked_list.get_kth_node_from_last(2).data)  # 7이 나와야 합니다!

# 내 코드
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)

    def get_node_linked_list(self, index):
        pass

    def get_kth_node_from_last(self, k):
        k = k-1
        count = 0
        cur = self.head
        while cur is not None:
            if count == k:
                return cur
            else:
                cur = cur.next
                count += 1
        if cur == None: # 예외처리
            exit()


linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)

print(linked_list.get_kth_node_from_last(2).data)  # 7이 나와야 합니다!

Q2. 배달의 민족 배달 가능 여부

❓

Q. 배달의 민족 서버 개발자로 입사했다. 상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다. 그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.

menus = ["떡볶이", "만두", "오뎅", "사이다", "콜라"]
orders = ["오뎅", "콜라", "만두"]

# 코드 스니펫
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]


def is_available_to_order(menus, orders):
    # 이 부분을 채워보세요!
    return True


result = is_available_to_order(shop_menus, shop_orders)
print(result)

# 내 코드
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]


def is_available_to_order(menus, orders):
    menus.sort() # ['떡볶이', '만두', '사이다', '오뎅', '콜라']
    orders.sort() # ['만두', '오뎅', '콜라']
    total_correct = []
    for order in orders:
        correct = False
        current_min = 0
        current_max = len(menus) - 1
        current_guess = (current_min + current_max) // 2
        while current_min <= current_max:
            if menus[current_guess] == order:
                correct = True
                break
            elif menus[current_guess] < order:
                current_min = current_guess + 1
            else:
                current_max = current_guess - 1
            current_guess = (current_min + current_max) // 2
        menus = menus[current_guess+1:] # 그 다음거는 무조건 이거 이상이기에 슬라이싱
        if correct == False:
            return False
    return True



result = is_available_to_order(shop_menus, shop_orders)
print(result)

Q3. 더하거나 빼거나

❓

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

# 코드 스니펫
numbers = [1, 1, 1, 1, 1]
target_number = 3


def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target):
    # 구현해보세요!
    return 5


print(get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number))  
# 5를 반환해야 합니다!

• N의 길이의 배열에서 더하거나 뺀 모든 경우의 수 N-1의 길이의 배열에서 마지막 원소를 더하거나 뺀 경우의 수를 추가한다.

• 예) [2, 3]
  • +2 +3
  • +2 -3
  • -2 +3
  • -2 -3

• 파이썬에서는 정수형, 캐릭터형 등 프리미티를 타입 같은 경우 파이썬 내부에서 파라미터로 넘기면 그 값을 복제해서 새로운 값을 만듬(Call By Value)

• 즉 그렇기에 target_count 부분을 신경써야함

• 함수에서 외부의 변수를 변경해주고 싶다라면 global 키워드를 사용해야함

• 반복되는 구조라면 '재귀'를 어떻게 쓸 수 있을지 생각

# 튜터 답안
numbers = [1, 1, 1, 1, 1]
target_number = 3

result_count = 0
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
    if current_index == len(numbers):
        if current_sum == target:
            global result_count
            result_count += 1
        return
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum + numbers[current_index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum - numbers[current_index])



get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)
print(result_count)