[1주차 - Day02] 어서와! 자료구조와 알고리즘은 처음이지?(2)

2021. 4. 21. 23:34

12. 수식의 후위 표기법

중위 표기법(infix notation) : 연산자가 피연산자들의 사이에 위치

ex) (A+B) * (C+D)

후위 표기법(postfix notation) : 연산자가 피연산자들의 뒤에 위치

ex) A B + C D + *

스택을 이용하면 중위 표현식을 후위 표현식으로 표현할 수 있다.

중위 표현식 -> 후위 표현식

중위 표현식을 왼쪽부터 한 글자씩 읽어서

피연산자이면 그냥 출력
( 이면 스택에 push
) 이면 ( 이 나올 때까지 스택에서 pop 후 출력
연산자이면 스택에서 이보다 높거나 같은 우선순위의 연산자를 pop 후 출력 그리고 이 연산자는 스택에 push
모두 읽은 후에 스택에 남아 있는 연산자를 모두 pop 후 출력

ex)

A * B + C -> A B * C +

A + B + C -> A B + C +

A + B * C -> A B C * +

class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

def solution(S):
    opStack = ArrayStack()
    answer = ''

    for s in S:
        if s == '(':
            opStack.push(s)

        elif s in prec:
            if opStack.isEmpty():
                opStack.push(s)
            else:
                while not opStack.isEmpty():
                    if prec[s] <= prec[opStack.peek()]:
                        answer += opStack.pop()
                    else: break
                opStack.push(s)

        elif s == ')':
            while opStack.peek() != '(':
                answer += opStack.pop()
            opStack.pop()

        else:
            answer += s


    while not opStack.isEmpty():
        answer += opStack.pop()

    return answer

괄호의 처리

여는 괄호 ( 는 스택에 push

닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop

여는 괄호의 우선 순위는 가장 낮게 설정

ex)

(A + B) * C -> A B + C *

A * (B + C) -> A B C + *

+) 연산자의 우선순위 설정

prec = { '*' : 3, '/' : 3, '+' : 2, '-' : 2, '(' : 1}

13. 후위 표기 수식 계산

후위 표기 수식을 왼쪽부터 한 글자씩 읽어서

피연산자이면 스택에 push
연산자이면 스택에 들어있는 피연산자 2개를 꺼내어 연산을 적용하고 결과를 다시 스택에 push

결과가 스택에 남음

class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]


def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
        if c == ' ':
            continue
        if c in '0123456789':
            val = val * 10 + int(c)
            valProcessing = True
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    if valProcessing:
        tokens.append(val)

    return tokens


def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    postfixList = []

    for s in tokenList:
        if s == '(':
            opStack.push(s)

        elif s in prec:
            if opStack.isEmpty():
                opStack.push(s)
            else:
                while not opStack.isEmpty():
                    if prec[s] <= prec[opStack.peek()]:
                        postfixList.append(opStack.pop())
                    else: break
                opStack.push(s)

        elif s == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()

        else:
            postfixList.append(s)


    while not opStack.isEmpty():
        postfixList.append(opStack.pop())

    return postfixList


def postfixEval(tokenList):
    Stack = ArrayStack()

    for token in tokenList:
        if type(token) is int:
            Stack.push(token)

        else:
            b, a = Stack.pop(), Stack.pop()
            if token == '+':
                Stack.push(a+b)

            elif token == '-':
                Stack.push(a-b)

            elif token == '*':
                Stack.push(a*b)

            elif token == '/':
                Stack.push(a/b)


    return Stack.pop()


def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
    return val

14. 큐

선입선출(First In First Out : FIFO) 구조

큐는 스택과 동일하게 선형 배열과 연결 리스트 두 가지를 이용해서 구현할 수 있다.

class ArrayStack:
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def is_empty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

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

    def peek(self):
        return self.data[0]

class LinkedListStack:
    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.get_length()

    def is_empty(self):
        return self.size() == 0

    def enqueue(self, item):
        node = Node(item)
        self.data.insert_at(self.size() + 1, node)

    def dequeue(self):
        return self.data.pop_at(1)

    def peek(self):
        return self.data.get_at(1).data

큐 연산

size() : 현재 큐에 들어있는 데이터 원소의 수를 구함
isEmpty() : 현재 큐가 비어 있는지를 판단
enqueue() : 데이터 원소를 큐에 넣는 동작
dequeue() : 데이터 원소를 꺼내는 동작
peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환

양방향 리스트를 이용한 큐

class Node:

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


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError('Index out of range')

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)


    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail

        self.nodeCount += L.nodeCount


class LinkedListQueue:

    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.getLength()


    def isEmpty(self):
        return self.size() == 0


    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.size()+1, node)


    def dequeue(self):
        return self.data.popAt(1)


    def peek(self):
        return self.data.getAt(1).data



def solution(x):
    return 0

15. 환형 큐

큐의 활용

자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적(Asynchronously)으로 일어나는 경우
자료를 이용하는 작업이 여러 곳에서 일어나는 경우
자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야하는 작업의 경우

환형 큐(Circular Queue)

정해진 개수의 저장 공간을 빙 돌려가며 이용

큐가 가득차면 더이상 원소를 넣을 수 없음 -> 큐 길이를 기억하고 있어야 함

환형 큐 연산

큐 연산에서 isFull() (큐에 데이터가 꽉 차있는지 판단하는 함수) 메서드 추가

class CircularQueue:

    def __init__(self, n):
        self.maxCount = n
        self.data = [None]*n
        self.count = 0
        self.front = -1
        self.rear = -1


    def size(self):
        return self.count

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.maxCount

    def enqueue(self, x):
        if self.isFull():
            raise IndexError("Queue full")

        self.rear = (self.rear+1) % self.maxCount
        self.data[self.rear] = x
        self.count += 1

    def dequeue(self):
        if self.isEmpty():
            raise IndexError("Queue empty")

        self.front = (self.front+1) % self.maxCount
        x = self.data[self.front]
        self.count -= 1
        return x

    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')

        return self.data[(self.front+1) % self.maxCount]


def solution(x):
    return 0

16. 우선순위 큐

큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

우선순위 큐의 구현은

enqueue 할 때 우선순위 순서를 유지하면서 넣기 -> 복잡도와 구현의 편의성 측면에서 더 유리!
dequeue 할 때 우선순위 순서에 따라 큐에서 빼기

+) 선형 배열보다는 연결 리스트를 이용하는 것이 시간적으로 더 유리

class Node:

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


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)


    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail

        self.nodeCount += L.nodeCount


class PriorityQueue:

    def __init__(self):
        self.queue = DoublyLinkedList()


    def size(self):
        return self.queue.getLength()

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head
        while curr.next.data != None and curr.next.data > x:
            curr = curr.next
        self.queue.insertAt(curr, newNode)

    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data


def solution(x):
    return 0

17. 트리

정점(Node)과 간선(Edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조

트리 관련 용어

노드 (Node)
간선 (Edge)
루트 노드 (root node), 말단 노드 (leaf node), 내부 노드 (internal node)
부모 노드 (parent node), 자식 노드 (child node)
노드의 수준 (level)
root 노드로부터 거쳐야 하는 간선의 개수
root 노드부터 0으로 시작
트리의 높이 (height) = 수준(level)의 최댓값 + 1 (또는, 깊이 (depth) 라고도 함)
부분 트리 (서브 트리; subtree)
트리 내에서 root 노드를 제외한 다른 노드로부터 시작하는 트리
노드의 차수 (degree)
자식 노드의 수
이진 트리 (binary tree)
모든 노드의 차수가 2 이하인 트리
재귀적으로 정의 가능 -> 빈 트리이거나, 루트 노드 + 왼쪽 서브 트리 + 오른쪽 서브 트리
(단, 모든 서브트리 또한 이진 트리)
포화 이진 트리 (full binary tree)
모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
(높이가 k이고 노드의 개수가 2^k -1 인 이진 트리)
완전 이진 트리 (complete binary tree)
높이가 k인 완전 이진 트리는 다음 조건을 만족하여야 함

1. 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
2. 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리

18. 이진 트리

모든 노드의 차수가 2이하인 트리

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

    def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1

class BinaryTree:
    def __init__(self, r):
        self.root = r

    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0

이진 트리 연산

size() : 현재 트리에 포함도어 있는 노드의 수를 구함
depth() : 현재 트리의 깊이 (또는 높이)를 구함

이진 트리 순회 (Traversal)

깊이 우선 순회 (Depth First Traversal)

전위 순회 (Pre-order Traversal)
중위 순회 (In-order Traversal)
후위 순회 (Post-order Traversal)

너비 우선 순회 (Breadth First Traversal)

깊이 우선 순회는 재귀적 방법이 적합

깊이 우선 순회

class Node:

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


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal

    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal


class BinaryTree:

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


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


    def preorder(self):
        return self.root.preorder() if self.root else []


    def postorder(self):
        return self.root.postorder() if self.root else []


def solution(x):
    return 0

19. 너비 우선 순회

수준(level)이 낮은 노드를 우선으로 방문
같은 수준의 노드들 사이에는

부모 노드의 방문 순서에 따라 방문
왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문

너비 우선 순회는 -> 큐(Queue)를 이용

class ArrayQueue:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

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

    def peek(self):
        return self.data[0]


class Node:

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


class BinaryTree:

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


    def bft(self):
        traversal, q = [], ArrayQueue()
        if self.root:
            q.enqueue(self.root)

        while not q.isEmpty():
            node = q.dequeue()
            traversal.append(node.data)

            if node.left:
                q.enqueue(node.left)
            if node.right:
                q.enqueue(node.right)

        return traversal


def solution(x):
    return 0

20. 이진 탐색 트리

모든 노드에 대해서,

왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 적고
오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰

성질을 만족하는 이진 트리

정렬된 배열을 이용한이진 탐색과 비교했을때

이진 탐색 트리를 이용하면데이터 원소의 추가와 삭제가 용이(하지만 공간 소요가 큼)

이진 탐색 트리는 중복값을 삽입할 수 없음!

항상 시간 복잡도가 O(logn) 나오는 것이 아님. 그렇지 않은 경우가 존재!

이진 탐색 트리 연산

insert(key, data) : 트리에 주어진 데이터 원소를 추가
remove(key) : 특정 원소를 트리로부터 삭제
lookup(key) : 특정 원소를 검색
inorder() : 키의 순서대로 데이터 원소를 나열
min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색

이진 탐색 트리에서의 원소 삽입

키를 비교하여 작으면 왼쪽으로, 크면 오른쪽으로 이동하여 각 방향의 노드가 존재하는 지 검사
1. 노드가 존재하지 않으면 새로운 노드 생성
2. 노드가 존재하면 해당 노드로부터 다시insert()메서드 호출
같은 키 값이 존재할 경우 오류 발생

class Node:

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


    def insert(self, key, data):
        if self.key > key:
            if self.left == None:
                self.left = Node(key, data)
            else:
                return self.left.insert(key, data)

        elif self.key < key:
            if self.right == None:
                self.right = Node(key, data)
            else:
                return self.right.insert(key, data)
        else:
            raise KeyError

        return True


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal


class BinSearchTree:

    def __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0

21강: 이진 탐색 트리 (2)

이진 탐색 트리에서의 원소 삭제

키를 이용해서 노드를 찾는다
- 해당 키의 노드가 없으면, 삭제할 것도 없음
- 찾은 노드의 부모 노드도 알고 있어야 함 (아래 2번을 진행하기 위해)
찾은 노드를 제거하고도 이진 탐색 트리 구조를 유지하기 위해 트리의 구조를 정리

이진 탐색 트리 구조의 유지

삭제되는 노드가

말단(leaf) 노드인 경우
1. 그 노드를 삭제
2. 부모 노드의 링크를 조정(left혹은right값을None으로 설정)
자식을 하나 가지고 있는 경우
1. 삭제되는 노드 자리에 그 자식을 대신 배치하고 삭제
2. 부모 노드의 링크를 조정(left혹은right값을 배치된 자식 노드로 설정)
자식을 둘 가지고 있는 경우
1. 삭제되는 노드보다 바로 다음(작거나 큰) 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 배치하고 대신 삭제
2. 부모 노드의 링크를 조정(left혹은right값을 배치된 자식 노드로 설정)

*삭제되는 노드가 root node 인 경우 → 대신 들어오는 자식이 새로 root가 됨 (처리 필요)

이진 탐색 트리가 별로 효율적이지 못한 경우

트리가 한쪽으로 치우쳐진 경우 →O(n)소요

높이의 균형을 유지함으로써 O(logn)의 시간 복잡도를 보장해주는 이진 탐색 트리는 다음과 같다.

AVL Tree
Red-Black Tree

하지만, 삽입/삭제가 보다 복잡함

class Node:

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


    def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif key > self.key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
        else:
            raise KeyError('Key %s already exists.' % key)


    def lookup(self, key, parent=None):
        if key < self.key:
            if self.left:
                return self.left.lookup(key, self)
            else:
                return None, None
        elif key > self.key:
            if self.right:
                return self.right.lookup(key, self)
            else:
                return None, None
        else:
            return self, parent


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count


class BinSearchTree:

    def __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None


    def remove(self, key):
        node, parent = self.lookup(key)
        if node:
            nChildren = node.countChildren()
            # The simplest case of no children
            if nChildren == 0:
                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # parent.left 또는 parent.right 를 None 으로 하여
                # leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
                if parent:
                    if node == parent.left:
                        parent.left = None
                    else:
                        parent.right = None

                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 를 None 으로 하여 빈 트리로 만듭니다.
                else:
                    self.root = None

            # When the node has only one child
            elif nChildren == 1:
                # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
                # 그 자식을 어떤 변수가 가리키도록 합니다.
                if node.left:
                    childNode = node.left
                else:
                    childNode = node.right

                # 만약 parent 가 있으면
                # node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
                # 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
                if parent:
                    if node == parent.left:
                        parent.left = childNode
                    else:
                        parent.right = childNode

                # 만약 parent 가 없으면 (node 는 root 인 경우)
                # self.root 에 위에서 가리킨 자식을 대신 넣습니다.
                else:
                    self.root = childNode

            # When the node has both left and right children
            else:
                parent = node
                successor = node.right
                # parent 는 node 를 가리키고 있고,
                # successor 는 node 의 오른쪽 자식을 가리키고 있으므로
                # successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
                # 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
                # 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
                while successor.left:
                    parent, successor = successor, successor.left

                # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
                node.key = successor.key
                node.data = successor.data

                # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
                # 그에 따라 parent.left 또는 parent.right 를
                # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
                if successor == parent.left:
                    parent.left = successor.right
                else:
                    parent.right = successor.right

            return True

        else:
            return False


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


def solution(x):
    return 0

22. 힙

이진 트리의 한 종류

완전 이진 트리 → (말단 노드가 왼쪽부터 차례로 채워져야 함)
루트 노드가 언제나 최댓값 (또는 최솟값) 을 가짐
- 최대 힙 (max heap) (또는 최소 힙(min heap))

모든 부모 노드는 자식 노드보다 작은 값 (또는 큰 값) 을 가짐

→ 재귀적으로도 정의됨 (힙 내의 모든 서브트리 또한 최대 힙)

힙은 중복값 삽입 가능

이진 탐색 트리 vs 힙

이진 탐색 트리는 특정 값을 검색하는 데에 사용

힙은 최대/최소값을 찾는 데 사용

배열을 이용하여 구현하는 힙

* root 노드 번호를 1로 설정

노드 번호 n을 기준으로

왼쪽 자식 번호 : n\*2
오른쪽 자식 번호 : n\*2 + 1
부모 노드의 번호 : n // 2

힙은 완전 이진 트리의 성질을 가지고 있기 때문에 배열로 구현해도 괜찮

최대 힙에 원소 삽입

class MaxHeap:

    def __init__(self):
        self.data = [None]


    def insert(self, item):
        ll = len(self.data)
        self.data.append(item)

        while (ll // 2) > 0:
            if self.data[ll//2] < self.data[ll]:
                self.data[ll//2], self.data[ll] = self.data[ll], self.data[ll//2]
            ll //= 2


def solution(x):
    return 0

23. 힙(2)

최대 힙에서 원소 삭제

루트 노드의 제거
트리 마지막 자리 노드를 루트 노드의 자리에 배치
자식 노드와 키 값을 비교하여 서로 교환 (위에서 아래로)

class MaxHeap:

    def __init__(self):
        self.data = [None]


    def remove(self):
        if len(self.data) > 1:
            self.data[1], self.data[-1] = self.data[-1], self.data[1]
            data = self.data.pop(-1)
            self.maxHeapify(1)
        else:
            data = None
        return data


    def maxHeapify(self, i):
        # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
        left = i*2
        # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
        right = i*2+1
        smallest = i
        # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if left < len(self.data) and self.data[left] > self.data[smallest]:
            # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
            smallest = left

        # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
        if right < len(self.data) and self.data[right] > self.data[smallest]:
            # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
            smallest = right

        if smallest != i:
            # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]

            # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
            self.maxHeapify(smallest)


def solution(x):
    return 0

'프로그래머스인공지능스쿨' 카테고리의 다른 글

[2주차 - Day01] 인공지능 수학 - 선형대수 (0)	2021.04.26
[1주차 - Day04] 파이썬을 무기로, 코딩테스트 광탈을 면하자! (2) (0)	2021.04.23
[1주차 - Day03] 파이썬을 무기로, 코딩테스트 광탈을 면하자! (1) (0)	2021.04.22
[1주차 - Day01] 어서와! 자료구조와 알고리즘은 처음이지?(1-2) (0)	2021.04.20
[1주차 - Day01] 어서와! 자료구조와 알고리즘은 처음이지?(1-1) (0)	2021.04.20

kd's 코드북