자료구조

17 July 2017

데이터를 어떤 구조로 저장하고 탐색해야하는가

Insert : 데이터를 어떻게 저장할 것인가
Search : 데이터를 어떻게 탐색할 것인가
Delete : 데이터를 어떻게 삭제할 것인가

알고리즘

문제를 해결하는 방법론

자료구조의 알고리즘

데이터를 저장하고 탐색하는 방법에 대한 고민들

자료구조를 이용한 알고리즘

자료구조를 이용해 어떤문제를 해결하는 것

Array & Linked List

배열

동일한 자료형을 가진 데이터의 모임
가변 배열이라해도 크기가 고정되어있음
길이를 늘리려면, 적절한 공간을 찾아 기존 값을 복사하고 늘어나는 부분에 데이터를 넣는다.
값을 찾을때에는 인덱스로 바로 접근
데이터의 추가, 삭제가 빈번하지 않으나 데이터의 접근이 빈번할때 사용

Linked List

길이를 늘릴때에는 뒤에 노드만 추가
값을 찾을때에는 처음 노드부터 따라가서 찾을 수 있다.
데이터를 자주 추가하고 삭제할때 사용

재귀함수 (recursion)

함수 정의 내에 같은 함수를 다시 호출하는 방법
탈출 조건이 필요하다.

stack frame : 공부해야함

피보나치

def fibo(n):
    if n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

if __name__ == "__main__":
    n = 10
    for i in range(n):
        print(fibo(i), end='    ')

# generator 사용
def fibo_gen(n):
    a = b = 1
    for i in range(n):
        yield a
        a, b = b, a + b

if __name__ == "__main__":
    f = fibo_gen(10)
    for i in range(10):
        print(next(f), end="    ")

generator

lazy 게으른 연산, 요구를 할때에만 값을 반환한다. 처음부터 가지고 있지 않음.
iterator 종류 중 하나

코루틴까지 공부하기

하노이의 탑

def hanoi(num, _from, _by, _to):
    # 탈출조건
    if num == 1:
        print("{}에서 {}로 {}번째 원반 이동".format(_from, _to, num))
        return
    hanoi(num - 1, _from, _to, _by)
    print("{}에서 {}로 {}번째 원반 이동".format(_from, _to, num))
    hanoi(num - 1, _by, _from, _to)


if __name__ == "__main__":
    while 1:
        numOfTray = int(input("원반의 갯수를 입력하세요(종료:0) :"))
        if numOfTray == 0:
            break
        hanoi(numOfTray, 'A', 'B', 'C')

Liner Search (선형 탐색)

순차적으로 탐색
탐색 속도 비교군
T(n) = n
이 알고리즘은 최악의 경우에도 n의 시간을 보장한다.
big O : n

def liner_search(data, target):
    for idx in range(len(data)):
        if data[idx] == target:
            return idx
        return None


if __name__ == "__main__":
    data = [i for i in range(10)]
    target = 4
    idx = liner_search(data, target)

    if idx is None:
        print("{}이 존재하지 않습니다.".format(target))
    else:
        print("찾는 데이터의 인덱스는 {}이고 데이터는 {}입니다.".format(idx, data[idx]))

Binary Search (이진 탐색)

liner search에 비해 성능이 좋다.
이진 탐색은 데이터가 정렬된 상태에서만 작동한다.
이 알고리즘은 최악의 경우에도 logn의 시간을 보장한다.
big O : logn

def binary_search(data, target):
    """
    데이터가 정렬된 상태로 전달되어야 합니다.
    :param data: sorted list
    :param target: 찾는 숫자
    :return: 찾는 숫자의 인덱스
    """
    start = 0
    end = len(data) - 1
    count = 0
    while start <= end:

        mid = (start + end) // 2
        # target 과 mid 값이 같을 경우
        if target == data[mid]:
            count += 1
            return mid, count
        # target 이 중간값보다 작을 경우
        elif target < data[mid]:
            count += 1
            # end를 중간값 바로 전으로 이동
            end = mid - 1
        # target 이 중간값보다 작을 경우
        else:
            count += 1
            # start 를 중간값 다음으로 이동
            start = mid + 1
    # while 을 빠져나가는 경우는 end 와 start 가 교차되었을때
    return None


if __name__ == '__main__':
    li = [i for i in range(100)]
    target = 96
    idx = binary_search(li, target)
    if idx:
        print(li[idx[0]])
        print("{}번만에 찾았습니다.".format(idx[1]))
    else:
        print("There's no data")

이진 탐색은 데이터가 정렬된 상태에서만 작동한다.

while로 해결할 수 있으면 있으면 재귀함수를 안쓰는 것이 좋다.
재귀함수는 가급적 안쓰는 것이 좋다.

과제 : Binary Search를 재귀함수로 바꾸기, 버블정렬

# Binary Search를 재귀함수로 바꾸기
def binary_search_re(start, end, target):
    lst = [i for i in range(start, end + 1)]
    mid = len(lst) // 2
    num = lst[mid]
    if start > end:
        return 1
    elif target == num:
        return num
    elif target < num:
        return binary_search_re(start, lst[mid - 1], target)
    else:
        return binary_search_re(lst[mid + 1], end, target)


if __name__ == '__main__':
    start = 1
    end = 11
    target = 2
    result = binary_search_re(start, end, target)
    if result:
        print(result)
    else:
        print("There's no data.")

# 버블정렬 (for 문을 2개 사용하면 Big O = n^2)
def bubble(lst):
    lst_len = len(lst)
    for i in range(lst_len - 1):
        for j in range(0, lst_len - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
    return lst


if __name__ == "__main__":
    list1 = [4, 7, 9, 3, 4, 6, 2, 7, 1]
    print(bubble(list1))

버블정렬의 Big O는 등차수열로 계산하면 n^2이 나온다.
for를 중첩하는 것은 가급적 피해야한다.

Big O (시간 복잡도)

O(1)
O(n)
O(logn)
O(nlogn)
O(n^2)

추상자료형 (ADT Abstract Data Type)

함수 인터페이스 목록
구현 방법을 명시하고 있지 않다

함수 인터페이스

함수이름 + 인자목록 + 반환값 + 설명을 명시해 놓은 것
이것을 알면 함수를 사용할 수 있게 함.
help(list.sort)
doc string이랑 비슷(같..)하다. 자료구조에서 부르는 이름.

Liked List!!!!

중요!!!
자료구조의 시작이자 끝

node

데이터를 담아두는 하나의 틀 (데이터부 + 다음 노드를 가리키는 참조부)

ADT (07_linked_list.py)

가정 :data로 None을 넣을 수 없음
예외 처리가 없으므로 제작자의 의도대로만 사용해야함.

append(data) -> None
empty() -> bool
- 비어있으면 True
- 비어있지않으면 False
size() -> integer
traverse(mode = ‘next’) -> data (‘first’:첫번째 node, ‘next’:첫번째 이후의 다음 node로 순회하며 반환)
remove() -> data (traverse를 통해 찾은 삭제 node를 삭제하고 삭제하는 node를 반환)

레퍼런스 카운팅

레퍼런스 카운트 : 데이터를 참조하고 있는 숫자. 0이면 아무데서도 쓰이는 곳이 없다는 의미 -> 가비지 콜렉션(메모리에서 데이터 사라짐)

>>> import sys
>>> sys.getrefcount()
>>> help(sys.getrefcount)
getrefcount(...)
    getrefcount(object) -> integer

    Return the reference count of object.  The count returned is generally
    one higher than you might expect, because it includes the (temporary)
    reference as an argument to getrefcount().

생성자 (constructor)

객체를 만들때 반드시 1번은 호출한다.
__init__

소멸자 (destructor)

객체를 메모리 공간에서 삭제될때 반드시 1번은 호출한다.
__del__
파이썬은 garbage collection을 하기 때문에 쓸 일은 별로 없다.

heap

프로그래머 마음대로 메모리를 할당하고, 스코프가 끝나지 않더라도 메모리에서 삭제할 수 있다.
할당된 메모리가 삭제되는 것을 보장하지 않음. (memory leak 발생 가능)
인터프리터 언어(파이썬 등)는 stack에 메모리에 할당 못함. heap에 할당함.
private heap : 파이썬이 실행되면서 할당하는 메모리 영역. 이 영역 내부를 나눠서 사용한다.
컴파일러 언어는 메모리의 모든 영역을 다 사용 (code, data, heap, stack)
파이썬 - compiler - lexer / parser
참고 : import ast(lexer에서 parser 넘어가는 중간단계)

과제 : dummy linked list 구현

stack / queue

stack

위에서 부터 꺼낸다.
Last in First out / LIFO / 후입선출

stack ADT

push(data) -> None : 마지막에 데이터 추가 (스택에 쌓는다.)
pop() -> data : 맨 마지막 데이터 삭제 -> 삭제된 데이터 반환
empty() -> bool
peek() -> data : 삭제하지 않고 맨 마지막 데이터만 반환

class Stack(list):
    push = list.append
    # 위 코드와 같다.
    # def push(self, data):
    #     super().append(data)
    # pop은 기존 list.pop 사용. 인자가 없으면 마지막 데이터를 삭제하고 반환
    
    def empty(self):
        # 데이터가 비어있는지 확인
        if not self:
            return True
        else:
            return False

    def peek(self):
        # 리스트의 마지막 데이터 반환
        return self[-1]


if __name__ == "__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    s.push(5)
    print(s)

    while not s.empty():
        data = s.pop()
        print(data, end='   ')

queue

First in, First out / FIFO / 선입선출

queue ADT

enqueue(data) -> None : insert (맨 뒤에 데이터 삽입)
dequeue() -> data : 맨 앞 데이터 삭제하고 삭제하는 데이터 반환
empty() -> bool
peek() -> data : 삭제하지 않고 맨 앞 데이터 반환

class Queue(list):
    enqueue = list.append

    def dequeue(self):
        return self.pop(0)

    def empty(self):
        if not self:
            return True
        else:
            return False

    def peek(self):
        return self[0]


if __name__ == "__main__":
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)
    print(q)

    while not q.empty():
        print(q.dequeue(), end='  ')

후위표기법을 사용한 계산기

가정: 모든 피연산자는 1자리 숫자

중위표기법

우리가 하는 수식
(2+5)*3*(2+1)

후위표기법

컴퓨터가 계싼하기 쉬은 수식
괄호가 없다.;
연산자가 뒤로
25+3*21+*

후위표기법 표시 방법

숫자는 무조건 리스트에 append
연산자는 가중치를 비교하여 stack이나 리스트에 append
*, / > +, - > (
연산자는 일단 stack에, 다음에 오는 연산자의 가중치가 높을 경우, 기존 연산자 위에 위치
다음에 오는 연산자의 가중치가 같을 경우 기존 연산자를 리스트에 append, 지금 연산자는 stack에
다음에 오는 연산자의 가중치가 낮을 경우, 기존 stack의 연산자를 리스트에 append.
stack에 연산자가 여러개 있을 경우 위의 연산자부터 비교.
( 는 연산자와 우선순위를 비교하지 않고 무조건 stack에 넣는다.
( 위에는 우선순위에 따라 stack에 연산자가 쌓이고 ( 는 우선순위가 낮으므로 ( 다음에 오는 연산자는 ( 위에 쌓인다.
) 가 나오면 (가 상쇄되어 없어지고 stack에 쌓여있던 연산자는 위에서부터 순서대로 리스트에 append
리스트를 join 하여 완료

# 가정 : 입력된 수식을 수는 모두 1자리 수이다.

from stack import Stack


class Calculator:
    def __init__(self):
        self.org_exp = None  # 중위표기법 (사용자 입력 수식)
        self.postfix_exp = None  # 후위표기법
        self.result = None

    def set_org_exp(self, org_exp):
        # 입력한 수식 정리하는 함수
        self.org_exp = org_exp.replace(' ', '')
        # 초기화 (이전 계산값이 남아있을수 있으므로)
        self.postfix_exp = None
        self.result = None

    def get_org_exp(self):
        return self.org_exp

    def get_weight(self, oprt):
        # 연산자 별로 가중치를 부여하는 함수
        if oprt == '*' or oprt == '/':
            return 9
        elif oprt == '+' or oprt == '-':
            return 7
        elif oprt == '(':
            return 5

    def convert_to_postfix(self):
        # 입력된 수식을 후위표기법으로 변환하는 함수
        # 리스트 초기화
        exp_list = []
        # stack 선언
        oprt_stack = Stack()
        # 입력된 수식을 한글자씩 순회
        for ch in self.get_org_exp():
            # ch가 숫자일때
            if ch.isdigit():
                # 리스트에 추가
                exp_list.append(ch)
            # 연산자일때
            else:
                # ( 이거나 스택이 비었을때
                if oprt_stack.empty() or ch == '(':
                    # stack에 쌓는다.
                    oprt_stack.push(ch)
                # ) 일때
                elif ch == ')':
                    # stack의 마지막 데이터를 지우면서 가지고 와서
                    op = oprt_stack.pop()
                    # op가 ( 이 아니라면
                    while op != '(':
                        # 리스트에 추가
                        exp_list.append(op)
                        # 다시 stack의 마지막 데이터를 지우면서 가지고 와서 ( 가 나올때까지 while
                        op = oprt_stack.pop()
                # +, -, *, / 일때
                # ch의 가중치가 stack에 있는 연산자의 가중치가 작거나 같을때
                elif self.get_weight(ch) > self.get_weight(oprt_stack.peek()):
                    oprt_stack.push(ch)
                else:
                    # ch의 가중치가 stack에 있는 연산자의 가중치가 작거나 같을때
                    # oprt_stack 가 비어있지않은지 먼저 확인하고 가중치 비교
                    while oprt_stack and self.get_weight(ch) <= self.get_weight(oprt_stack.peek()):
                        # 스택에서 삭제하면서 리스트에 추가
                        exp_list.append(oprt_stack.pop())
                    #
                    oprt_stack.push(ch)
        # 다 돌고나서 연산자가 남아있을 경우
        while oprt_stack:
            exp_list.append(oprt_stack.pop())
        self.postfix_exp = ''.join(exp_list)

    def get_postfix_exp(self):
        # 캐시 기법
        if not self.postfix_exp:
            self.convert_to_postfix()
        return self.postfix_exp

    # 필수는 아니지만 편의를 위해 만든 함수
    def calc_two_oprd(self, oprd1, oprd2, oprt):
        if oprt == '+':
            return oprd1 + oprd2
        elif oprt == '-':
            return oprd1 - oprd2
        elif oprt == '*':
            return oprd1 * oprd2
        elif oprt == '/':
            return oprd1 / oprd2

    def calculator(self):
        oprd_stack = Stack()
        # 접근자가 있으면 클래스외부에서 접근할땐 항상 그함수를 통해 접근해야함.
        for ch in self.get_postfix_exp():
            if ch.isdigit():
                oprd_stack.push(int(ch))
            else:
                oprd2 = oprd_stack.pop()
                oprd1 = oprd_stack.pop()
                oprd_stack.push(
                        self.calc_two_oprd(oprd1, oprd2, ch)
                )
        self.result = oprd_stack.pop()

    def get_result(self):
        if not self.result:
            self.calculator()
        return self.result


if __name__ == "__main__":
    calc = Calculator()
    while 1:
        exp = input("수식을 입력하세요.(종료:0):")
        if exp == '0':
            break

        calc.set_org_exp(exp)
        print(calc.get_postfix_exp())
        print('{exp} = {result}'.format(
                exp=calc.get_org_exp(),
                result=calc.get_result()
        ))

Tree !!!

사이클을 이루지 않는 연결 그래프의 일종
루트노드 : 가장 상위 노드 (level 0)
인터널노드(브랜치노드) : 루트는 아니지만 자식 노드가 있음
리프노드(단말노드) : 자식이 없는 마지막 노드
엣지(간선, 링크): 노드끼리 연결함
서브트리 :자식이 크리를 가짐
높이(height) : 루트노드 부터의 높이

Binary Tree

자식노드를 최대 2개만 가지는 트리
Full Binary Tree(포화이진트리) : 모든 레벨의 노드가 자식을 2개씩을 가지는 트리
Complete Binary Tree(완전이진트리) : 위에서 아래로, 왼쪽에서 오른쪽으로 노드가 쌓임

Tree 순회

전위순회

부모부터 순회를 시작, 왼쪽에서 오른쪽 (재귀)
자식이 더이상 없으면 상위로 올라가 오른쪽 순회

중위순회

왼쪽 -> 부모 -> 오른쪽 (재귀)
가장 하단의 왼쪽까지 내려가서 순회 시작
가장 하단의 왼쪽 > 부모 > 오른쪽

후위순회

가장 하단의 왼쪽까지 내려가서 순회 시작
가장 하단의 왼쪽 > 오른쪽 > 위로 올라옴 > 오른쪽 가장 하단의 왼쪽 > 오른쪽 > 위로 올라옴

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

    # 소멸자 - 데이터를 메모리에서 삭제하기 전에 호출된다.
    def __del__(self):
        print("TreeNode of {} is deleted.".format(self.data))

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

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


class BinaryTree:
    def __init__(self):
        self.root = None

    def get_root(self):
        return self.root

    def set_root(self, r):
        self.root = r

    def make_node(self):
        # 이진트리의 모든 기능을 구현하는 클래스라 추가함.
        # 노드의 생성을 위임함. (캡슐레이션)
        new_node = TreeNode()
        return new_node

    def get_node_data(self, cur):
        return cur.data

    def set_node_data(self, cur, data):
        cur.data = data

    def get_left_sub_tree(self, cur):
        return cur.left

    def get_right_sub_tree(self, cur):
        return cur.right

    def make_left_sub_tree(self, cur, left):
        cur.left = left

    def make_right_sub_tree(self, cur, right):
        cur.right = right

    def preorder_traverse(self, cur, func):
        # 전위순회
        if cur == None:
            return
        func(cur.data)
        self.preorder_traverse(cur.left, func)
        self.preorder_traverse(cur.right, func)

    def inorder_traverse(self, cur, func):
        # 중위순회
        if not cur:
            return
        self.inorder_traverse(cur.left, func)
        func(cur.data)
        self.inorder_traverse(cur.right, func)

    def postorder_traverse(self, cur, func):
        # 후위순회
        if not cur:
            return
        self.postorder_traverse(cur.left, func)
        self.postorder_traverse(cur.right, func)
        func(cur.data)


if __name__ == "__main__":
    bt = BinaryTree()
    # 노드를 생성하는 것을 함수에 위임함. 7개의 노드 생성
    n1 = bt.make_node()
    bt.set_node_data(n1, 'A')

    n2 = bt.make_node()
    bt.set_node_data(n2, 'B')

    n3 = bt.make_node()
    bt.set_node_data(n3, 'C')

    n4 = bt.make_node()
    bt.set_node_data(n4, 'D')

    n5 = bt.make_node()
    bt.set_node_data(n5, 'E')

    n6 = bt.make_node()
    bt.set_node_data(n6, 'F')

    n7 = bt.make_node()
    bt.set_node_data(n7, 'G')

    n8 = bt.make_node()
    bt.set_node_data(n8, 'H')

    # 트리의 루트 설정
    bt.set_root(n1)
    # 1번 노드에 2, 3번을 자식으로 붙임
    bt.make_left_sub_tree(n1, n2)
    bt.make_right_sub_tree(n1, n3)
    # 2번 노드에 4, 5번을 자식으로 붙임
    bt.make_left_sub_tree(n2, n4)
    bt.make_right_sub_tree(n2, n5)
    # 3번 노드에 6, 7번을 자식으로 붙임
    bt.make_left_sub_tree(n3, n6)
    bt.make_right_sub_tree(n3, n7)

    # 1번 노드에 8번 노드를 자식으로 붙임
    bt.make_right_sub_tree(n1, n8)
    # 8번 노드에 3번 노드를 자식으로 붙임
    bt.make_right_sub_tree(n8, n3)

    # 3, 8 노드 삭제를 위해 1 - 6 노드 연결
    bt.make_right_sub_tree(n1, n6)
    # 6번 노드의 자식으로 7번 노드를 연결
    bt.make_right_sub_tree(n6, n7)
    # 3, 8번 노드 삭제
    del n3, n8

    # 노드값을 출력(람다는 호출되지않으면 사라짐)
    f = lambda x: print(x, end='    ')

    # 전위순회
    bt.preorder_traverse(bt.get_root(), f)
    print('\n')
    # 중위순회
    bt.inorder_traverse(bt.get_root(), f)
    print('\n')
    # 후위순회
    bt.postorder_traverse(bt.get_root(), f)
    print('\n')

Binary Search Tree

루트(부모)를 중심으로 왼쪽은 루트보다 작은값, 오른쪽은 루트보다 큰값
탐색의 BigO = logn
추가, 삭제 BigO = logn (추가할때 이어붙임)
성능이 좋다.
문자일때는 비교함수를 사용하여 기준을 정해준다.

추가

추가할 데이터를 루트와 비교하여 루트보다 작으면 왼쪽, 크면 오른쪽
이동한 곳에 노드가 있을 경우 다시 값을 비교하여 왼쪽, 오른쪽
위치할 곳에 노드가 없을때 그 곳에 추가

삭제

삭제할 노드가 단말노드
삭제할 노드의 자식노드가 하나일때
삭제할 노드의 자식노드가 두개일때

from binary_tree import *


class BinarySearchTree(BinaryTree):
    def insert(self, data):
        new_node = self.make_node()
        self.set_node_data(new_node, data)

        cur = self.get_root()
        if not cur:
            self.set_root(new_node)
            return

        while True:
            if data < self.get_node_data(cur):
                # left에 노드가 있으면
                if self.get_left_sub_tree(cur):
                    # cur를 이동
                    cur = self.get_left_sub_tree(cur)
                else:
                    # left에 노드가 없으면 그자리에 new_node를 넣고 종료
                    self.make_left_sub_tree(cur, new_node)
                    break
            else:
                if self.get_right_sub_tree(cur):
                    cur = self.get_right_sub_tree(cur)
                else:
                    self.make_right_sub_tree(cur, new_node)
                    break

    def search(self, target):
        cur = self.get_root()
        while cur is not None:
            if target == self.get_node_data(cur):
                return cur
            elif target < self.get_node_data(cur):
                cur = self.get_left_sub_tree(cur)
            else:
                cur = self.get_right_sub_tree(cur)
        return cur

    def remove_leaf(self, parent, del_node):
        # 루트노드를 지울때
        if del_node == self.get_root():
            self.get_root(None)
            return del_node
        # 일반적인 경우
        if self.get_left_sub_tree(parent) == del_node:
            # self.remove_left_sub_tree(parent)
            self.make_left_sub_tree(parent, None)
        else:
            # self.remove_right_sub_tree(parent)
            self.make_right_sub_tree(parent, None)
        return del_node

    def remove_one_child(self, parent, del_node):
        # 지우려는 노드의 자식이 1개인 경우
        # 삭제할 노드가 root일 경우, root노드를 다음노드로 이동
        # parent가 가리키는 것은 스택프레임이 사라지면서 자동으로 사라짐
        if del_node == self.get_root():
            if self.get_left_sub_tree(del_node):
                self.set_root(self.get_left_sub_tree(del_node))
            else:
                self.set_root(self.get_right_sub_tree(del_node))
            return del_node

        # 삭제하려는 노드가 root가 아닐경우
        del_child = None
        # 지우려는 노드의 왼쪽에 자식이 있다면
        if self.get_left_sub_tree(del_node):
            del_child = self.get_left_sub_tree(del_node)
        else:
            del_child = self.get_right_sub_tree(del_node)
        # 지우려는 노드가 parent의 왼쪽에 있었을때
        if self.get_left_sub_tree(parent) == del_node:
            self.make_left_sub_tree(parent, del_child)
        # 지우려는 노드가 parent의 오른쪽에 있었을때
        else:
            self.make_right_sub_tree(parent, del_child)

    def remove_two_children(self, del_node):
        # root에 대한 예외처리가 필요없음
        # 지우려는 노드와 값을 바꿔서처리 (왼쪽으로1번, 이후에는계속오른쪽으로 이동하며비교 -> 트리에서 지우려는 노드보다 다음으로 큰값을 찾는다)
        # 왼쪽으로 1번이동
        rep_parent = del_node
        replace = self.get_left_sub_tree(del_node)
        # 오른쪽으로 이동하며 대체노드 찾음(오른쪽 자식이 더이상없을때까지)
        while self.get_right_sub_tree(replace):
            rep_parent = replace
            replace = self.get_right_sub_tree(replace)
        # 대체노드를 찾으면 값을 교환(이 코드는 c 방식)
        temp_data = self.get_node_data(replace)
        self.set_node_data(replace, self.get_node_data(del_node))
        self.set_node_data(del_node, temp_data)
        # 부모의 왼쪽에 붙어있었다면 !!!
        if self.get_left_sub_tree(rep_parent) == replace:
            #
            self.make_left_sub_tree(rep_parent, self.get_left_sub_tree(replace))
        # 부모의 오른쪽에 붙어있었다면
        else:
            self.make_right_sub_tree(rep_parent, self.get_left_sub_tree(replace))
        return replace

    def remove(self, target):
        del_parent = self.get_root()
        del_node = self.get_root()
        while True:
            if del_node is None:
                return None
            # 지우려는 노드를 찾았을때
            if target == self.get_node_data(del_node):
                break
            # 지우려는 노드가 현재 노드보다 작을 경우
            elif target < self.get_node_data(del_node):
                # 하나씩 이동
                del_parent = del_node
                del_node = self.get_left_sub_tree(del_node)
            # 지우려는 노드가 현재 노드보다 클 경우
            else:
                del_parent = del_node
                del_node = self.get_right_sub_tree(del_node)
        # target의 자식에 따라 remove 종류를 다르게 적용
        if self.get_left_sub_tree(del_node) is None and self.get_right_sub_tree(del_node) is None:
            return self.remove_leaf(del_parent, del_node)
        # 지우려는 노드의 자식 노드가 1개일때
        elif self.get_left_sub_tree(del_node) is None or self.get_right_sub_tree(del_node) is None:
            return self.remove_one_child(del_parent, del_node)
        # 지우려는 노드의 자식노드가 2개일때
        else:
            return self.remove_two_children(del_node)


if __name__ == "__main__":
    bst = BinarySearchTree()

    # 트리노드생성
    bst.insert(6)
    bst.insert(3)
    bst.insert(2)
    bst.insert(4)
    bst.insert(5)
    bst.insert(8)
    bst.insert(10)
    bst.insert(9)
    bst.insert(11)

    f = lambda x: print(x, end='    ')
    # 전위순회
    bst.preorder_traverse(bst.get_root(), f)
    print('\n')

    # remove
    # bst.remove(9) # 말단노드 삭제
    # bst.remove(8) # 자식이 1개인 노드 삭제
    bst.remove(6) # 자식이 2개인 노드 삭제
    bst.preorder_traverse(bst.get_root(), f)
    print('\n')

BST의 단점

insert 순서가 1, 2, 3, 4, 5일 경우 링크드리스트와 형태가 같아져 Big O가 n으로 나와서 이진트리의 강점이 사라진다.

AVL (균형이진트리)

이진트리에 데이터를 insert하면서 효율적인 이진트리 구성으로 만들어준다.
BST의 단점을 보완
Black Red.. 도 있음

Quick Sort

단순 알고리즘

for 문을 2번 사용
모두 Big O = n^2

bubble sort (버블정렬)
insertion sort (삽입정렬)
selection sort (선택정렬)

Divide and Conquer (분할 정복 기법)

어려운 문제를 쪼개서(divide) 해결(conquer)
재귀 함수 이용

Quick sort (퀵소트)
Merge sort (머지소트)

Quick sort

데이터 중에 pivot을 정하고 pivot의 왼쪽에 left, 오른쪽에 right
left는 오른쪽으로 이동하면서 데이터가 pivot과 크기를 비교하여 pivot보다 같거나 크면 멈춤.
right는 왼쪽으로 이동하면서 데이터가 pivot과 크기를 비교하여 pivot보다 같거나 작으면 멈춤.
left와 right의 데이터 교환
left는 오른쪽으로 1칸 이동, right는 왼쪽으로 1칸 이동
반복하다가 left와 right가 교차하면 멈춤

def quick_sort(data, start, end):
    """
    quick sort
    :param data: list
    :param start: 시작 데이터 인덱스
    :param end: 마지막 데이터 인덱스
    :return: sorted list
    """
    # 탈출조건 : start와 end가 교차되었을 경우
    if start > end:
        return
    left = start
    right = end
    # pivot은 데이터 값
    pivot = data[(start + end) // 2]
    print("p")
    # left와 right가 교차되면 while을 빠져나감
    while left <= right:
        # left가 pivot보다 작을경우 오른쪽으로 이동, 크면 while을 빠져나감
        while data[left] < pivot:
            left += 1
        # right가 pivot보다 클경우 왼쪽으로 이동, 작으면 while을 빠져나감
        while data[right] > pivot:
            right -= 1

        # left와 right가 교차되지 않았는지 확인
        # 교차되지 않았다면
        if left <= right:
            # left와 right의 데이터 교환
            data[left], data[right] = data[right], data[left]
            # 한칸씩 이동
            left += 1
            right -= 1

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


if __name__ == "__main__":
    data = [7, 3, 5, 2, 6, 1, 4, 3, 2, 7]
    quick_sort(data, 0, len(data) - 1)
    print(data)

Quick sort의 Big O 계산

n개의 데이터를 절반씩 쪼갠 값이 1이 될때까지
n * (1/2)^k = 1
n * logn

sort 할때, 함수로 기준을 줄 수 있음

li.sort(key = lambda x: x%2 == 0)
짝수가 뒤로 간다.

OOP 참고…

class Base:
	var = 10 # 클래스 맴버, 클래스가 가지고 있고 객체들이 공유함
	
	def __init__(self):
		self.data = None # 객체 멤버

why i studied full time for 8 months for a google interview

google interview university

언어 종류별 컴파일러

컴파일러 언어

컴파일 타임 / 런타임(프로그램이 실행되는 시간)
컴파일 타임 : 소스코드를 받아 컴파일러를 커져 컴파일 언어 > 어셈블러를 거쳐 기계어로 변환 ( 요즘은 컴파일러 + 어셈블러)
컴파일러를 거쳐 object code가 나옴(목적코드)
c언어는 컴파일러를 거치면 기계어로 나옴 > 바로 실행
java는 컴파일러를 거치면 바이트코드로 나옴 > VM > 기계어로 변환 > 실행
input을 런타임에 받아 결과가 나옴
컴파일 타임에 분석이 끝난 코드를 런타임에 실행만 하므로 빠름

인터프리터 언어

런타임만 있음.
컴파일러가 input과 소스코드를 런타임에 받아 코드를 분석 > 바이트 코드 > VM > 결과
런타임 속도가 느림

컴파일

lexer와 parser로 구성
lexer : 소스코드를 받아 데이터를 쪼개서 트리(AST)를 구성
parser : AST를 받아 symbol table을 만들어 바이트코드(c는 기계어)로 만든다.