[Week2 자료구조/알고리즘] TIL 3일차 - 스택과 큐, 트리

TIL을 쓰는데 너무 오랜 시간이 걸리기 때문에, 매일 기록하기 위해선, 조금 단순화하기로 하였다.

스택과 큐의 개념에 대해서는 기존의 글을 참고하자.

 

 

[파이썬 기본 데이터 구조] 1. 스택과 큐

 

1) 스택

후위표기법

후위표기법은 대표적으로 스택을 활용하여 푸는 문제이다.

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

(A+B)*(C-D)

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

AB+CD-* : 앞의 연산자부터 처리

• 전위 표기법(prefix notation) : 연산자가 피연산자들 앞에 위치

*+AB-CD

 

강의에서는 중위표기법 → 후위표기법을 스택을 이용해서 변환하였다

 

(중위 표기법 -> 후위 표기법 변환) 로직

연산자 우선순위를 고려한다. 

피연산자 : 출력

연산자 : 우선순위를 고려하여 출력

• 스택에 push : 스택 맨 위의 연산자보다 우선순위가 높으면
• 스택에서 pop : 여는 괄호가 나온 경우, 우선순위가 같거나 낮은 경우, 남아있는 식이 없는 경우 모두 pop

 

연산자 우선순위 테이블(prec)

3	*	/
2	+	-
1	(

 

코드

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

    opStack = ArrayStack()
    postfixList = []
    for token in tokenList:
        if token=='(':
            opStack.push(token)
        elif token==')':
            while opStack.peek()!='(':
                postfixList.append(opStack.pop())
            opStack.pop()
        elif token not in prec.keys():
            postfixList.append(token)
        else:
            if opStack.isEmpty():
                opStack.push(token)
            else:
            	#연산자 우선순위 같거나 작으면 pop
                while opStack.isEmpty()!=True and prec[opStack.peek()]>=prec[token]:
                    postfixList.append(opStack.pop())
                opStack.push(token)
    #빈 스택이 될 때까지 출력
    while opStack.isEmpty()!=True:
        if opStack not in ['(', ')']:
            postfixList.append(opStack.pop())
        else:
            opStack.pop()
    return postfixList

 

(후위표기법 계산) 로직

피연산자 : 스택에 삽입

연산자 : 스택에 top, top-1 값을 이용하여 계산한 뒤 다시 push

* 이때, 주의할 것은 top-1 (연산자) top 순서여야 함을 유의하자(뺄셈, 나눗셈의 피연산자의 순서를 다르게 할 경우 결과가 달라진다)

후위 표기법이므로 연산자는 순서대로 계산하면 된다.

 

코드

def postfixEval(tokenList):
    valStack = ArrayStack()
    
    for token in tokenList:
        if type(token) is int:
            valStack.push(token)
        elif token == '*':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 * num2)
        elif token == '/':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 / num2)
        elif token == '+':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 + num2)
        elif token == '-':
            num2 = valStack.pop()
            num1 = valStack.pop()
            valStack.push(num1 - num2)
    
    return valStack.pop()

 

2) 큐

클래스 다이어그램

큐의 기본적인 클래스 다이어그램은 다음과 같다.

큐의 클래스 다이어그램

활용

자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우

자료를 이용하는 작업이 여러 곳에서 일어나는 경우

자료의 처리가 순차적으로 일어나야 하는 경우 사용된다.

 

보통 메모리의 크기가 무한하지 않으므로 원형큐를 이용해서 크기를 제한한다.

 

원형 큐(Circular Queue)

원형큐는 사용할 수 있는 공간의 크기를 제한해야 하기 때문에 다음의 함수를 이용한다.

isFull():Boolean

• front : 큐에 제일 먼저 들어간 원소를 가리킨다.
• rear : 큐에 제일 나중에 들어간 원소를 가리킨다.

앞의 포인터와 함수를 이용해서 함수를 구현할 수 있는데, 배열을 이용할 경우 인덱스는 0~(n-1)까지이다. 따라서 포인터를 변경하는 연산을 할 때,  (front or rear)%maxCount 처리해야 한다.

 

클래스 다이어그램

원형 큐 클래스 다이어그램

 

우선순위 큐(Priority Queue)

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

삽입 순서는 우선순위 낮은 것부터 → 큰 것으로 이루어지므로 pop 연산도 동일하게 일어난다.

 

활용

운영체제의 CPU 스케쥴러

 

구현

1. Enqueue 할 때 우선순위 순서를 유지하도록
2. Dequeue 할 때 우선순위 높은 것을 선택

2번의 경우 큐에 있는 모든 데이터를 살펴봐야 하므로 1번 방식이 조금 더 유리하다.

 

1. 선형 배열 이용
2. 연결 리스트 이용

Enqueue 할때 우선순위 순서를 유지하도록 하는 방법을 선택하면, 배열보다는 연결리스트를 이용하는 것이 유리하다. 그 이유는 배열의 경우 중간에 삽입하면 이후의 모든 원소들을 한 칸씩 뒤로 이동시켜야 하지만, 연결리스트는 단순히 앞 뒤의 연결만 바꾸면 되기 때문이다.

 

 

3) 트리

그래프의 일종으로, 노드가 엣지로 연결되어 있는 있는 자료구조

 

용어

• 루트 노드 (root node) : 가장 위에 위치한 노드
• 리프 노드 (leaf nodes) : 자식 노드가 없는 노드 = degree가 0인 노드
• 내부 노드 (internal nodes) : 루트, 리프 노드가 아닌 나머지의 노드
• 부모 (parent) 노드 : 하나의 간선으로 연결된 노드 중 상위 노드
• 자식 (child) 노드 : 하나의 간선으로 연결된 노드 중 하위 노드
• 노드의 수준 (level) : 루트 노드 기준 0으로, 루트 노드에서부터 몇 개의 간선을 거치는지(거리)
• 노드의 차수 (degree) : 자식 노드의 
• 트리의 높이 (height) , 깊이 (depth) : 트리의 최대 수준(level)+1
• 부분 트리 (서브트리; subtrees) : 트리의 일부

 

이진트리(binary tree)

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

 

포화 이진트리 (full binary trees)

모든 레벨에서 2개의 자식 노드들이 모두 채워져 있는 이진트리

 

완전 이진트리 (complete binary trees)

높이가 k라고 가정한다면,

k-2번째 레벨은 자식 노드가 두 2개이고,

k-1번째 레벨은 자식 노드가 왼쪽부터 순차적으로 채워져 있는 이진 트리

 

 

구현

이진트리를 링크드리스트로 구현해 보자.

노드와 트리의 클래스 다이어그램은 다음과 같다.

 

클래스 다이어그램

이진 트리에서 사용되는 노드와 트리 클래스 다이어그램

• size() : 전체 노드의 개수 = left서브트리+right서브트리+root노드
• depth() : max(left서브트리의 depth, right 서브트리의 depth)+1
• traverse()
  • 깊이 우선 순회(재귀적 방법으로 구현)
    • 중위 순회(inorder traversal) : left → root → right
    • 전위 순회(preorder traversal) : root → left → right
    • 후위 순회(postorder traversal) : left → right → root
  • 넓이 우선 순회 : 수준이 낮은 노드부터 방문(루트노드 →부모노드 →자식노드)

 

이진탐색트리(binary search tree tree)

모든 노드들이 아래의 조건을 만족하는 이진트리

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

 

그렇다면, 왜 이진탐색 트리를 쓰는지를 알아보자. 그러기 위해서 정렬된 배열을 이용한 탐색에 비해 이진 탐색이 갖는 이점은 찾아보자.

트리구조이므로 데이터 원소의 추가, 삭제가 용이하지만, 공간 복잡도가 증가하고 평균 O(log n)의 탐색 복잡도를 갖는다.

보통 한쪽으로 치우치는 이진트리의 경우 탐색에 매우 불리하다.

(따라서 더 나은 성능을 보이게 하는, 높이의 균형을 유지하게 하는 이진트리 연산들이 있다 tradeoff-삽입, 삭제가 덜 유연)

• AVL tree
• Red-black tree

 

 

구현

이진 탐색트리를 구현하기 위한 노드와 이진탐색트리의 클래스다이어그램은 다음과 같다

 

클래스 다이어그램

• insert(key, data) : 트리에 key 자리에 데이터 원소를 추가
  • key가 작은 경우 → 왼쪽 서브트리로 내려가 연산 수행 or 왼쪽에 삽입
  • key가 큰 경우 → 오른쪽 서브트리로 내려가 연산 수행 or 오른쪽에 삽입
  • key가 같은 경우 → keyError 발생
• remove(key) : 트리에 key 데이터 원소를 삭제
  • 자식 노드를 가지고 있지 않은 경우 → parent의 연결만 끊기
  • 자식 노드를 하나 가지고 있는 경우 → 자식 노드를 parent에 연결
  • 자식 노드를 두 개 가지고 있는 경우 → 그다음 키를 가진 자식 노드를 parent에 연결
• lookup(key) : key에 해당하는 노드와 부모노드를 반환
• inorder() : key의 순서대로 데이터 원소를 나열
• min() : 최소키를 가지는 원소 탐색
• max() : 최대키를 가지는 원소 탐색

 

모든 코드는 깃허브를 참고하자.