DAY 9. K 튜터님 자료구조_알고리즘 강의(2/3), 알고보면 알기쉬운 알고리즘 - 3

내배캠 4기 Node.js 트랙 9일차... 알고리즘 시작한지 4일차 속된말로 뒤질거같다ㅋㅋㅋㅋ (정신나감)

 

오늘은 진짜 의무감에 오늘 하루를 마무리 해본다.

 

오전은 K 튜터님의 자료구조_알고리즘 강의가 있었고, 오후 내내 (지옥같은) 알알알 3주차 강의를 봤다...

 

============================================================================================

- K 튜터님 자료구조_알고리즘 강의 2일차

• 시간 복잡도 : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 말하는데, 꼭 최악의 경우를 기준으로 계산해야한다.
• 공간 복잡도 : 문제를 해결하는데에 대한 공간(메모리)과의 상관관계를 말하는데, 공간 복잡도를 희생해서라도 시간 복잡도의 개선이 프로그래밍에 중요하다.
• 배열 : 연관된 데이터를 하나의 변수에 그룹핑해서 관리가능하다. 메모리에 연속적인 위치에 존재를 하여 하나의 변수에 여러 정보를 담을 수 있고, 반복문과 결합하면 많은 정보도 효율적으로 처리 가능하다. 조회(Read)에 큰 장점이 있다.
• 링크드리스 : 유동적으로 연결고리를 떼었다가 붙였다가 할 수 있는 자료구조이다. 원소의 삽입/삭제에 강점이 있다.  하지만 인덱스로 접근이 불가능해 조회에 취약하다. Head 노드부터 출발해서 포인터를 따라 순차적으로 이동하는 체이닝 기법이다.

• 노드 : 화물 칸들을 링크드리스트에서 노드라하며, 맨 앞의 노드를 Head, 맨 뒤의 노드를 Tail 이라고 한다.
• 포인터 : 현재 노드가 가리키는 다음 화물 칸

- 노드를 클래스로 정의(data(노드값), next(포인터) 정의 필수)

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

- 링크드리스트 자료구조 클래스 정의(head 정의 필수)

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

- 링크드리스트 끝에 새로운 노드를 추가하는 append 함수

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

- 원하는 위치의 노드를 찾아내는 get_node 함수

def get_node(self, index):  # 원래 강의노트에 작성된 코드를 그대로 가져왔어요!

    node = self.head  # 링크드리스트의 Head를 처음 노드로 지정합니다!

    curr_idx = 0  # 현재 순회하고 있는 index를 나타냅니다!
    # 현재 순회하고 있는 index가 원하는 위치보다 작다면 계속 루프를 돌아요!
    while curr_idx < index:
        # if node.next is None:
        #     print('올바른 인덱스를 입력하세요')
        #     return
        try:
            node = node.next  # 원하는 위치에 당도할 때 까지 다음 노드로 이동!
            curr_idx += 1  # 인덱스도 갱신!
        except:
            print('올바른 인덱스를 입력하세요')
            quit()

    return node  # 원하는 인덱스의 노드를 리턴해요!

- 원하는 위치에 새로운 노드를 추가하는 add_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
    try:
        # [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
    except:
        print('올바른 인덱스를 입력해주세요')
        quit()

- 종합

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


# # 3을 가진 Node 를 만드려면 아래와 같이 하면 됩니다!
# node = Node(3)  # 현재는 next 가 없이 하나의 노드만 있어요!


# 주의할 점은 노드를 만들 때 next까지 세팅을 하는 것이 아니에요!
# 이것은 링크드리스트 자료구조 클래스에서 해주는 역할인 것을 인지하셔야 합니다!

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:
            # if node.next is None:
            #     print('올바른 인덱스를 입력하세요')
            #     return
            try:
                node = node.next  # 원하는 위치에 당도할 때 까지 다음 노드로 이동!
                curr_idx += 1  # 인덱스도 갱신!
            except:
                print('올바른 인덱스를 입력하세요')
                quit()

        return 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
        try:
            # [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
        except:
            print('올바른 인덱스를 입력해주세요')
            quit()

    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

    def print_all(self):
        curr = self.head
        while curr is not None:
            print(curr.data)
            curr = curr.next


linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)
linked_list.append(6)

linked_list.add_node(4, 1)

linked_list.delete_node(2)

linked_list.print_all()

강사님께서 추가로 수정해보라는게 있었는데, 정확하게 어딘진 모르겠으나, 노드 삭제와 예외처리를 해서 엄한 index 를 추가하려고하면 "올바른 인덱스를 입력해주세요" 라고 출력되게 구성해보았다.

 

- 알알알 3주차 

https://icepri3535.tistory.com/69

[스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 3주차

알고볼수없어서 알기어려운 알고리즘이다. 

생존을 위해서 적당히 타협하려한다.

 

============================================================================================

오늘 하루 스트레스를 엄청 받고 삭히고 스트레스받고 풀고 스트레스받고 단념하는 하루였다.

오늘은 내가 졌다. 알고리즘 GG