패스트캠퍼스 환급챌린지 일차 미션 (2월 3일) : 딥러닝·인공지능 Signature 초격차 패키지 Online. 강의 후기

 

날씨가 무지 컴컴한데, 오늘은

 

Part1. 딥러닝을 시작하기전에

CH02-07. 덱

 

&

 

CH02-08. 이전 탐색 트리

 

 

 

CH02-07. 덱 

스택과 큐의 장점을 모두 가지고 있는 것으로써, 덱만 써도 된다고 한다.

 

■ 덱은?

"스택과 큐의 장점을 다 갖고 있지만 메모리가 더 많이 필요하다는 단점이 있다." 

특징 1: 포인터 변수가 더 많이 필요하기 때문에 메모리가 더 많이 필요하다

특징 2: 파이썬에선 기본적으로 큐의 기능을 제공하지 않기 떄문에 '덱' 라이브러리를 호출하여 쓰는 경우가 많다!

           (물론 큐 라이브러리도 제공하지만 일반적으로 덱을 사용하는경우가 더 많다.
            즉~! 큐 말고 덱을 더 자주 사용한다~)

특징 3: 빅오 상수시간만큼만 쓴다고 한다.( O(1))

특징 4: 양쪽에서 넣고 빼고를 할 수가 있다!(신세계!!)

 

 

자 그러면, 덱의 연산을 알아보자.

 

■  덱의 연산

1. 좌측 삽입(Append Left) / 덱의 가장 왼쪽에 새 데이터를 삽입

2. 좌측 삭제(Pop Left) / 덱의 가장 왼쪽에서 데이터를 추출

3. 우측 삽입(Append Right) /  덱의 가장 오른쪾에서 새 데이터를 삽입

4. 우측 삭제(Pop Right) / 덱의 가장 오른쪽에서 데이터를 추출

 

■  덱 + 연결리스트?

지난 시간에서 본 것처럼 스택과 큐처럼 덱도 연결리스트로 구현할 수 있는데,
덱은 위에서 본 것처럼 앞(front) 과 뒤(rear) 두개의 포인터를 가진다.

앞(front) : 가장 좌측에 있는 데이터를 가리키는 포인터

뒤(rear) : 가장 뒤쪽에 있는 데이터를 가리키는 포인터

넣거나 빼고는 큐와 유사하다.

 

■  좌측에다가 값을 삽입 할 때?

    1. 왼쪽에 값을 넣는다.

    2. 프론트 포인터가 가리키는 노드와 새로 들어온 노드를 상호간 연결한다. 

    3. 프론트 포인터를 새로들어온 노드(원소)로 바꿔주면 끝!

 

■  좌측에서 값을 삭제 할 때?

    1. 프론트를 다음 위치(다음 노드) 로 바꿔주기만 하면 끝!

 

■  Python에서 덱을 하용하는 경우?

 1. 앞서 말한 것처럼 기본적인 파이썬의 리스트 자료형은 큐의 기능을 제공하지 않는다.(가능하면 덱 라이브러리 사용)

 2. 삽입과 삭제에 대해 모두 시간 복잡도 O(1)이 요구된다.

append.left로 왼쪽에서 붙히기, 왼쪽에서 빼기, 좌우에서 하나씩 빼기

 

그러면 연결리스트에서 이 덱이 어떻게 사용이 될까?

 

 

 

CH02-08. 이진 탐색 트리

트리 자료구조의 가장 기본이 되는 것, 

 

■   탐색트리란?

"가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조." 

나무를 뒤집은 것 같이 생겨 트리라는 말이 붙었나?

특징 1. 루트노드(root node) : 부모가 없는 최상위 노드

         2. 단말 노드(leaf node) : 자식이 없는 노드, 즉 루트부터 타고 내려가서 자식이 없는 마지막 노드까지..그 떄의 노드

특징 2. 부모와 자식관계가 성립 / 그리고 형제 관계도 성립한다.

특징 3. 깊이(depth) : 루트 노드에서의 길이(length)
            아래 이미지 기준으로 볼때 트리의 높이는 2 이고, 30을 기준으로 볼때 23은 깊이 2, 17은 깊이 1이다.

            길이 : 출발 노드에서 목적지 노드 까지 거쳐야 하는 간선의 수

            높이 : 루트 노드에서 리프 노드까지의 거리

 

트리에 대한 개념도

 

 

■   이진 탐색 트리란?

특징 1: 왼쪽 자식노드 < 부모노드 < 오른쪽 자식 노드( 4, 7, 9) 

            이러한 성질을 보장한다. (이진  혹은 이분) 트리는 굉장히 효율적이다.

 

특징 2: 왼쪽 트리, 오른쪽 트리 모두 이진 트리라고 한다?

 

특징3. 삽입 연산

           ① 루트 노드에서 출발하여 아래쪽으로 내려오면서 삽입할 위치 탐색!

           ② 삽입할 노드의 키가 작으면 왼쪽으로, 삽입할 노드의 키가 크면 오른쪽으로 삽입

이진트리에 대한 개념도

 

 

특징3. 노드 5를 찾는다?
           7보다 커 작어? 4보다 커 작아? 두번만 하면 바로 찾아낸다.

 

특징4. 삭제를 한다?(삭제는 조금 복잡하다)

           - case1 : 왼쪽 자식이 없는 경우 → 오른쪽 자식으로 대체

           - case2 : 오른쪽 자식이 없는 경우 →  왼쪽 자식으로 대체

            -case3 : 왼쪽, 오른쪽 모두 있는 경우 →  오른쪽 서브 트리에서 가장 작은 노드로 대체 

 

예시1 : 7번을 삭제하고 싶다?!

          case3 인 경우이니까 오른쪽 서브트리, 즉 9가 가진 트리에서 가장 작은 노드이니 8을 대체.
          7의 위치에 8이 들어가고 9 밑에는 아무것도 안남는다.

 

 

예시2 : 4번을 삭제하고 싶다?!

            이것도 case3 인 경우이니, 오른쪽을 기준으로 가장 작은 원소는 5이다. 따라서

             4 위치에 5를 대체하고, 5 밑에는 6이 있는 형태가 된다.

 

 

예시3 : 3번을 삭제하고 싶다?!

            case 2(오른쪽 자식이 없는 경우) 2가 3의 위치에 가면 끝

 

 

특징5. 트리에 있는 정보를 출력하고자 할 때, 순회(traversal)을 사용한다.

           - 1. 전위 순회(pre-order traverse) : 루트방문 →  왼쪽자식 방문 →  오른쪽 자식 방문 

           - 2. 중위 순회(in-order traverse) :  왼쪽자식 방문 → 루트방문 →  오른쪽 자식 방문 

           - 3. 후위 순회(post-order traverse) :  왼쪽자식 방문 → 오른쪽 자식 방문 → 루트방문  

 

 

특징6. 레벨 순회

           - 가까운 것부터 층별로 나눈다.
           - A / BC / DEFG 순으로 확인한다.

 

 

 

 

3일차 끝.

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.

https://bit.ly/48sS29N