2019.07.13 Tree

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 트리

1. 어떤 노드 간에 경로가 존재해야 한다.( 즉 연결이 되어 있어야 한다) - connected
2. 단 사이클이 없어야 한다 - acyclic
3. set안에 tree와 tree가 있으면 forest이다
4. 루트 노드가 없어지면 각각 분리집합으로 분할 가능

트리 용어

• 레벨와 트리의 높이가 같다고 하면 한쪽으로 굉장히 치우진 것과 같다.

엣지와 노드와의 관계

• MST : KRUSKAL 알고리즘 -> 도시계획
• CS/binary_tree.pdf at master · ythwork/CS

이진트리

이진트리의 특징

완전 이진 트리

추가 공부할 사항

• 포화 이진 트리
• 편향 이진 트리

이진트리의 순회

1. 스텍기반
   1. 전회순회
   2. 중위순회
   3. 후위순회
2. 큐 기반
   1. 레벨 순회

전위순회(pre order)

class TreeNode:
    def __init__(self, data):
        self.data=data
        self.left=None
        self.right=None

def preorder(node):
    #base case
    if not node:
        return

    #노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을 넣고 방문할 떄 마다 실행
    print(node.data, end = "  ")
    # 왼쪽 자식
    preorder(node.left)
    # 오른쪽 자식
    preorder(node.right)

if __name__ == "__main__":
    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n6 = TreeNode(6)
    n7 = TreeNode(7)

    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5
    n3.left = n6
    n3.right = n7

    preorder(n1)

중위순회(in order)

def preorder(node):
    #base case
    if not node:
        return


    # 왼쪽 자식
    preorder(node.left)

     #노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을         넣고 방문할 떄 마다 실행
    print(node.data, end = "  ")

    # 오른쪽 자식
    preorder(node.right)

후위순회 (post order)

def preorder(node):
    #base case
    if not node:
        return


    # 왼쪽 자식
    preorder(node.left)

    # 오른쪽 자식
    preorder(node.right)

     #노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을         넣고 방문할 떄 마다 실행
    print(node.data, end = "  ")

2019.07.13 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 자료구조

2. 자료구조는 데이터베이스에 어떻게 데이터를 담을 것인지에 대한 이론이다.

3. 서버 개발자로서 굉장히 중요한 부분이다.

1. 전체적인 흐름

1. 동적배열(Dynamic array) vs 연결리스트(linked list)
   2. insert, delete, search에 따라서 효율이 다름
2. BST(array list와 linked list의 단점 보완)
   2. insert, delete, search 모두 O(log(n))
   3. 트리의 깊이가 깊어지면 문제 발생
3. 레드블랙트리(red black tree)
   3. self-balancing 기능이 생기면서 BST문제 해결
4. B-Tree
   4. 캐시기능 추가 보완
5. B+Tree

동적배열 vs 연결리스트

1. 동적배열(파이썬에서는 list가 동적배열이다 - 따라서 append와 pop은 O(1) )
   1. 장점 : search - (O(1) : 인덱싱때문에)
   2. 단점 : Insert, delete : O(n) - 최악의 경우는 제일 앞에 것을 지우고, 삭제할 때이다. 하나씩 다 옴겨줘야 한다.
   3. 할당되어 있는 전체 크기가 capacity라고 하는데, 만약 특정 위치에 값을 넣거나 삭제하려고 하면 자리를 계속 옴겨야 한다.
   4. 만약에 capacity가 꽉 찼는데 append해야 한다면 amortized analysis (분할 상환 분석-뒤에서 참고)
   5. 예) 파이썬의 list
2. 연결리스트
   1. 장점 : insert, delete : O(1)
   2. 단점 : search : O(n)
   3. 예) 더미 더블링크드 리스트
3. 만약에 쓴다고 하면 동적배열을 써야 한다. 정말 배열이 붙어있어서 지역성으로 캐시가 발생할 확률이 높다. 하드웨어의 이점을 받을 수 있다.
4. 이거 2개를 보완해주는게 BST이다.

BST(이진탐색트리)

• 이진탐색트리
• 루트를 기준으로 왼쪽에는 항상 더 작은 자료가 위치하고 오른쪽에는 더 큰 자료가 위치한다.
• *insert, delete, search 모두 O(log(n))
• 아무리 많이 해도 트리의 높이(height of tree)만큼만 하면 된다.log(n)
• 트리에 있는 것은 파이썬에서 key값이라고 볼 수 있다.
  • dictionary이고 a collection of pairs(key, item)
  • 해당 key에 item을 참조하게만 해놓으면 문제해결

BST를 공부하기 위해서 기본적으로 Tree에 대해서 알아야 한다. Tree의 search, delete, insert에 대해서 공부해야 한다.

redblack tree

참고 : RedBlack Tree에 대해

• 7,6,5,4,3,2,1 순서대로 삽입해서 이진탐색 트리(Binary Search Tree)를 만들어 보면 위의 그림과 같이 한쪽으로 치우처진 tree가 완성된다.

1을 찾으려고 한다면?

• 항상 트리의 높이만큼 시간이 필요하다. 그렇다면 이진탐색 트리(Binary Search Tree)를 사용하는 이유가 없다.
• 이러한 문제점을 해결하기 위해 나온 자료구조가 Balanced binary search tree의 한 종류인 RedBlack Tree이다.

• 각 노드에 색깔을 저장하는 공간을 추가하여 색깔을 기준으로 균형을 맞추는 트리이다.

자세한 사항은 또 뒤에서 redblack tree만 다루어보자.

B TREE

참고 : B-Tree 개념 정리 | Jlog

• 기존에 tree에서 할 수 없었던 캐시를(지역성) 추가하여 보완

• 한 개의 노드에 여러개의 데이터가 들어갈 수 있다.
• 지역성 문제를 해결하여 훨씬 효율을 높였다.

자세한 사항은 B tree만 다룬다.

추가

분할 상환 분석(Amortized analysis)

• 등장배경: 우리가 짜는 함수의 경우는 빅오를 구하기에 굉장히 애매한 경우가 많다. 따라서 대략적으로 빅오를 구하는 방법
• DA(동적배열)에서 append를 할때 메모리(capacity)가 꽉 찬 경우
• 메모리(heap)을 돌아다니면서 가능한 공간을 찾아다닌다. 가능한 위치를 찾아서 복사해서 넣게 되면 최소한 O(n)
• heap이 linked list로 구성되어 있다.
• 해결방안
  • 우리가 아는 데이터의 갯수가 200개이면 키자마자 250개를 잡아 놓는다.
    • 만약에 3개만 쓰게 되면 굉장히 비효율적이다.
  • 한 개씩 늘리면서 모든 공간이 다 차게 되면 크기를 X2 한다.
• 가끔 한번씩 O(n)이 필요한데 그만큼 하고 나몬 지속적으로 O(1)이 되므로 이정도는 그렇게 치자.
• ex) 데이터의 갯수가 3개이면 4개면 된다.
• 이렇게 하면 캐시히트와 인덱싱을 유지할 수 있다.
• heap안에 찾아다니면서 2배 크기가 가능한 곳을 찾아다니는 것이다.

2019.07.04 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 정렬 O(nlogn) - 자료의 구조가 많아 질수록 정렬의 효율이 높아진다.

2. 퀵소트

3. 머지소트

1. 퀵소트

1. 하나의 스택프레임 안에서 conquer를 한 이후에 다시 호출 할 때 divide가 되는 것이다.
2. 파티션을 알고 있으면 좋다.
   1. 피벗을 기준으로 왼쪽에는 작은 값이, 큰 값은 오른쪽에 오도록 몰아버리는 것
   2. conquer이다.
3. pivot은 인덱스가 아니라 값이다.(처음 혹은 끝, 중간)
4. 재귀 함수 사용

def quick_sort(arr, start, end):
    #기저조건(base case)
    if start >= end:
        return

    left = start
    right = end
    pivot = arr[(left+right)//2] #정수형 나누기 해야됨

    #파티션
    #left와 right가 교차하기 전이라면 파티션을 계속 수행한다.
    while left <= right:
        #left가 언제 멈춰야 하나?
        while arr[left]<pivot:
            left+=1
        #right가 언제 멈춰야 하나?
        while arr[right]>pivot:
            right-=1

        # left와 right가 교차하지 않았다면 교환
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
            left+=1
            right-=1


    quick_sort(arr, start, right)
    quick_sort(arr, left, end)


if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6, 10, 8, 1, 3]
    start = 0
    end = 7
    quick_sort(arr, start, len(arr)-1)
    print(arr)

2. 머지소트

• 먼저 다 나누고 정렬을 한다.
• 하나 하나가 다 스택프레임으로 쌓인다.
• 다 나눈 이후에 왼쪽은 left 오른쪽은 right

def merge(arr, start, mid, end):
    left = start
    right = mid + 1
    temp = []  #로컬 베리어블이라서 업데이트 안하면 사라져버린다.


    # 둘 중에 하나라도 범위를 벗어나기 전가지
    while left<= mid and right <= end:
        if arr[left] <= arr[right]:
            temp.append(arr[left])
            left += 1
        else:
            temp.append(arr[right])
            right += 1

    #만약에 남아있는 것이 right라면
    #right를 돌면서 temp에에 넣는다.

    while right <= end:
        temp.append(arr[right])
        right +=1

    while left <= mid:
        temp.append(arr[left])
        left += 1

    # arr에 temp를 업데이트 하는 코드
    arr[start:end+1] = temp
    print(temp)


def merge_sort(arr, start, end):
    #base_case
    if start >= end:
        return

    mid = (start+end)//2

    #divide
    merge_sort(arr, start, mid)
    merge_sort(arr, mid+1, end)

    #conquer
    merge(arr, start, mid, end)


if __name__ == "__main__":
    arr = [3,6,9,1,3,5,7,8]
    start = 0
    end = len(arr)-1
    merge_sort(arr, start, end)
    print(str(arr))

2019.07.03 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 정렬 O(n2) - 그나마 제일 좋은것은 insertion이 제일 좋다.

2. 버블솔트

3. 삽입정렬

4. 선택정렬

1. 버블 솔트

• 일반적으로 for문이 2개면 n2이다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]


if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6]
    bubble_sort(arr)
    print(arr)

2. 삽입 정렬

• [5, 2, 6, 1, 8]
• 첫 번째 인덱스는 지나가고 2번 째 인덱스부터 temp에 넣어서 그 숫자를 첫 번째 인덱스부터 비교한다.
• i를 temp에 넣고, j는 i-1부터 인덱스를 줄여가며 temp와 비교한다. i의 앞쪽은 정렬되어 있을 것이기 때문에 그 해당 위치에 insert를 하는 것이기 때문에 insertion이다.
• insertion은 끝까지 다 비교하지 않아도 되기 때문에 bubble_sort보다 더 효율적이다.

while문을 통한 구현

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        temp = arr[i]
        j = i - 1
        while j!=-1:
            if arr[j] > temp:
                arr[j+1] = arr[j]
                j-=1
            else:
                break
        arr[j+1] = temp

if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6]
    insertion_sort(arr)
    print(arr)    

for문을 통한 구현

def insertion_sort(li):
    n=len(li)
    temp=None
    for i in range(1, n):
        temp=li[i]
        for j in range(i-1, -2, -1): #-2까지 해야지 -1까지 된다.
            if j==-1:
                break
            if li[j] > temp:
                li[j+1]=li[j]
            else:
                break
        li[j+1]=temp

if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6]
    insertion_sort(arr)
    print(arr)    

선택 정렬(selection)

• 첫 번째 인덱스에 적합한 가장 작은 값을 선택한다.
• 그리고 해당 인덱스를 첫 번째 인덱스와 바꾼다.
• i를 0부터 시작해서 일단 첫 번째 인덱스를 가장 작은 값으로 가정하고 시작
• 바깥 포문은 제일 마지막꺼 전 까지만 돌면 되므로 n-2까지
• 안 쪽 포문은 i+1부터 n-1(끝까지)

def selection_sort(arr):
    n = len(arr)

    for i in range(0, n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6]
    selection_sort(arr)
    print(arr)

2019.07.02 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 원형규

1. circular queue(원형큐)
   1. 크기가 정해져 있는 배열!! or linked list로도 만들 수 있다.
   2. head, tail
   3. 배열, head, tail 만 있으면 구현할 수 있다.
2. 구현 특징
   1. 핵심포인트 : 텅빈 큐를 어떻게 표현할 것이냐?/ tail이 인덱스를 벗어낫을 떄 어떻게 처리할 것인가?
   2. 텅빈 큐는 head == tail 이면 비었다고 표현한다.
   3. full은 한 칸을 버리지만 tail + 1을 했을 때 h면 full로 표현한다.
   4. tail은 마지막 데이터의 다음을 가르키게 구현을 한다.
3. 큐사이즈는 정해주거나, 작은 숫자를 바탕으로 테스트하면 좋다.

class CQueue:
    #모든 인스턴스가 필요하면 클래스 멤버로 선언

    MAXSIZE = 10

    def __init__(self):
        #리스트 컨프렌션
        self.__container = [None for _ in range(CQueue.MAXSIZE)]
        #인포메이션 하이딩
        self.__head = 0
        self.__tail = 0

    def is_empty(self):
        if self.__head == self.__tail:
            return True
        return False

    def is_full(self):
        next = self.__step_forward(self.__tail)
        if next == self.__head:
            return True
        return False

    def enqueue(self, data):
        if self.is_full():
            raise Exception("The queue is full")

        self.__container[self.__tail] = data
        #tail은 마지막 데이터의 다음을 가르킨다.
        self.__tail = self.__step_forward(self.__tail)

    def dequeue(self):
        if self.is_empty():
            raise Exception("The queue is empty")

        result = self.__container[self.__head]
        self.__head=self.__step_forward(self.__head)
        return result

    def peek(self):
        if self.is_empty():
            raise Exception("The queue is empty")
        return self.__container[self.__head]

    # 편의함수
    def __step_forward(self, x):
        x+=1
        if x >= CQueue.MAXSIZE:
            x = 0
        return x

if __name__ == "__main__":
    cq = CQueue()

    for i in range(5):
        cq.enqueue(i)

    while not cq.is_empty():
        print(cq.dequeue(), end = "   ")

2019.04.12 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 자료구조

자료구조에 대한 정의는 너무나도 많다.
그 중에 가장 마음에 와닿는 글이 있어서 정리를 해본다.

" 프로그래밍은 결국 데이터를 다루는 방법입니다. 데이터를 입력받고, 데이터를 처리하여 도출된 데이터를 출력합니다.

자료구조는 데이터를 입력 받아 어떻게 저장하는 지에 대한 학문입니다.
데이터를 어떻게 저장하는지(입력), 어떻게 찾는지(탐색), 어떻게 지우는지(삭제)가
자료구조의 종류에 따라 천차만별입니다.

그럼, 어떤 자료구조를 언제 사용해야 할까요? 이는 결국 성능과 효율적인 메모리 사용에 달려있습니다.
프로그래머가 처한 상황에서 가장 뛰어난 성능을 내고 또 가장 효율적으로 메모를 사용한다면 그 자료구조를 선택하면 됩니다.

알고리즘은 방법론입니다. 많은 알고리즘이 있지만, 자료구조에 연관된 알고리즘만 언급하겠습니다.
자료구조와 알고리즘은 매우 밀접한 연관을 가지고 있습니다. 위에 언급한 삽입 정렬과 병합 정렬은 엄밀히 말해 알고리즘입니다. 하지만 자료구조를 배울 때 반드시 마주치게 되지요. 알고리즘은 자료구조를 구현하는 방법이라고 보시면 될 것 같습니다. "

“프로그래머가 갖추어야 할 ‘기본’은 무엇인가?” 넥슨 개발자 컨퍼런스(NDC) 참관 후기 | 패스트캠퍼스

자료구조의 구성

1. insert : 어떻게 데이터를 넣을 것인가?
2. search : 어떻게 데이터를 찾을 것인가?
3. delete : 어떻게 데이터를 삭제할 것인가?

자료구조의 분류

• 단순구조 : 프로그래밍에서 사용되는 기본 데이터 타입
• 선형구조 : 저장되는 자료의 전후관계가 1:1 (리스트, 스택, 큐 등)
• 비선형구조 : 데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프 등)
• 파일구조 : 서로 관련된 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조
• 출처 : 강의노트 17. 알고리즘, 자료구조 개요 · 초보몽키의 개발공부로그

선형구조(배열과 linked list 그리고 스택과 큐)

1. 배열(array)
   1. 같은 자료형의 변수를 모아 놓은 것
   2. 인덱싱 활용 가능(search)
      1. 검색으로 배열을 이길 수는 없다.
   3. 데이터가 군집화 되어있다.
      1. 캐시히트의 가능성이 높다.
   4. 검색속도가 그 어떤 자료구조보다 빠르다.O(1)
   5. 데이터의 삽입과 삭제가 느리다. 최악의 경우 O(n)
      1. 맨 앞에 데이터를 삽입하게 되면 모든 데이터를 복사해서 한칸씩 다 옴겨야 한다.
      2. 배열은 공백을 인정하지 않는다. O(n)
2. Linked list ( 데이터의 삽입과 삭제가 많고, 검색이 별로 없을 때)
   1. 검색 속도 최악 O(n)
   2. 데이터의 삽입과 삭제는 O(1)
      1. 어디든 데이터를 놓고 연결만 해주면 된다.
   3. 데이터가 흩어져 있다.
      1. 캐시히트의 가능성이 굉장히 떨어진다. -> 캐시미스 발생
      2. 페이지폴트까지 날수도 있다.
   4. 미리 힙을 주고 흩어져 있는 문제를 해결할 수 있다.
      1. 다이나믹 힙
3. Stack
   1. 무언가를 쌓는다라는 의미를 가진 자료구조이다.
   2. LIFO(Last in, First out) : 후입선출
4. Queue
   1. 우리의 일반적인 줄서기
   2. FIFO(First in, First out) : 선입선출

만약에 배열과 Linked list 2개 다 사용가능한 상황이면 무조건 배열을 쓴다.
배열은 메모리의 스택에 할당해서 사용한다.

파이썬에서의 list

파이썬의 list는 배열과 다르다.
파이썬은 포인터 배열이다.
포인터는 배열처럼 일렬로 되어 있으나, [1,2,3]
1은 class int 여서 상수객체이기 때문에 4바이트보다 훨씬 크다.

파이썬의 리스트는 파이썬에서는 같은 자료형의 변수를 모아 놓은 것이 아니다.
파이썬에는 배열이라는 자료구조가 없는 것이다. 즉 지원하지 않는다.

예시

얕은 복사

>>>    #얕은 복사
>>>    li = [1,2,3,4]
>>>    li3 = li.copy() # or copy.copy(li)도 가능
>>>    li3     #[1,2,3,4]
>>>    li3.append(5)
>>>    li3      #[1,2,3,4,5]
>>>    li       #[1,2,3,4]
>>>

위의 내용을 이해하기 위해서는 단순히 객체가 [1,2,3,4]의 형태처럼 메모리에 올라가 있다고 생각하면 안된다.
실제적으로 파이썬에서 list를 생성한다고 하더라도 모두 모여서 메모리에 올라가지 않는다. [* , * , * , * ]와 같은 형태로 생성되어 첫번째 * 은 1을 가르키고 두 번째 * 은 2를 가르키고 이런 형식이다. 얕은 복사는 [* , * , * , * ]를 복사해 온 것이다. 따라서 li3는 li의 [* , * , * , * ]를 복사해온 것이다. 따라서 li3에서 append를 통해 새로운 요소를 추가하게 되면 li3의 [* , * , * , * ]가 [* , * , * , * , * ]가 되어서 마지막 * 가 새로운 요소를 가르키게 된다. 따라서 li3가 변경되더라도 li는 변경되지 않는다.
하지만 여기에서도 예외는 있다.

>>>    #얕은 복사
>>>    li = [1,2,3,[4,5]]
>>>    li3 = li.copy()
>>>    li3    #[1,2,3,[4,5]]
>>>    li3[3].append(6)
>>>    li3    # [1,2,3,[4,5,6]]
>>>    li     # [1,2,3,[4,5,6]]
>>>

위에서 보면 알 수 있듯이 원래 얕은 복사에서라면 li3를 바꾼다고 해서 li가 바뀌어서는 안된다. 하지만 li는 변경되었다. 그렇다면 li3는 왜 변경되었을까? 위에 언급한대로 li3는 li의 [* , * , * , * ]를 복사해 온 것이다. 위에 예시에서 마지막 * 은 3번째 인덱스 [4,5]을 가르키고 있다. li3와 li 모두 [4,5]을 가르키고 있는 것이다. 따라서 li3를 통해 [4,5]를 변경하게 되면 마지막 *가 가르키는 것이 변경되는 것이므로 li 역시 변경되게 된다.(즉 li와 li3의 내부리스트는 각은 객체를 참조하기 떄문이다.)

이러한 것을 맡기 위해서는 깊은 복사가 필요하다.

깊은 복사

>>>    import copy     #deepcopy를 위해서는 copy를 import 해주어야 한다.
>>>    li = [1,2,3,4]
>>>    li4 = copy.deepcopy(li)
>>>    li4        # [1,2,3,4]
>>>    li4.append(5)
>>>    li4        # [1,2,3,4,5]
>>>    li         # [1,2,3,4]
>>>    li = [1,2,3,[4,5]]
>>>    li4 = copy.deepcopy(li)
>>>    li4        # [1,2,3,[4,5]]
>>>    li4[3].append(6)
>>>    li4        # [1,2,3,[4,5,6]]
>>>    li         # [1,2,3,[4,5]]

깊은 복사를 통해서는 완전히 동일한 새로운 객체를 생성하는 것이므로 li4에 어떤 요소를 추가해도 li는 전혀 영향을 받지 않는다. 따라서 상황에 맡게 단순 객체 복사, 얕은 복사, 깊은 복사를 사용해야 한다.

참고 : 2019_03_23_TIL(깊은 복사 얕은 복사)

비선형구조

트리

• connected acyclic graph
  • 사이클(순환)이 없는 연결된 그래프
  • 루트노드(root)를 반드시 가진다.
  • 트리를 구성하는 노드 간에 단순 경로가 반드시 존재한다.
    • 단순경로란 지나왔던 접점을 다시 지나지 않는 경로
    • 한 개의 노드에서 다른 한개의 노드를 선택하면 단순 경로가 항상 존재
  • 루트 노드를 제외한 나버지 노드들은 분리집합으로 분할이 가능하며 이 집합들은 각각 하나의 트리를 구성한다(재귀적 정의)

트리 용어 정리

부모노드와 왼쪽 자식노드 , 오른쪽 자식노드로 나누어짐

• 루트노드 : 뒤로 뒤집어서 보면 여기서부터 쭉 퍼져나가므로 root(뿌리) 노드이다. 트리의 시작점
• 에지 : 노드를 연결하는 선
• 리프노드 : 자식노드가 하나도 없는 노드
• 인터널노드 : 자식노드가 하나라도 있는 노드
• 차수 : 자식노드의 갯수
• 트리의 차수 : 트리에 있는 노드들 중 최대 차수

이진 트리

• 어떤 노드의 자식 노드의 수가 최대 2개인 트리

이진 트리의 종류

• 포화 이진 트리
  • 모든 레벨이 꽉 차 있다.
  • 즉 모든 노드들의 2개의 자식노드를 가지고 있다.(리프노드 제외)

• 완전 이진 트리
  • 트리의 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 채워지는 트리
  • 가장 높은 레벨 단계에서 항상 왼쪽에서 오른쪽으로 채워져 있어야 한다.

트리의 순회는 다음 장에서 추가로 공부한다!

• 순회란 트리의 모든 노드를 중복하지 않으면서 방문하는 것을 말하며, 데이터를 찾고, 저장하고, 삭제하는데 쓰인다.

2019.04.09 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 데이터 베이스

mysql은 관계형 데이터 베이스이다.
관계형 데이터 베이스 시스템들은 SQL 문법을 사용한다.

• nosql : 빅데이터와 같이 큰 데이터가 늘어나면서 관계형 데이터가 한계가 있다고 생각

DATABASE SERVER

server이기 때문에 앞으로 들어나지 않는다.
database server밑에서 여러개의 database가 있을 수 있고
database 밑에서는 여러개의 table이 있다.
그 안에 DATABASE가 있다.

database

1. oracle이 1위 회사이다.
2. 중소기업은 mysql —> php와 너무 잘 맞다. APM(apach, php, mysql)
3. MariaDB
   django
4. postgreSQL —> open source

database는 table이라는 것을 카테고라이징 한 것이다.

• table은 entity 혹은 relation이라고 부른다.
• 열은 column 혹은 field라고 부른다.
• 행은 row 혹은 tuple이라고 부른다.(파이썬의 자료형 tuple과 동일하다)
• 또한 이 row 한 줄을 recode라고 한다.
• 레코드는 구체적인 데이터를 이야기한다.

기본적으로 행과 열을 통해서 데이터베이스에 접근한다.

DATABASE CLIENT

mysql-client
phpmyadmin
mysql query browser
navicat

• 참고사항
• utf-8 mb4 (unicode utf-8)의 의미
  • a,b,c —> 1byte
  • 한글 —> 3byte
  • 어차피 3바이트까지 하면 되는데 굳이 4바이트까지 써야하나?
  • 따라서 자체적으로 3바이트로 만들었는데
  • 이모티콘이 나오면서 4바이트로 바꿈(utf-8 mb4)

시작하기

students

• student ID - int, primary key(테이블에서 오직 하나)
• height
• score
• birthday
• class ID - int, NULL

teacher

• teacher - int, primary key
• subject - varchar(가변)/ not null
• class id - int, NULL

server start

mysql.server start
mysql -u root

• mysql -u root ===> connection이 연결 TCP 연결(socket으로 연결이 둟린 것이다.)
• 이것을 session이라고 한다. TCP 연결을 했다.
• client는 여려명일 수 있다. john, greg 등
• 쓰레드의 가장 큰 문제점 : 레이스 컨디션
  • 여러명이 접속하게 되면 table이 shared resource가 된다. (공유자원)
  • updata문을 통해서 balance 값을 5000원에서 3000원으로 바꾸면서 끊김
  • 무결점을 보장해줘야한다.
  • 그렇기 때문에 session을 연 다음에 update를 하는 순간 그 쓰레드에 대해서만 복사해서 준다.
  • 트랜젝션을 업데이트를 한 다음에 commit을 통해 트랜젝션을 끝내고 데이터 베이스를 바꿈.
  • commit전에는 절대 데이터 베이스는 바뀌지 않는다. 무결성
  • 트랜젝션과 세션의 차이를 잘 알아야 한다.
  • Do it! 오라클로 배우는 데이터베이스 입문 - 이지훈 - Google 도서

유저확인

SELECT USER, HOST FROM USERS;

유저 생성 및 비밀번호 설정

CREATE USER “byeonguk”@“localhost” IDENTIFIED BY "1234";

권한 주기

GRANT ALL PRIVILEGES ON *.* TO "byeonguk"@"localhost" with grant option;

권한 적용

FLUSH privileges

권한 확인

SELECT USER, HOST, SUPER_PRIV FROM MySQL.USER;

데이터 삭제 혹은 테이블 삭제

DROP DATABASE mydb;
DROP TABLE 테이블명

테이블에 대한 정보 확인

SHOW tables

• 테이블 리스트 확인
  SHOW CREATE table "테이블 명"
• 해당 테이블에 대한 정보
  DESC "테이블 명";
• 해당 테이블 스키마 열람
• 스키마란 : 테이블에 적재될 데이터의 구조와 형식을 정의 하는 것
  SELECT * FROM "테이블명"
• 우리가 찾던 그 정보확인

테이블 생성

CREATE TABLE students(
-> student ID INT AUTO_INCREMENT, 
-> studentName VARCHAR(20)  #학생의 이름이 20바이트까지 가능
-> height SMALLINT DEFAULT 200,
-> score, SMALLINT NULL,
-> birtyday DATE NOT NULL,
-> classID INT NULL,
-> PRIMARY KEY(studentID),                    # 오직 한개만 있다
-> FOREIGN KEY(classID), REFERENCES classes(classID) 

• classID라는 외래키 참조하는데 classes 열에서 classID를 참조한다.
• 잘못되었을 때 \c를 하면 빠져나올 수 있다.

CREATE TABLE teachers (
->teacherID INT AUTO_INCREMENT NOT NULL,
->subject VARCHAR(30) UNIQUE,
->classID INT NULL,
->PRIMARY KEY(teacherID),
->CONSTRAINT fk_classID
->FOREIGN KEY (clastsID) REFERENCES classes (classID)
);

데이터 삽입

INSERT INTO students 
-> (studentName, height, scores, birthday, classID)
-> VALUES
-> (‘GREG’, 180, 87, ‘2002-3-23’, 1)

칼럼(열)더하기

DESC teacher;        #직관적으로 현 상황을 볼 수 있음

ALTER TABLE teachers
-> ADD COLUMN teacherName ;

SHOW CREATE TABLE teacher;          #해당 테이블에 대한 정보 제공(create할 때의 정보)

백업하기

mysqldump -u root -p —databases 
mydb > mydb1.sql
#mydb1.sql이 생김

카피하기

CREATE TABLE student_cp
-> (SELECT * FROM students); 

SELECT * FROM student_cp  #잘 복사되었는지 확인

데이터 업데이트하기

UPDATA student_cp
-> SET score = 100
-> WHERE studentName = ‘Mary’;             #Mary를 해주지 않으면 전부 다 100으로

메리 점수만 확인하기

SELECT studentName, score FROM student_cp
->WHERE studentName like ‘Mary’;
# WHERE studentName like "Ma%"; 
# %는 어떤 글자든지 다 소화시켜준다.

데이터 베이스에 조건문 넣기 (50점 이상 70점 이하 점수 보기)

SELECT studentName, score
-> FROM student_cp
-> WHERE score > 50 and score < 70

특정 데이터 지우기

Delete from student_cp
-> WHERE studentName like “Mary’;

SELECT * FROM student_cp (확인)

foreinkey 없애기

foreinkey를 없애려면
자동으로 인덱스를 잡기 때문에

폴인키 제약조건을 없앤 다음에 쇼 인덱스를 해준 다음에 잡혀있는 인덱스를 없애준다.

1)
ALTER TABLE teachers
-> DROP FOREIGN KEY teachers;

2)
DROP INDEX classID
-> ON teachers;

SHOW CREATE TABLE teachers      #확인

JOIN

join은 테이블을 가로로 연결할 때 쓴다.

• inner join
• outer join
  • left outer join
  • right outer join
  • full outer join
    • mysql, mariadb는 full outer을 지원하지 않는다.
    • 필요할 때 union을 통해 구현한다.

MySQL full outer join : 네이버 블로그

INNER JOIN

ex) join 예시
student name / score / class id / teacher name / subject
==> class id로 묶는다.( class id에 대한 교집합)

NULL을 어떻게 처리할 것인가?

• inner은 빠진다.

if select studentname, classid, teacher 이렇게 하면 classid가 누구것인지 알수가 없다.

S.를 붙여 student 표현 T.를 붙여 teacher 을 표현

• 적용 방법
  • SELECT S.studentsName,S.score, S.classID, T.teacherName, T.subject
  • FROM students S INNER JOIN teachers T (student가 left teacher가 right)
  • ON S.classID = T.classID
  • ORDER BY S.classID

LEFT OUTER JOIN ( 왼쪽에 위치한 집합은 다 나온다.)

SELECT S.studentName, S.score, S.classID,
    -> T.teacherName, T.subject
    -> FROM students S LEFT OUTER JOIN teachers T
    -> ON S.classID = T.classID

RIGHT OUTER JOIN (오른쪽에 위치한 집합은 다 나온다.)

SELECT S.studentName, S.score, S.classID
    -> T.teacherName, T.subject
    -> FROM students S RIGHT OUTER JOIN teachers T
    -> ON S.classID = T.classID;

FULL OUTER JOIN

SELECT S.studentName, S.score, S.classID
    -> T.teacherName, T.subject
    -> FROM students S LEFT OUTER JOIN teachers T
    -> ON S.classID = T.classID
    -> UNION
    -> SELECT S.studentName, S.score, S.classID
    -> T.teacherName, T.subject
    -> FROM students S RIGHT OUTER JOIN teachers T
    -> ON S.classID = T.classID;

GROUP BY

• 전체 평균
  • SELECT AVG(score) FROM students;
• 반별로 평균을 알고 싶다.
  • SELECT classID, AVG(score)
  • -> FROM students
  • -> GROUP BY classID
• 만약에 반 배정 안 받는 애들은 빼고 싶다.
  • SELECT classID, AVG(score)
  • -> FROM students
  • -> WHERE classID IS NOT NULL
  • -> GROUP BY classID;
• 평균 65점 이상인 반을 본다.
  • SELECT classID, AVG(score)
  • -> FROM students
  • -> WHERE classID IS NOT NULL
  • -> GROUP BY classID
  • -> HAVING AVG(scores) > 65;

WHERE 와 GROUP BY, HAVING

WHERE와 ==> 그룹을 하기 전에 조건절 수행
GROUP BY
HAVING의 차이 ==> 이미 그룹바이로 그룹이 끝난 이후에 조건절 수행(반듯이 그룹을 한 것에 대해서만 조건절을 수행한다)

M : N

• INNER JOIN을 2개 사용한다.
  ex) Student와 subject와의 관계

• VARCHAR 와 CHAR의 차이 : 비트를 고정해줄 것인가? 아니면 유동적으로 할 것이냐?

CREATE TABLE subjects(
    -> subjectName CHAR(20) UNIQUE NOT NULL,     #unique not null은 프라이머리 key가 없으면 생성한다.
    -> roomNum TINYINT NOT NULL);
INSERT INTO subjects 
(subjectName, roomNum) 
VALUES ('math', 101), ('literature', 105), 
('science', 107), ('english', 110), ('ethics', 111);

학생 입장에서 subject name + 강의실 번호까지

sql> SELECT ST.studentName, ST.score, 
SB.subjectName, SB.roomNum
FROM students ST INNER JOIN student_subject SS
ON ST.studentName=SS.studentName
INNER JOIN subjects SB
ON SS.subjectName=SB.subjectName
ORDER BY ST.studentName;

과목 입장에서 배열

sql> SELECT SB.subjectName, SB.roomNum, 
ST.studentName, ST.score 
FROM students ST INNER JOIN student_subject SS 
ON ST.studentName=SS.studentName 
INNER JOIN subjects SB 
ON SS.subjectName=SB.subjectName 
ORDER BY SB.subjectName;

SELECT의 순서가 바뀌는 것은 크게 의미가 없고
마지막에 ORDER BY에 따라서 정렬 순서를 정해준다.

SQL

• VIEW
• INDEX
  • CLUSTERED INDEX
  • SECONDARY INDEX

VIEW

VIEW는 select문이다.
view를 마치 테이블처럼 사용한다.

1. view는 select문일 뿐이지 테이블이 새로 만들어지는 것이 아니다.
2. 가독성이 높아진다.
3. 보안문제 해결

ex) 쇼핑몰
customer / 생년 월일 /

• 알바생에서 customer 테이블을 그대로 보여주면 안되니깐 view(생년월일이 없는)를 하나 만들고 권한을 부여(GRANT)

CREATE VIEW

CREATE VIEW view_st_sb_join 
AS 
SELECT ST.studentName, ST.score,
SB.subjectName, SB.roomNum  
FROM students ST INNER JOIN student_subject SS 
ON ST.studentName=SS.studentName 
INNER JOIN subjects SB 
ON SS.subjectName=SB.subjectName 
ORDER BY ST.studentName;

WHERE 적용 가능

SELECT * FROM view_st_sb_join;

sql> SELECT * FROM view_st_sb_join 
WHERE score BETWEEN 50 AND 70;

DROP VIEW 적용 가능

DROP VIEW view_st_sb_join;

INDEX

index를 쓰는 이유 <-- 데이터 검색

Tree BST --> o(log n)
단점 보완 -> red - black - tree (균형 이진 트리) 추가 단점 보완 => B-tree

• CLUSTERED INDEX

  • 한 테이블마다 1개씩만 존재한다.
  • 데이터 자체를 클러스트 인덱스에 맞추어서 정렬한다.
  • primary key가 클러스트 인덱스가 된다.
  • primary key를 안 잡고 데이터를 넣은 뒤 primary key를 잡으면 나중에 굉장히 정렬하는 시간이 오래 걸릴 수 있다. ==> 항상 미리 잡고 시작하자.

• SECONDARY INDEX

  • 원하는만큼 붙일 수 있다.
  • B-트리라는 자료구조를 만들고 실제 데이터를 참조해서 만든다.
    • where 에 쓰인다. ex) where classID = 3
    • secondary index를 언제만드냐?
      • where가 자주 쓰일 때 만들어 놓으면 search를 할 때 secondary index를 활용하여 서치
      • 쓰는 이유 : 검색 속도가 엄청나게 빨라진다.
      • 단점 : 테이블에 대해 insert를 계속하고 업데이트를 계속한다고 하면 계속 B-tree도 업데이트 시켜줘야하고, 수정, 삽입 등이 많이 늘어나면 페이지 분할이 일어나서 속도가 늦어질 수 있다.
      • where을 내가 얼마나 쓸 것인지 파악하고, 내가 수정 삽입 등을 얼마나 할 것인지 고민
  • CREATE INDEX는 secondary index만 만들 수 있다.
  • cluster int를 만들기 위해서는 ALTER TABLE이라는 커맨드를 써야한다.

참고사항

내부 스키마 외부 스키마 개념 스키마
[DB기초] 스키마란 무엇인가?

2019.04.01 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 자료구조의 큰 틀에 대해 이야기하기

자료구조

자료구조는 메모리에 data를 어떻게 저장할 것인가에 대한 고민부터 시작된다.
list, tuple, dictionary 모두 자료구조의 한 형태이다

자료구조는 딱 3가지이다.

1. 데이터를 어떻게 삽입할 것인가?(insert)
2. 데이터를 어떻게 검색할 것인가?(search)
3. 데이터를 어떻게 삭제할 것인가?(delete)

ADT(abstract data type) : 추상 자료형

자료 구조에서 삽입, 탐색, 삭제 등을 담당하는 함수들의 사용 설명서

1. 어떤 자료구조가 가지고 있는 오퍼레이션(함수)의 나열(목록)
2. 함수 시그니처(인터페이스)만 나열할 뿐, 내부 구현은 표기하지 않음
3. 함수(operation)의 작동 방식 설명.

ex)

>>>    help(list.append)
help on method_descriptor:

append(...)
    L.append(object) -> None
>>>

우리는 여기에서 append함수가 어떻게 구현되었는지 알 수 없다. 하지만 append함수를 사용하는 것에는 전혀 문제가 없다. 이러한 특징을 인터페이스와 구현이 분리되었다고 하며 추상화라는 표현을 쓴다.

linked List

데이터와 참조로 구성된 노드가 한 방향 혹은 양방향으로 쭉 이어져 있는 자료구조

• single linked list
• double linked list

노드

자료구조를 구현할 때 데이터를 담는 틀

• 노드는 저장할 데이터와 다음 노드를 가르키는 참조로 이루어져 있다.(단일 연결리스트)
• double linked list에서는 다른 형태의 노드가 활용된다.

single linked list

single linked list에서의 노드 구현

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


# 소멸자
# 객체가 사라지기 전에 반드시 한번 호출하는 것을 보장한다.
# 소멸자를 호출하고 지우는 것을 보장해준다.
# 실제 로드가 사라지는 것을 확인하기 위해서 가지고 옴
    def __del__(self):
        print(f'node[{self.__data}] deleted!')
        pass

    @property
    def data(self): 
        return self.__data

    @data.setter
    def data(self, data):
        self.__data = data

    @property
    def next(self):
        return self.__next

    @link.setter
    def next(self, next):
        self.__next = next

• 자료구조에서는 보안이 중요하므로 정보은닉 2가지를 모두 적용해주었다.
• 멤버 __data에는 데이터를 저장하고, 멤버 __ next는 다음 노드를 가르킨다.

single linked list의 인스턴스 멤버

1. head -> 리스트의 첫 번째 노드를 가르킨다.
2. d_size -> 리스트의 요소 개수이다.

single linked list의 ADT

1. S.empty() ---> Boolean

   • 리스트가 비었으면 True, 아니면 False

2. S.size() ---> integer

   • 리스트에 있는 요소 개수

3. S.add() ---> None

   • 노드를 리스트의 맨 앞에 추가

4. S.search(target) ---> node

   • 리스트에서 target을 찾는다.
   • 찾으면 노드를, 못 찾으면 None 반환

5. S.delete() ---> None

   • 맨 앞의 노드 삭제

single linked list 구현

class SLinkedlist:

    def __init__(self):
        self.head = None
        self.d_size = 0

    def empty(self):
        if self.d_size == 0:
            return True
        else:
            return False

    def size(self):
        return self.d_size

    def add(self, data):
        new_data = Node(data)
        new_data.next = self.head
        self.head = new_data
        self.d_size += 1

    def search(self, target):
        cur = self.head
        while != None:
            if cur.data == target:
                print(f"찾으신 데이터:{cur.data}가 있습니다")
                return cur
            cur = cur.next
        return None

    def delete(self):
        self.head = self.head.next

def show_list(sll):
    cur = sll.head
    for _ in range(sll.size()):
        print(cur.data, end=" ")
        cur = cur.next

if __name__ == "__main__"
    single = SLinkedlist()
    single.add(1)
    single.add(2)
    single.add(3)
    single.add(4)
    single.add(5)

    print(single.size())
    single.search(3)
    show_list(single)

    single.delete()
    show_list(single)

5
찾으신 데이터 3가 있습니다.
1 2 3 4 5
node[5] deleted!
2 3 4 5
node[4] deleted!
node[3] deleted!
node[2] deleted!
node[1] deleted!

Dummy double linked list

• dummy

  • 더미란 데이터를 가지지 않는 노드를 의미한다.
  • double linked list에서는 양 옆에 배치한다.

• 구현 이유

  • 더미가 있게 됨으로서 데이터가 있던지 없던지 상관없이 간단하게 데이터를 추가 삭제할 수 있게 되었다.원래는 뒤에 데이터가 있는지 앞에 데이터가 있는지 확인을 해야하지만 더미(head와 tail)이 있게 되므로서 상관하지 않고 구현할 수 있다.

double linked list 노드

Dummy double linked list instance Member

• instance member

  • head : 리스트 맨 앞에 있는 더미를 가르킨다.
  • tail : 리스트 맨 뒤에 있는 더미를 가르킨다.
  • d_size : 리스트의 요소 개수

• ADT

Dummy double linked list 구현

class Node:
    def __init__(self, data=None):
        self.__data = data
        self.__prev = None
        self.__next = None
        print(self)

    def __del__(self):
        print("data of {} is deleted".format(self.data))

    @property
    def data(self):
        return self.__data

    @data.setter
    def data(self, data):
        self.__data = data

    @property
    def prev(self):
        return self.__prev

    @prev.setter
    def prev(self, b):
        self.__prev = b

    @property
    def next(self):
        return self.__next

    @next.setter
    def next(self, n):
        self.__next = n

    def __str__(self):
        return f"created:[{self.__data}]"


class DoubleLinkedList:

    def __init__(self):
        self.head = Node()  
        self.tail = Node()
        self.d_size = 0

        self.head.next = self.tail
        self.tail.prev = self.head

    def empty(self):
        if self.d_size == 0:
            return True
        else:
            return False

    def size(self):
        return self.d_size

    def add_first(self, data):  
        new_node = Node(data)  
        new_node.next = self.head.next
        new_node.prev = self.head
        self.head.next.prev = new_node
        self.head.next = new_node
        self.d_size += 1


    def add_last(self, data):  # 항상 제일 앞에는 first가 있다고 가정한다.
        new_node = Node(data)
        new_node.next = self.tail
        new_node.prev = self.tail.prev
        self.tail.prev.next = new_node
        self.tail.prev = new_node
        self.d_size += 1

    def insert_after(self, data, node):
        new_node = Node(data)            
        new_node.next = node.next
        new_node.prev = node
        node.next.prev = new_node
        node.next = new_node
        self.d_size += 1

    def insert_before(self, data, node):
        new_node = Node(data)
        new_node.next = node
        new_node.prev = node.prev
        node.prev.next = new_node
        node.prev = new_node
        self.d_size += 1

    def search_forward(self, target):
        cur = self.head.next
        while cur is not self.tail:
            if cur.data == target:
                return cur
            cur = cur.next
        return None  

    def search_backward(self, target):
        cur = self.tail.prev
        while cur is not self.head:
            if cur.data == target:
                return cur
            cur = cur.prev
        return None


    def delete_first(self):
        if self.empty():
            return
        else:        
            self.head.next = self.head.next.next
            self.head.next.prev = self.head

        self.d_size -= 1

    def delete_last(self):
        if self.d_size == 0:
            return

        self.tail.prev = self.tail.prev.prev
        self.tail.prev.next = self.tail
        self.d_size -= 1

    def delete_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

        self.d_size -= 1

    # 편의 함수
    def traverse(self, start=True):
        if start:
            # 리스트의 첫 데이터부터 순회를 시작
            cur = self.head.next
            while cur is not self.tail:  # is는 객체 자체의 비교이다.
                yield cur
                cur = cur.next

        else:
            # 리스트의 마지막 데이터부터 순회
            cur = self.tail.prev
            while cur is not self.head:
                yield cur  # 만약에 아래 쪽에 node.data를 안했으면 cur.data해야 한다.
                cur = cur.prev


def show_list(d_list):
    g = dlist.traverse()
    for node in g:
        print(node.data, end=" ")
    print()


if __name__ == "__main__":
    dlist = DoubleLinkedList()
    dlist.add_first(1)
    dlist.add_first(2)
    dlist.add_first(3)
    dlist.add_first(4)
    dlist.add_first(5)

    show_list(dlist)

    # 데이터를 찾은 이유는 그 뒤에 데이터를 넣기 위해서
    searched_data = dlist.search_backward(3)
    if searched_data:
        # dlist.delete_node(searched_data)
        dlist.insert_before(15, searched_data)
        print(f"searched data:{searched_data.data}")
    else:
        print('기준 노드가 없습니다. 다시 확인해주세요.')

    show_list(dlist)
    # dlist.delete_first()
    # dlist.delete_last()
    del_data = dlist.search_forward(15)
    if del_data:
        # del_data가 15를 가르키고 있으므로 레퍼런스 카운터가 0이 안된다. 따라서 None을 해서 레퍼런스 카운터를 0으로 만든다.
        dlist.delete_node(del_data)
        del_data = None
    else:
        print("기준 노드가 없습니다. 다시 확인해주세요")
    show_list(dlist)
    print("*" * 100)
    # generator 객체


created:[None]
created:[None]
created:[1]
created:[2]
created:[3]
created:[4]
created:[5]
5 4 3 2 1 
created:[15]
searched data:3
5 4 15 3 2 1 
data of 15 is deleted
5 4 3 2 1 
****************************************************************************************************
data of None is deleted
data of 1 is deleted
data of 2 is deleted
data of 3 is deleted
data of 4 is deleted
data of 5 is deleted
data of None is deleted

• self를 앞에 붙이는 것은 무언가 지속적으로 남겨놓을 때 붙인다.
• 따라서 지속적으로 남겨놓을 필요가 없을 때는 붙이지 않는다.

2019.03.28 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. Stack 2개로 queue 구현하기

Stack와 Queue

• Stack과 Queue는 모두 컴퓨터 자료구조 방법론에 해당한다.

• Stack : LIFO (last in first out) 후입 선출

• Stack의 ADT (operation list , operation의 시그니처만 나열)

  1. S.empty() --> Boolean (스택이 비어있으면 True, 아니면 False)
  2. S.push(data) ---> None (스택의 맨 위에 데이터를 쌓는다.) None->무조건들어간다
  3. S.pop() ---> data (스택 맨 위의 데이터를 삭제하면서 반환)
  4. S.peek() ---> data (스택 맨 위의 데이터를 반환)

• Queue : FIFO (first in first out) 선입 선출

• Queue의 ADT (operation list , operation의 시그니처만 나열)

  1. Q.empty() —> Boolean (큐가 비어있으면 true, 비어있으면 False)
  2. Q.enqueue(data) —> None (큐의 맨 뒤에 데이터를 쌓는다.)
  3. Q.dequeue(data) —> data (큐의 맨 앞에 데이터를 삭제하면서 반환)
  4. Q.peek() —> data (큐의 맨 앞의 데이터를 반환)

Stack의 ADT 구현

• ADT 구현

>>>class Stack:
>>>    def __init__(self):
>>>        self.container=list()
>>>
>>>    def empty(self):
>>>        if not self.container:
>>>            return True
>>>        else:
>>>            return False
>>>
>>>    def push(self, data):
>>>        self.container.append(data)
>>>
>>>    def pop(self):
>>>        return self.container.pop()
>>>
>>>    def peek(self):
>>>        return self.container[-1]

위와 같이 스택의 ADT를 표시할 수 있다.

Queue의 ADT 구현

• ADT 구현

>>>class Queue:
>>>
>>>    def __init__(self):
>>>        self.container = list() 
>>>    
>>>    def empty(self):
>>>        if not self.container:
>>>            return True
>>>        else:
>>>            return False
>>>    def enqueue(self, data):
>>>        self.container.append(data)
>>>
>>>    def dequeue(self):     
>>>        return self.container.pop(0)
>>>
>>>    def peek(self):
>>>        return self.container[0]

위와 같이 Queue의 ADT를 표시할 수 있다.

Stack 2개로 Queue 구현하기

• 2개의 Stack을 활용하여 Queue의 ADT를 구현해야 한다.
• Stack의 ADT를 활용할 수 있다.
• 1개의 자료는 Stack을 Stack1 --> Stack2로 한번만 이동가능하다.
• 같은 폴더 안에 Stack의 ADT가 저장되어 있다고 가정(import 사용)

실제 구현

>>> from stack import Stack 
>>>
>>> class Queue:
>>>     
>>>        def __init__(self):
>>>            self.stack1 = Stack()
>>>            self.stack2 = Stack()
>>>
>>>        def empty(self):
>>>            if self.stack1.empty() and self.stack2.empty():
>>>                return True
>>>            else:
>>>                return False
>>>
>>>        def enqueue(self, data):
>>>            self.stack1.push(data)
>>>
>>>        def dequeue(self):
>>>            if self.stack2.empty():
>>>                while not self.stack1.empty():
>>>                    self.stack2.append(stack1.pop())
>>>            return self.stack2.pop()
>>>
>>>        def peek(self):
>>>            if self.stack2.empty():
>>>                while not self.stack1.empty():
>>>                    self.stack2.append(self.stack1.pop())
>>>            return self.stack2.peek()
>>>
>>>
>>> if __name__ == "__main__":
>>>        Que = Queue()
>>>        for i in range(10):
>>>            Que.enqueue(i)        
>>>        
>>>        print(Que.peek())
>>>        print(Que.dequeue())
>>>        print(Que.dequeue())
>>>        Print(Que.empty())
>>>        print(Que.enqueue(10))
>>>        print(Que.dequeue())
>>>        
0
0
1
False
None
2

이해하기가 쉽지 않다면 유튜브 영상을 추천한다.

[추천 참고 영상] (https://youtu.be/t45d7CgDaDM)

2019.03.14 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

자료구조 Stack & Queue

1.Stack

stack이란 무언가를 쌓는다라는 의미를 갖는 자료구조이다.
stack의 사전적의미를 찾아보면
: [명사] 동적이고 순차적인 자료의 목록.
: [영어] 무더기, 많음 다량, 굴뚝.
이라고 나온다.

LIFO(Last in, First out)

후입선출.
스택은 접시를 쌓는 것과 같기 때문에 먼저 들어간 자료보다는 가장 늦게 쌓이고 가장 위에 있는 접시가 먼저 나오게 된다.
이것은 후입선출이라고 한다.

먼저 스택을 사용하기 위해서 ADT라는 개념을 배워보자.

ADT(abstract data type) : 추상 자료형

1. 어떤 자료구조가 가지고 있는 오퍼레이션(함수)의 나열(목록)
2. 함수 시그니처(인터페이스)만 나열할 뿐, 내부 구현은 표기하지 않음
3. 함수(operation)의 작동 방식 설명.

위의 조건을 꼭 지켜줘야한다. ADT에 대해 명쾌히 설명을 해준 블로그를 참고해보면,

추상 자료형(Abstract Data Type)

기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것을 추상 자료형이라고 한다.

예를 들면, 사용 설명서와 같다. 선풍기의 사용 설명서를 본다고 가정하자. 사용 설명서에는 정지, 미풍, 약풍, 강풍, 회전, 타이머등의 기능 설명과 사용 방법이 나와있다. 하지만 버튼을 눌렀을 때 선풍기 내부회로에서 어떤 일이 발생하는지에 대해서는 전혀 나와있지 않다. 추상 자료형은 선풍기의 사용 설명서와 같이 기능과 사용 방법을 정의한 것이다.

추상 자료형의 필요성

추상 자료형은 구현자와 사용자를 분리해 준다. 라이브러리를 가져다 쓰거나 내장 함수를 사용하는 것도 추상 자료형이 정의되어 있기 때문이다. 또한 추상 자료형에 대한 구현은 외부로 부터 숨겨져 정보 은닉(Information Hiding)이 이루어지게 된다.

추상 자료형 정의

무선 마우스의 추상 자료형을 정의해 본다면,

ADT of Wireless Mouse

• Data

: Power, LeftButton, RightButton 전원, 왼쪽버튼, 오른쪽버튼

• Operation

: PowerOn() 전원 On

: PowerOff() 전원 Off

: LeftButtonClick() 왼쪽 버튼 클릭

: RightButtonClick() 오른쪽 버튼 클릭

출처: https://ledgku.tistory.com/41 [견우와 직녀]

위의 글을 참조하여 한번에 개념을 이해하였다.

선생님은 코드를 통해 ADT에 대해 이야기해주셨다.

>>>dir(list)
>>>
['__add__',
 '__class__',
 '__contains__',
 '__delattr__',
 '__delitem__',
 '__dir__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattribute__',
 '__getitem__',
 '__gt__',
 '__hash__',
 '__iadd__',
 '__imul__',
 '__init__',
 '__init_subclass__',
 '__iter__',
 '__le__',
 '__len__',
 '__lt__',
 '__mul__',
 '__ne__',
 '__new__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__reversed__',
 '__rmul__',
 '__setattr__',
 '__setitem__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 'append',
 'clear',
 'copy',
 'count',
 'extend',
 'index',
 'insert',
 'pop',
 'remove',
 'reverse',
 'sort']

위와 같이 list라는 객체의 내장 메소드들이 나오게 되는데
(#_method_ 와 아래 나온 메소드들의 차이를 알아보자!)

여기서 아래에 나오는 append, clear, copy와 같은 메소드들을
다시 코드를 통해 검색해보면

>>>help(list.append)
>>>Help on method_descriptor:

append(...)
    L.append(object) -> None -- append object to end

위와 같은 것을 얻을 수 있다. 즉 ADT가 요구하는 3가지 조건에 부합하는
설명을 볼 수 있다.
함수의 작동방식에 대해 설명해주고 있고(help on method_descriptor)
함수의 시그니처(인터페이스)만 설명하고 내부구현에 대해서는 언급하지 않으므로 추상자료형의 표기법으로 적합하다.

위와 같은 표기법으로 append, clear, copy, count, extend,,, sort까지 모아놓으면 그게 list의 ADT이다

Stack의 ADT

Stack의 ADT (operation list , operation의 시그니처만 나열)

1. S.empty() --> Boolean (스택이 비어있으면 True, 아니면 False)
2. S.push(data) ---> None (스택의 맨 위에 데이터를 쌓는다.) None->무조건들어간다
3. S.pop() ---> data (스택 맨 위의 데이터를 삭제하면서 반환)
4. S.peek() ---> data (스택 맨 위의 데이터를 반환)

• ADT 구현

>>>class Stack:
>>>    def __init__(self):
>>>        self.container=list()
>>>
>>>    def empty(self):
>>>        if not self.container:
>>>            return True
>>>        else:
>>>            return False
>>>
>>>    def push(self, data):
>>>        self.container.append(data)
>>>
>>>    def pop(self):
>>>        return self.container.pop()
>>>
>>>    def peek(self):
>>>        return self.container[-1]

위와 같이 스택의 ADT를 표시할 수 있다.

코드를 통한 Stack

스택을 사용하기 위해서는 stack 모듈을 불러와야 한다.

>>> from stack import Stack
>>> st=stack()       #스택이 만들어진다. list와 비슷하다.
>>> st.push(1)
>>> st.push(2)
>>> st.push(3)
>>> st.push(4)
>>> st.push(5)
>>> while not st.empty():
>>>     data = st.pop())
>>>     print(data)
>>> 5
>>> 4
>>> 3
>>> 2
>>> 1
>>> 

Stack과 함께 또 봐야하는 것이 있는데 바로 queue이다.

Queue(큐)

지금 놓치지 말아야 할 것은 stack와 queue는 모두 자료구조에서 자료가 저장되는 형태를 나타는 것이다.
queue의 사전적의미를 보면

: 규, 대기 행렬, 줄을 서서 기다리다
: 꼬리, 끝, 후미.

를 말한다. stack과는 다른 형태로 자료구조가 쌓인다.
Stack의 단점은 늦게 온 사람이 먼저 일을 처리하는 형태로 먼저 온 사람은 지속적으로 기다려야 하는 단점이 있다.
그에 비해 우리가 일반적으로 줄서기와 같은 것이 queue인데
먼저 기다린 사람이 먼저 나간다. FIFO(First in First Out) : 선입선출이며 보통 프로세스 처리, cpu관리에서 많이 쓰인다.

큐의 문제점은 일반적으로 배열을
[1][2][3][4][5]
이런 직선 형태로 보왔을 때,
[Pop][2][3][4][5] 가장 오래기다린, 처음 들어온 [1]이라는 데이터가 Pop이 되면 다른 데이터들을 차례대로
땡겨주어야 한다.
( 소수의 자료의 경우는 상관이 없지만 많은 데이터의 경우 연산에 많은 시간이 걸린다. )

이러한 문제점을 해결하기 위해 나온게 원형 큐, 순환 큐, 환영 큐 라고 불리는 방벙인데 배열을 직선이 아니라 원형으로 보는 것이다. (#다음에 추가적인 공부가 필요하다)

Queue의 ADT

Queue의 ADT (operation list , operation의 시그니처만 나열)

1. Q.empty() —> Boolean
   1. 큐가 비어있으면 true, 비어있으면 False
2. Q.enqueue(data) —> None
   1. 큐의 맨 뒤에 데이터를 쌓는다.
3. Q.dequeue(data) —> data
   1. 큐의 맨 앞에 데이터를 삭제하면서 반환
4. Q.peek() —> data
   1. 큐의 맨 앞의 데이터를 반환

• ADT 구현

>>>class Queue:
>>>
>>>    def __init__(self):
>>>        self.container = list() 
>>>    
>>>    def empty(self):
>>>        if not self.container:
>>>            return True
>>>        else:
>>>            return False
>>>    def enqueue(self, data):
>>>        self.container.append(data)
>>>
>>>    def dequeue(self):     
>>>        return self.container.pop(0)
>>>
>>>    def peek(self):
>>>        return self.container[0]

위와 같이 Queue의 ADT를 표시할 수 있다.

위에서 배운 것을 바탕으로 다음에는 Stack을 활용하여 계산기를 구현한다!

2019.03.11 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. linear_search

li라는 list에서 특정한 target의 인덱스를 찾으려면 어떻게 해야할까?
li = [ 5, 7, 2, 8, 3, 9, 1] 이라는 것에서
3이라는 target의 인덱스를 찾을 수 있는 함수를 구현해보자.

linear_search(li, target)--> idx
반환값은 target이 있다면 target의 인덱스
target이 없다면 None을 반환

def linear_search(li, target):
        for i in len(li):
            if li[i] == target:
                return i
        return None      # target이 없으면  None을 반환해라.

굉장히 간단한 함수이다. 하지만 함수의 성능을 보면 굉장히 비효율적으로 볼 수 있다.

알고리즘의 성능차이 비교 절대 시간을 비교 하면 안된다.
컴퓨터 성능이 차이나므로 상대 시간 : 어떤 알고리즘을 실행하는데 해비한 연산의 연산 횟수를 비교하자.
즉 데이터의 갯수에 따른 연산 횟수를 계산해서 성능을 계산하자

이 연산에 + - 등 보다는 그 알고리즘을 구성하는데 가장 헤비하게 미치는 연산은 for문이다.
일반적으로 for문 혹은 if문 비교 연산 if문을 많이 호출하면 느린거고 if문을 조금 호출하면 빠른 것이다.

또한 데이터가 늘어남에 따라 연산횟수가 얼마나 변화하는지를 비교해 봐야 한다.

성능을 평가할떄는 3가지 방법이 있다.

1. 최선의 경우
2. 평균의 경우 --> quick sort
3. 최악의 경우 --> 알고리즘을 말할때는 항상 최악의 경우를 가정한다.
   • 이 알고리즘은 아무리 최악의 경우 몇회의 연산횟수를 보장한다.

성능 평가에 대해 조금 더 공부해보려고 한다.

What does T(n) mean in relation to O(n)?

When discussing an algorithm, the common usage of the symbol 𝑇T is to represent its time complexity.
𝑇T is a function. The input to this function is the input size, the output is the (worst-case) running time for an input of that size.
Therefore, 𝑇(𝑛)T(n) is a number: the number returned by the function 𝑇T when given the number 𝑛n. This number is the running time of our algorithm on an input of size 𝑛n.
The 𝑂O in "𝑂(𝑛)O(n)" is not a function. This is Big O notation. In particular, the symbol 𝑂(𝑛)O(n) represents the class of all functions that grow (asymptotically) at most as quickly as the linear function 𝑓(𝑛)=𝑛f(n)=n.
Big O notation gives us a convenient way to talk about upper bounds. For example, we can say "the time complexity of this algorithm is 𝑂(𝑛2)O(n2)" (formally: "𝑇∈𝑂(𝑛2)T∈O(n2)") to say that the running time of the algorithm is at most quadratic in the input size.
Sometimes, you can see both symbols being used in a single equation. For example, the time complexity of MergeSort is commonly described by the following recurrence: "𝑇(𝑛)=2𝑇(𝑛/2)+𝑂(𝑛)T(n)=2T(n/2)+O(n)".
The meaning of the above statement: For any 𝑛n, the time 𝑇(𝑛)T(n) needed to sort 𝑛n elements can be computed by taking the time 𝑇(𝑛/2)T(n/2) needed to sort 𝑛/2n/2 elements, multiplying that time by 2, and adding something extra. That something extra must be at most linear in 𝑛n.

What does T(n) mean in relation to O(n)? - Quora

해석 :

알고리즘을 논할 때, 기호 T의 일반적인 용도는 시간 복잡성을 나타내는 것이다.

T는 함수다. 이 함수에 대한 입력은 입력 크기, 출력은 해당 크기의 입력에 대한 (최악의) 실행 시간이다.

따라서, T(n)는 숫자다: n을 부여했을 때 T 함수가 반환하는 숫자다. 이 숫자는 크기 n의 입력에 대한 우리의 알고리즘의 실행시간이다.

"O(n)"의 O는 기능이 아니다. 이것은 Big O 표기법이다. 특히 기호 O(n)는 선형 함수 f(n)=n만큼 빠르게(증식적으로) 성장하는 모든 기능의 클래스를 나타낸다.

Big O 표기법은 우리에게 상위에 대해 이야기할 수 있는 편리한 방법을 제공한다. 예를 들어, 우리는 "이 알고리즘의 시간 복잡성은 O(n2)"(공식적으로 "TOO(n2))라고 말할 수 있다.

때때로, 당신은 하나의 방정식에 두 개의 기호가 사용되는 것을 볼 수 있다. 예를 들어, MergeSort의 시간 복잡성은 일반적으로 "T(n)=2T(n/2)+O(n)"에 의해 설명된다.

상기 문장의 의미 : 어떤 n에 대해서도 n 요소를 분류하는데 필요한 T(n/2)는 n/2 요소를 분류하는 데 필요한 시간을 취하고 그 시간을 2로 곱한 후, 어떤 것을 추가함으로써 계산할 수 있다. 그 어떤 특별한 것은 n에 가장 직선적일 것이다.

---->> T 함수는 함수에 대한 최악의 실행시간이다. T(n)은 숫자인데 n 크기에 대한 자료를 함수에 넣었을 때 걸리는 실행시간이다.

---->> 우리가 말하는 알고리즘의 성능이 어떤 것인지 T of N 을 항상 구할 수는 없으므로 big O를 구하는 것을 배운다.

binary_search

def binary_search(li, target):
    """
    binary_search(li, target)--> idx
    반환값은 target이 있다면 target의 인덱스
    target이 없다면 None을 반환
    """

binary_search는 기본적으로 들어오는 자료가 정렬이 되었다고 가정하고 시작한다.
이를 통해 우리는 정렬된 자료의 중간값과 target을 비교하고, target이 중간값보다 작다면
중간값 이후의 배열에는 신경쓰지 않고 중간값이 전의 값들로만 비교하겠다는 것이다.
이를 통해 우리는 for 문을 돌렸을 때보다 훨씬 좋은 성능의 알고리즘을 구현할 수 있다.
(실제로도 많이 쓰이는 알고리즘이다)

구현

def binary_search(li, target):
        start = 0       #(인덱스는 0부터 시작하므로)
        end = len(li) - 1       #(인덱스를 기준으로 해야함으로 1을 빼줘야 한다)
        while start <= end:
                mid = (start + end) // 2
                if li(mid) > target:
                    end = mid - 1
                elif li(mid) < target:
                    start = mid + 1
                else:
                    return mid   # 이러면 실제로 리턴 값에만 들어가게 되므로 시스템적으로 나오는 것은 없다. 따라서 꼭 print를 해서 화면에 나오게 해줘야 한다. or 이 함수를 다른 변수에 할당하고 그 변수를 print하도록 한다.
        return None

[
참고자료] (https://github.com/fabl1106/CS/blob/master/data_structure/binary_search/binary_search.pdf)

새롭게 알게 된 중요한 사실

def exam():
        return 1

exam() 

을 실행해보면 아무것도 나오지 않는다. 숫자 혹은 string을 적어도 마찬가지 이다.

여기서 중요하게 알아야 할 것은 return을 해주는 것은 그 함수에서 리턴 값을 거기에 할당해주는 것이기 때문에 화면에는 나타나지 않는다.
이것을 해결하기 위해서는 return 위에 print 를 적어 화면에 표시하고 싶은 것을 적고 아래에
return 만을 적어서 함수를 빠져나오게 하거나
exam()을 특정변수에 할당해주어서 ( a = exam() ) 그 변수를 print 하는 방법이 있다.

다시 방법을 적어보면

def exam():
        print(1)
        return
exam()        # 이렇게 하면 return 값은 None이 반환된다. 따라서 상황에 따라 return 뒤에 1을 적어줘야 한다.

혹은

def exam():
        return 1

a = exam()
print(a)     #print를 해주어야 한다. 정 위와 같이 해주고 싶다고 하면 exam() 앞에 print를 해주면 된다.

def exam():
        return 1
print(exam())