알고리즘 2주차 완료

이번 알고리즘 2주차는 상당히 어려웠다. 특히나 링크드리스트의 개념을 이해하는건 마치, 생명을 탄생시켜 움직임을 작동시키는 것처럼 느껴졌다. 그래도 반복해서 듣고 보고 이해하려고 하니, 조금은 느낌이 와닿는듯 하였고, 문제를 풀면서 조금씩 익숙해지기 시작했다. 또 이번 주차에서 배운것 중에는 이진탐색이나 재귀함수의 개념자체는 그렇게 어렵지는 않았던것 같았다.

 

2주차 숙제의 첫번째 문제

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):
        cur = self.head
        len_count = 1
        while cur.next is not None:
            cur = cur.next
            len_count += 1

        cur = self.head
        for i in range(len_count - k):
            cur = cur.next

        return cur


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

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

 

ㄴ 이 문제 또한 자력으로 풀어냈으나 풀이와는 조금 다르게 O(N제곱)만큼 소요되는 부분이라 조금 비효율적이다.

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


def is_available_to_order(menus, orders):
    for order in orders:
        count = 0
        for menu in menus:
            if menu == order:
                count += 1
        if count == 0:
            return "주문 불가"

    return "주문 가능"


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

 

2주차 숙제의 세번째 문제

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
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(array):
        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 + array[current_index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
                                                       current_sum - array[current_index])


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