스파르타 코딩 클럽 알고리즘 2주차 숙제

숙제하면서 알게 된 것
1. python에서 클래스나 함수를 정의할 때 자기 자신을 매개변수로 받을 수 있다.(self 매개변수)
2. 클래스 내부에서 __init__ 메소드를 사용하여 클래스에 대한 초기화를 수행할 수 있음

숙제 내용
1. 연결 리스트에서 뒤에서 n번째인 노드의 값을 구하기
2. 주문한 음식을 배달할 수 있는지 확인하기
3. 주어진 수를 더하거나 빼서 원하는 값을 구할 수 있는 경우의 수를 구하기

1번 숙제

# linked list using python
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)
......

연결 리스트에서 Node 클래스는 값은 존재하지만 다음 노드를 가리키지 않는 상태로 초기화가 되어 있다. 그리고 LinkedList 클래스는 노드에 값이 저장되어 있는 상태로 초기화되어 있으며, append 메소드를 사용하여 새로운 노드에 값을 추가할 수 있다.

# 뒤에서 n번째에 위치한 노드의 값 구하기
    def get_nth_node_from_last(self, n):
        length = 1
        cur = self.head

        while cur.next is not None:
            cur = cur.next
            length += 1
        end_length = length - n
        cur = self.head
        for i in range(end_length):
            cur = cur.next
        return cur

위의 get_nth_node_from_last 메소드는 다음 노드를 가리키는 포인터가 존재할 경우 그 포인터가 없는 노드를 찾을 때까지 length를 1씩 증가시킨다. 노드를 모두 찾은 후에는 뒤에서 n번째 노드의 값을 탐색한다.

2번 숙제

# 주문한 메뉴와 메뉴판을 비교(이진탐색)
def is_existing_target_number_binary(target, array):
    cur_min = 0
    cur_max = len(array) - 1
    cur_guess = (cur_min + cur_max) // 2

    find_count = 0

    while cur_min <= cur_max:
        find_count += 1
        if array[cur_guess] == target:
            print(find_count, "회 탐색")
            return True
        elif array[cur_guess] < target:
            cur_min = cur_guess + 1
        else:
            cur_max = cur_guess - 1

	# 중간값을 기준으로 배열을 다시 반으로 나눈다.
        cur_guess = (cur_min + cur_max) // 2

    return False

이진 탐색을 사용하여 메뉴판의 메뉴와 주문한 메뉴를 비교하기 전에 메뉴판 또는 주문한 메뉴를 가나다 또는 abcd 순으로 정렬한다.

buffet_menus = ["스시", "샐러드", "육회", "케이크", "탕수육", "마운틴듀", "에스프레소", "스테이크"]
buffet_orders = ["스시", "스테이크", "탕수육"]

주문한 메뉴 및 메뉴판은 위와 같이 구현할 수 있다.

def is_available_to_order(menus, orders):
    menus.sort()
    for order in orders:
        if not is_existing_target_number_binary(order, menus):
            print("다시 주문해주세요!")
            return False

    print("주문이 가능합니다.")
    return True

참고로 menus.sort()를 orders.sort()로 변경해도 def is_available_to_order 함수의 True/False 값은 동일하다. 다만 메뉴판의 수 또는 주문한 메뉴의 수에 따라 비교하는 횟수는 달라질 수 있다.

def is_available_to_order(menus, orders):
    # menus -> orders 변경
    orders.sort()
    for order in orders:
        if not is_existing_target_number_binary(order, menus):
            print("다시 주문해주세요!")
            return False

    print("주문이 가능합니다.")
    return True

3번 숙제

# 주어진 수들을 더하거나 빼서 원하는 값을 구하는 경우의 수를 구하라
given_number = [1, 1, 1, 1, 1]
target_number = 3
case_count = 0


def count_of_ways_target_plus_or_minus(array, target, cur_index, cur_sum):
    if cur_index == len(array):
        if cur_sum == target:
            global case_count
            case_count += 1
        return
    # 더하거나 빼기
    count_of_ways_target_plus_or_minus(array, target, cur_index + 1, cur_sum + array[cur_index])
    count_of_ways_target_plus_or_minus(array, target, cur_index + 1, cur_sum - array[cur_index])

count_of_ways_target_plus_or_minus 함수에서 주어진 수를 1개씩 사용할 경우 cur_sum에서 주어진 수를 더하거나 뺄 수 있으며, cur_index는 1씩 증가한다. (이 때 cur_sum 및 cur_index의 값은 0이라고 가정)
그리고 주어진 수를 전부 사용할 경우 cur_index의 값이 배열의 길이와 같아지면서 해당 함수를 종료할 수 있다.