TIL 9일차 정리

오늘은 크게 일정이 따로 없고 독학하는 시간을 가졌기 때문에 바로 코드 정리를 해보겠습니다.

 

코드정리

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 print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        node = self.get_node(index - 1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index - 1)
        node.next = node.next.next
        return


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()
linked_list.delete_node(0)
linked_list.print_all()

오늘은 Linked_list 에 대해서 알아 보도록 하겠습니다.

	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 공간을 할당받아야 한다.	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array 를 사용하자	삽입과 삭제가 빈번하다면 LinkedList 를 사용하는 것이 더 좋다.

링크드 리스트는 Array와 다르게 동적으로 중간중간 삽입삭제가 편리한 자료구조입니다. 면접에 나올정도로 중요하다고 합니다.

Array 는 [0, 1, 2, 3, 5, 4] 라는 어레이가 있으면 3과 5사이에 4를 넣어주려면 한칸한칸 움직여야 하는 굉장히 불편한 구조를 가지고 있습니다.

하지만 링크드 리스트는 (0) => (1) => (2) => (3) => (5) => (4) 같은 구조를 가지고 있기 때문에 땟다 붙였다 할 수 있는 편리한 리스트입니다. 중간에 삭제 하는것 또한 (3) => 을 삭제하고 싶다면 그 부분만 버리고 =>(5) 를 바로 이어주면 되기 때문에 시간 복잡도가 굉장히 좋습니다.

 

요약하자면 파이썬의 배열은 링크드 리스트로 쓸 수 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조 입니다.

 

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2

    while current_min <= current_max:
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_max + current_min) // 2

    return False


result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

이 코드는 이분탐색 알고리즘 입니다.

 

이분탐색은 순차탐색과 다르게 반씩 짤라가면서 타켓과 가까워지기 때문에 굉장히 효율적인 시간복잡도를 가지고 있는것이 특징입니다.

하지만 이분탐색을 사용하려면 중요한 포인트가 있습니다. 정렬이 되어야 한다는 점입니다. 그렇기에 이분탐색을 사용하기전에 .sort() 함수로 꼭 정렬을 하고 시작하길 바랍니다.

코드를 리뷰해보자면, current_min 값에 최솟값 0을 지정해주고 current_max 값에 현재 인덱스에 마지막 값을 할당해줍니다.

그리고 current_guess 변수에 예측할 값을 넣어 줍니다 이분탐색의 특징 답게 중간 값을 찾아줍니다 최솟 값과 최댓 값을 더한뒤 2로 나눠주면 중간 값을 찾을 수 있지만, 중요한 점은 꼭 // 로 소수점을 지운 몫만 가져와야 합니다. 이러한 로직을 반복하다 보면 순차탐색보다 훨씬 덜 돌면서 타켓 값을 찾을 수 있습니다. 이분탐색의 시간복잡도는 N/2^k = O(logN) 만큼 걸립니다.

 

그럼 오늘의 TIL 은 ... 끄ㅡㅌ(망할 알고리즘)