[내일배움캠프] 2022-11-22 TIL

자료구조 알고리즘 원격 강의 진도 나가기

시간복잡도와 공간복잡도

• 시간복잡도: 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
• 공간복잡도: 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계

*상수나 계수는 무시할 정도이며, 차수가 가장 중요함

*공간복잡도를 희생해서라도 시간복잡도를 낮추는 것이 베스트

 

점근표기법

• 빅오(Big-O): 최악의 성능이 나올 때의 연산량 표기     ex) O(N)
• 빅오메가(Big-Ω): 최선의 성능이 나올 때의 연산량 표기     ex) Ω(1)

* 최악의 경우를 대비해야 하므로 알고리즘 분석은 빅오 표기법 위주로!

 

Array vs Linkedlist

*Python의 경우: []로 감싸는 list 자료형이 array로 만들어졌으나, 동적 배열이라는 것을 이용하여 배열의 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계되어 있다. 파이썬의 배열은 linkedlist로 쓸 수도 있고, array로도 쓸 수 있게 만든 효율적인 자료구조다.

 

Linkedlist 클래스 만들어 보기

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    #맨 뒤에 새로운 Node를 붙이는 함수
    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

    #특정 index의 원소를 찾는 함수
    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

     #특정 index의 Node 뒤에 새로운 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

    #특정 index의 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

관련하여 참고하기 좋은 블로그 글: https://hudi.blog/ds-linked-list/