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

자료구조 & 알고리즘 특강 (강창민 튜터님)

시간복잡도

• 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. (출처: 위키피디아)
• 프로그램의 수행 성능을 최악의 경우를 가정하여 정량화하는 방법으로 고안한 알고리즘이 정말로 유용한지 판단하는 좋은 기준이 된다.
• Big-O(빅오) 표기법으로 표시(ex O(1), O(N), O(N²))하며, N의 지수부분만이 유효하게 쓰이고 나머지(계수와 상수)는 절삭한다.

공간복잡도

• 문제를 해결하는데에 대한 공간과의 상관관계를 가리킨다.
• 최적화가 덜 되어있다고 해도 당장은 프로그램을 돌리는 컴퓨팅 리소스의 성능을 올리면 해결이 되어서 시간 복잡도에 비해서는 중요도가 높지 않다.

배열

• 배열은 프로그래밍을 할 때 가장 자연스럽게 많이 쓰는 자료구조이며, 연관된 데이터를 하나의 변수에 그룹핑해서 관리하는 게 핵심이다.
• 배열을 생성하면 메모리에 연속적인 위치에 존재를 하여 하나의 변수에 여러 정보를 담을 수 있고, 반복문과 결합하면 많은 정보도 효율적으로 처리할 수 있다.
• O(1)의 조회시간,  O(N)의 원소 삽입 혹은 삭제시간(배열 끝이 아닌 다른 곳에서), O(N)의 검색시간(정렬이 되어있는 배열이면 O(log N))
• 특정 원소를 삭제하거나 null로 만들어도 그 흔적은 그대로 남아있다.(파이썬에서는 이를 해결함)

링크드리스트

• 노드: 각 자료를 부르는 이름, 화물차의 한 칸 한 칸, 맨 앞은 Head, 맨 뒤는 Tail
• 포인터: 다음 노드를 가리키는 것(다음 노드의 주소를 값으로 가짐), 화물차의 연결부, 맨 뒤 노드의 포인터는 NULL
• O(N)의 조회시간,  O(1)의 원소 삽입 혹은 삭제시간
• 링크드리스트 클래스 만들어보기(주석과 함께)
  • get_node를 정의할 때 입력된 index가 실제 링크드리스트의 길이보다 큰 예외를 if 문으로 처리해주었다.(숙제!)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None # None은 NULL과 같아요

class LinkedList:
    def __init__(self, value):
        self.head = Node(value)  # head 에 시작하는 Node 를 연결합니다.

    def append(self, value): # LinkedList 가장 끝에 있는 노드에 새로운 노드를 연결합니다.
        curr = self.head         
        while curr.next is not None: # curr의 다음이 끝에 갈 때까지 이동합니다. 
            curr = curr.next          
        curr.next = Node(value)

    def get_node(self, index):
        node = self.head # 링크드리스트의 Head를 처음 노드로 지정합니다!
        curr_idx = 0 # 현재 순회하고 있는 index를 나타냅니다!
        # 현재 순회하고 있는 index가 원하는 위치보다 작다면 계속 루프를 돌아요!
        while curr_idx < index: 
            node = node.next # 원하는 위치에 당도할 때 까지 다음 노드로 이동!
            curr_idx += 1 # 인덱스도 갱신!
            if node == None:
                print('올바르지 않은 index 입니다.')
                return 
        return node # 원하는 인덱스의 노드를 리턴해요!

    #특정 index의 Node 뒤에 새로운 Node를 붙이는 함수
    def add_node(self, index, value):
        new_node = Node(value) # 일단 새로운 값을 기준으로 새 노드를 만들어요!
        if index == 0: # 0번째에 추가를 하고 싶다면!
            new_node.next = self.head # 원래 Head였던 노드를 새 노드의 next로 지정해요!
            self.head = new_node # 그리고, Head를 새 노드로 바꾸어줍니다!
            return

        # [3] - [4] - [5]에서 [3] - [4] - [6] - [5]로 6을 중간에 넣는다고 할게요!
        # 추가하고 싶은 index의 이전 노드 정보를 갖고옵니다! 여기선 [4] 입니다.
        node = self.get_node(index - 1) 
        # 1. 이전 노드([4])의 포인터([5])를 next_node로 임시 저장해요!
        next_node = node.next
        # 2. 이전 노드([4])의 포인터를 [6]으로 지정합니다!
        node.next = new_node
        # 3. 새로 삽입한 노드([6])의 포인터를 next_node인 [5]으로 지정합니다!
        new_node.next = next_node

 

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

트리

• 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조. [네이버 지식백과]
• 데이터들이 순차적으로 나열된 것이 아니라 계층적 혹은 망으로 구성되어 있어 표현에 초점이 맞춰져 있다.
• 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식만을 가지는 트리
• 완전 이진 트리(Complete Binary Tree): 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 하는 이진 트리
• 배열로 표현: 0번째 요소 None으로 시작하여 노드 위에서 부터 아래로, 왼쪽에서부터 오른쪽으로 쌓으면서 표현: [None, Root 노드, 자식 노드1, 자식 노드2, 자식 노드의 자식 노드1, ...]
• 최대 노드의 개수 N = 2^(h+1) -1  → h = log_2(N+1) - 1 →  이진 트리의 최대 높이: O(log(N))