프로그래머스 강좌, 자료구조와 알고리즘 - 3

자료구조와 알고리즘 - 3 link

14강. 큐(Queues)


큐는 Stack과 달리 선입선출(FIFO; First-In First-Out) 의 순서로 제어됩니다. 리스트 속에 데이터들의 시작과 끝의 포인터가 존재합니다. 입력(enqueue)시, 리스트의 rear pointer에 추가되며 출력(dequeue)시, 리스트의 front pointer 부분을 꺼내게 됩니다.

실습

목표: 배열과 양방향 연결 리스트 구현시, 연산 복잡도 확인

배열 - 출력시, 모든 개체의 위치를 옮기는 과정에서 O(n) 가 소요
양뱡향 연결 리스트 - 포인터만 변경하게 됨으로 O(1) 소요

15강. 환형 큐(Circular Queue)


dequeue 과정에서 발생한 front pointer 앞의 공간을 재사용하지 못하는 큐의 단점을 개선하여 리스트의 시작과 끝을 이음으로써 재사용 가능

실습

목표: 환형큐의 enqueue, dequeue, peek 구조를 구현

범위가 제한된 배열을 환형으로 이어서 쓴다는점을 감안하여 배열의 끝과 처음을 연속적으로 사용

16강. 우선순위 큐(Priority Queues)

FIFO 의 특성을 가진 일반적인 큐와 달리 우선순위에 따라 enqueue나 , dequeue의 대상이 선택되는 방식.

실습

목표: 양방향 리스트를 통해 enqueue할 때, 순차검색을 통해 일치하는 위치에 넣는 방식 사용, data의 값이 클수록 높은 우선순위.

enqueue => O(n), dequeue = O(1)
트리구조 사용시 더 유용하나 다음 과정에 진행, 퀵정렬과 비슷한 느낌일것으로 예상

17강. 트리(Trees)


트리의 각 노드를 정해진 순서로 방문하는 것, 순회 (traversal) 연산.

  • 깊이 우선 순회 (DFT; Depth First Traversal)
  • 넓이 우선 순회 (BFT; Breadth First Traversal)

    DFT (Depth First Traversal) vs DFS (Depth First Search)? link

    1. DFT는 DFS를 사용합니다.
    2. DFS가 연결된 그래프에 적용되는 알고리즘 인 반면, DFT는 일반적으로 연결이 끊어진 그래프에 적용되는 순회입니다.
    3. DFS는 DFT가 수행하는 동안 각각의 모든 노드를 방문 할 것이라고 보증하지 않았습니다.

    하지만 같은것이라 보아도 크게 문제되지 않습니다. 두 용어 모두, 그래프 또는 트리 (모든 트리는 또한 그래프이기도 합니다) 를 대상으로 노드들을 방문하는 순서를 규정하는 방식을 뜻합니다.

근데 tree보단 root모양인데 왜 그렇게 굳어진걸까?

18강. 이진 트리(Binary Trees)

모든 노드의 자식노드; 차수가 2 이하인 트리구조

깊이 우선 순회(DFT; Depth First Traversal)

  • 중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤 노드 x 를 방문, 그리고 나서 오른쪽 서브트리를 순회
  • 전위 순회 (pre-order traversal): 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회
  • 후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문

실습 1

목표: 이진트리의 depth 값 계산하는 기능 구현

class Node:
	# 초기화 & size()
	
    def depth(self):
        # 재귀적으로 호출하며 단말노드 부터 체크
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        # l 과 r 변수에 좌우 노드의 깊이값 저장
        return (l if l > r else r) + 1
        
class BinaryTree:
	# 초기화 & size()
	
    def depth(self):
        # 루트값 유무 확인
        if self.root:
            # root node 부터 depth 확인절차 진행
            return self.root.depth()
        else:
            return 0

실습 2, 3 - 깊이 우선 순회(DFT; Depth First Traversal)

목표: 이진트리의 전위순회, 후위순회 연산 기능 구현

class Node:
	# 초기화 & inorder()
	
	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:
	# 초기화 & inorder()
	
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []
    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

19강 이진 트리 - 넓이 우선 순회(BFT; Breadth First Traversal)

BFT는 트리 구조에서 낮은 level 중 왼쪽 노드부터 순회하게 됩니다. 이로써 DFT와 달리 재귀적으로 구현이 불가합니다. 하지만 Queue를 사용하여 다음에 방문할 노드를 enqueue 해두고 dequeue 하게되면 각각의 level별로 노드를 순회하게 됩니다.

실습

목표: 넓이 우선 순회 기능을 구현

    def bft(self):
        traversal = []
        queue = ArrayQueue()

		# root 존재여부 확인
        if self.root:
            queue.enqueue(self.root)

		# 하위 노드를 queue에 추가하며 노드의 값을 저장
        while not queue.isEmpty():
            node = queue.dequeue()
            traversal.append(node.data)
            if node.left:
                queue.enqueue(node.left)
            if node.right:
                queue.enqueue(node.right)

        return traversal

20강. 이진 탐색 트리(Bianry Search Trees) (1)

시간복잡도
1. Search Operation - O(n)
2. Insertion Operation - O(1)
3. Deletion Operation - O(n)

퀵정렬의 알고리즘을 트리의 형태로 접근하는 방식으로 생각하면 될 것 같다.

실습

목표: BST 에 insert 기능을 구현

    def insert(self, key, data):
	    # 키 중복시 예외
        if self.key is key:
            raise KeyError('inserted key is duplicated')

        # key의 비중 확인
        if self.key > key:
            # 하위노드 존재여부 대응
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif self.key < key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
                
        return True

21강. 이진 탐색 트리(Binary Search Trees) (2)

트리노드 삭제시 고려사항 참조

  1. 하위노드 X
  2. 1개의 하위노드
  3. 2개의 하위노드

3번을 처리하며 1, 2의 과정 모두 처리가능

def remove(self, key):
    node, parent = self.lookup(key)

    if node:
        nChildren = node.countChildren()
        
        if nChildren is 0: #하위노드 0개
            if parent:
                if node.key is parent.left.key:
                    parent.left = None
                else:
                    parent.right = None
            else:
                self.root = None
            
        elif nChildren is 1: #하위노드 1개
            childNode = None
            if node.left:
                childNode = node.left
            else:
                childNode = node.right
                
            if parent:
                if node.key is parent.left.key:
                    parent.left = childNode
                else:
                    parent.right = childNode
            else:
                self.root = childNode
                
        else: #하위노드 2개
            parent = node
            successor = node.right
            while successor.left:
                parent = successor
                successor = successor.left
                
            node.key = successor.key
            node.data = successor.data
            
            if successor.key is parent.left.key:
                parent.left = successor.right
            else:
                parent.right = successor.right

        return True

    else:
        return False

22강. 힙(Heaps)

힙 (heap) 도 이진 트리의 한 종류이며 이진 힙 (binary heap) 이라고도 불립니다.

힙에는 최대 힙 (max heap) 과 최소 힙 (min heap) 이 있습니다. 최대 힙과 최소 힙은 데이터 원소의 순서 기준이 내림차순이냐 오름차순이냐만 달라지고 완전히 대칭이므로, 여기에서는 최대 힙을 기준으로 설명을 전개하겠습니다. 최대 힙은 세 가지의 성질을 유지하고 있는 이진 트리입니다. 그 세 가지 성질은:

  • 루트 노드가 항상 최댓값을 가진다.
  • 완전 이진 트리이다. (최하위 레벨을 제외하고 모든 레벨이 차있는 상태)
  • 최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.

완전이진트리의 제약조건으로 인해 log(n)에 비례하는 실행시간을 가짐

배열을 이용해 이진트리 표현시 index 는
*노드 번호 n 기준

  • 상위 : m // 2
  • 좌측 하위: 2 * n
  • 우측 하위: 2 * n + 1

실습

목표: 새로운 노드 추가

    def insert(self, item):
        self.data.append(item)
        index = len(self.data)-1
        
        while index > 1:
            if(self.data[index] > self.data[index // 2]):
	            # 아래 방법으로도 손쉽게 값 교환을 할 수 있었다.
	            # self.data[index], self.data[index // 2] = self.data[index // 2], self.data[index]
                self.data[index] = self.data[index // 2]
                self.data[index // 2] = item
                index = index // 2
            else:
                break

23강. 힙(Heaps) (2)

최대 힙에서의 삭제. logn의 복잡도
1. 루트노드의 제거 (루트노드에 최대값이 위치)
2. 트리의 마지막 노드를 루트노드로 이동
3. 양쪽 자식노드보다 작을때 까지 서로 값을 교환 (자식노드 중 둘다 클경우 더 큰쪽으로)

최대/최소 힙의 응용

우선 순위 큐 (priority queue)
삽입(enqueue)시, 느슨한 정렬(=반정렬; 큰값이 상위, 작은값이 하위에 있음)을 이루고 있도록 함. O(logn) 의 복잡도
출력(dequeue)시, 최대값을 순서대로 추출. O(logn) 의 복잡도

힙 정렬 (heap sort)
정렬되지 않은 원소를 최대힙에 삽입, O(logn) X 힙이 빌때까지 삭제순으로 정렬, O(logn) = O(nlogn)

좋은 웹페이지 즐겨찾기