[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 7회차 미션

7. 다양한 링크드 리스트 구조

-> 더블 링크드 리스트 구조 : 노드의 구조가 기존의 링크드 리스트와 다르다

                            이전데이터 주소 + 노드 + 다음데이터 주소

-> 항상 앞에서부터 검색을 해야하는 링크드 리스트의 단점을 보완하기 위한 것

 

 

class Node:

    def __init__(self, data, prev=None, next=None):

        self.prev = prev

        self.data = data

          self.next = next

-> 더블 링크드 리스트 선언

 

class NodeMgmt:

    def __init__(self, data):

        self.head = Node(data)  //최초의 노드가 헤드가 된다

        self.tail = self.head   //헤드나 꼬리부분은 똑같다

 

    def insert(self, data): //삽입 함수 생성 앞에서부터 끝까지 검색하고 끝에 넣어

        if self.head == None:  //

            self.head = Node(data)  //head에 만들기

            self.tail = self.head  //tail에도 head 와 같은거 넣기

        else:

            node = self.head 

            while node.next:  //node 반복

                node = node.next 

            new = Node(data) //마지막 node를 가리킨다

            node.next = new

            new.prev = node

            self.tail = new

 

    def desc(self):

        node = self.head

        while node:

            print (node.data)

            node = node.next

 

double_linked_list = NodeMgmt(0)

for data in range(1, 10):

    double_linked_list.insert(data)

double_linked_list.desc()

-> 결과0 1 2 3 4 5 6 7 8 9

-> 더블 링크드 리스트의 코드 작성

연습 3 노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수 작성

-> 더블 링크드 리스트의 tail에서부터 뒤로 이동하며 특정 숫자인 노드를 찾는 방식으로 함수 구현

-> 테스트 : 임의로 0~9 까지 데이터를 링크드 리스트에 넣어보고 데이터값이 2인 노드앞에 1.5데이터값을 가진 노드를 추가하기

def search_from_head(self, data):  //헤드부터 검색하는 함수

        if self.head == None:   // 방어코드

            return False

   

        node = self.head

        while node:

            if node.data == data:

                return node

            else:

                node = node.next

        return False

   

    def search_from_tail(self, data):

        if self.head == None:

            return False

   

        node = self.tail

        while node:

            if node.data == data:

                return node

            else:

                node = node.prev

        return False

 

node_3 = double_linked_list.search_from_tail(3)

node_3.data

->3 출력

    def insert_before(self, data, before_data):

        if self.head == None:

            self.head = Node(data)

            return True

        else:

            node = self.tail

            while node.data != before_data:

                node = node.prev

                if node == None:

                    return False

            new = Node(data)

            before_new = node.prev

            before_new.next = new

            new.prev = before_new

            new.next = node

            node.prev = new

            return True

 

double_linked_list.insert_before(1.5, 2)

double_linked_list.desc()

-> 0 1 1.5 2 3 4 5 6 7 8 9

 8. 알고리즘 복잡도 표현 방법

 A. 알고리즘 복잡도 계산이 필요한 이유

-> 하나의 문제를 푸는 알고리즘은 다양할 수 있다

-> but 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해 복잡도를 정의하고 계산

 B. 알고리즘 복잡도 계산 항목

B-1. 시간복잡도 : 알고리즘 실행 속도

     주요 요소: 반복문이 지배  

    입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행시간을 지배

B-2. 공간복잡도: 알고리즘이 사용하는 메모리 사이즈

   C. 알고리즘 성능 표기법

      Big O ( 빅- 오) 표기법 : O ( N)

-      알고리즘 최악의 실행 시간 표기

-      가장 많이 일반적으로 사용

-      아무리 최악의 상황이라도 이정도의 성능은 보장한다는의미

Ω 오메가 표기법: Ω(N)

-      오메가 표기법은 알고리즘 최상의 실행시간 표기

θ 세타 표기법: θ(N)

-      세타 표기법은 알고리즘 평균 실행시간 표기

-> 시간 복잡도 계산은 반복문이 핵심 요소임을 인지했고 계산표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 공부해야겠다

 

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG