알고리즘 2주차 숙제

뒤에서 k번째 노드 출력

 def get_kth_node_from_last(self, k):
        cnt = 0
        cur = self.head
        while cur is not None:
            cnt += 1
            cur = cur.next

        find_k = cnt - k
        cur = self.head
        for i in range(find_k):
            cur = cur.next
        return cur

=> 두 번 돌게 됨.

    def get_kth_node_from_last(self, k):
        slow = self.head
        fast = self.head

        for i in range(k):
            fast = fast.next

        while fast is not None:
            slow = slow.next
            fast = fast.next

        return slow

=>한 번 돌게 됨.
=>이 문제같은 경우는 링크드리스트의 길이도 길지 않아 두 가지 방법에 시간복잡도가 크게 차이 나지않지만, 한 번만 돌게 되는 코드는 기억해 두는 것이 좋을 것 같다.

배달 가능 여부

def is_available_to_order(menus, orders):
    menu = set(menus)
    for order in orders:
        if order not in menu:
            return False
        
    return True

=>굳이 이진탐색 할 필요가 없음.
set을 이용해서 in연산을 진행하면 O(1)의 시간복잡도로 처리함.
그냥 리스트로 진행하면 시간복잡도는 O(N)이 됨.
따라서 set함수를 이용함.

더하거나 빼거나

numbers = [1, 1, 1, 1, 1]
target_number = 3
cnt = 0  # target값이 나오는 연산 갯수
# sum = 0  # 진행된 연산 합
# index = 0  # 연산순서

def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, index, sum):
    if index == len(array):
        if sum == target:
            global cnt
            cnt += 1
        return

    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, index + 1, sum + array[index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, index + 1, sum - array[index])

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

=>grobal + 재귀함수

알고리즘3주차

스택&큐

:스택과 큐는 들어가고 나오는 곳이 정해져있는 자료구조
1. 스택

• 맨 위에 들어가고 맨 위에서 나오는 구조

2. 큐

• 맨 위에 들어가고 맨 아래에서 나오는 구조

해쉬

:해쉬알고리즘을 통해서 문자열을 고정된 길이의 데이터로 만들 수 있음.
->블록체인기술에 사용되기도 하고, 딕셔너리를 만들때도 사용함.

버블정렬

• 배열의 n번째와 n+1번째를 비교

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
    for i in range(len(array), 0, -1):
        for j in range(i-1):
            if array[j] > array[j+1]:
                array[j],array[j+1] = array[j+1],array[j]
    return array

bubble_sort(input)