📚 TIL

📕 알고리즘 강의 2주차 복습

📌 오늘의 문제

✔ 링크드리스트 끝에서 k번째 노드 찾기

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = 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)
    #노드를 2개 잡는다

    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




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

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

✔ while cur is not None VS while cur.next is not None

이렇게 내가 직접 그려보니 이해가 훨씬 잘되는 것 같다.
결론 ! 전자는 루프를 빠져나왔을 때 cur이 NULL이 되고 후자는 루프를 빠져나왔을 때 cur은 마지막 노드가 된다

✔ 문자열 리스트 2개 비교

• ✔ 내가 푼 코드

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


def is_available_to_order(menus, orders):
    # 이 부분을 채워보세요!
    shop_menus.sort()
    left=0
    right=4
    find=0
    for i in shop_orders:
        while left<=right:
            mid=(left+right)//2
            if shop_menus[mid]==i:
                find=1
                break
            elif shop_menus[mid]<i:
                left=mid+1
            else:
                right=mid-1
        if find!=1:
            return False
    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_set = set(menus)
    for order in orders:
        if order not in menus_set:
            return False
    return True


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

❗ 집합은 중복을 허용하지 않는 자료형으로 집합 내에서 탐색의 시간복잡도는 O(1)이다 ❗

✔ 타겟넘버

이 문제는 전에도 본 적이 있는 문제 같다 ㅎㅎ 하지만 전체의 경우를 다 해보는 것 밖에는 떠오르지 않았다. 그래서 solution을 봤는데 재귀함수 방법을 사용했다.

numbers = [2, 3, 1]
target_number = 0
result_count = 0  # target 을 달성할 수 있는 모든 방법의 수를 담기 위한 변수


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)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
print(result_count)  # 2가 반환됩니다!

함수에서 파라미터로 배열을 넘기면 그 내부에 원소를 추가하거나 할 수 있는데 파라미터로 int ,str 타입의 변수를 넘기면 그 값이 복제되어 새로운 값을 생성한다
따라서 함수 내부의 변수 값만 변경이 되고 함수의 외부의 변수에는 변경사항이 적용되지 않기 때문에 문제가 생긴다, 이런 경우에는 함수 외부의 변수를 사용하기 위해 글로벌 변수를 사용한다

📕 알고리즘 강의 3주차

📖 정렬

📌 버블 정렬

• 순서대로 앞과 뒤를 비교하면서 정렬하는 방식
• 시간복잡도 O(N^2)

📌 선택 정렬

• 배열의 첫번째 원소부터 배열의 가장 작은 원소를 바꾼다
• 첫번째 원소가 정해진 후에는 두번째 원소를 첫 번째 원소를 제외한 원소들중에서 가장 작은 원소와 바꾼다
• 이렇게 차례차례 바꾼다
  -- 시간복잡도 O(N^2)

📌 삽입 정렬

• 배열의 첫번째 원소부터 정렬한다
• 두번째 원소부터 앞의 원소와 비교해서 오름차순으로 정렬을 한다.
• 이렇게 정렬이 된 원소들과 비교해서 정렬할 원소가 정렬된 원소보다 크다면 비교를 중단해도된다(break)
  -- 시간복잡도 O(N^2)

📌 병합 정렬 (merge)

• 분할 : 시간복잡도 O(log2N)
• 병합 : 시간복잡도 O(N)
  최종 시간 복잡도 : O(log2N * N)

I will

• 완전 루즈해지는 것 같다 ... 이러지마 ... ㅠㅠ
• 평일에 하기로 했지만 못한 것들은 주말에 ....