TIL 20.12.02 - infix to postfix, 큐, 트리, 힙
1. 중위표기법 -> 후위표기법 ( infix to postfix )
1) 중위 표기법 (infix notation)
ex. (A + B) * (C + D)
연산자가 피연산자들의 사이에 위치
2) 후위 표기법 (postfix notation)
ex. A B + C D + *
연산자가 피연산자들의 뒤에 위치
괄호를 사용하지 않는다.
3) infix to postfix 규칙
- 피연산자는 바로 출력.
- 연산자이면 스택에 push.
이 때, push할 연산자가 스택의 top 연산자에 비해 우선순위가 높을 때까지 스택에서 pop하여 출력한 후 해당 연산자를 push한다. 즉, 자신보다 낮은 우선순위의 연산자만 남겨두고, 자신보다 높거나 같은 우선순위의 연산자는 pop하여 출력.
- 여는 괄호는 스택에 push.
- 닫는 괄호는 여는 괄호가 나올 때까지 pop하여 연산자들만 출력. (즉, 괄호는 출력하지 않음.)
2. Queue
자료를 보관할 수 있는 선형 구조.
선입선출 구조. FIFO (First In First Out)
1) 연산
| 연산 | 설명 | 배열로 구현시 연산 복잡도 | 이중연결리스트로 구현시 연산 복잡도 |
| size() | 현재 큐에 들어있는 데이터 원소의 개수. | O(1) | |
| isEmpty() | 큐가 비어있는지 알려줌. | O(1) | |
| enqueue() | 데이터 원소를 큐에 넣는 동작. | O(1) | |
| dequeue() | 큐로부터 데이터 원소를 꺼내는 동작. | O(N) | |
| peek() | 큐의 맨 앞에 저장된 데이터 원소를 반환. 제거하지는 않는다. | O(1) |
2) Circular Queue (환형 큐)
- isFull() : 큐가 꽉 차있는지 판단.
- front와 rear를 적절히 계산하여 정해진 길이의 배열을 환형으로 재활용한다.
3) Priority Queue (우선순위 큐)
- 운영체제의 CPU스케줄러
- 구현방식
Enqueue할 때 우선순위 순서를 유지하도록 or Dequeue할 때 우선순위 높은 것을 선택.
Enqueue할 때 우선순위 순서를 유지하는 것이 더 유리하다.
선형배열, 연결리스트로 구현할 수 있다.
선형배열은 공간의 측면에서 유리하고, 연결리스트는 노드 사이 삽입 및 삭제가 쉬우므로 시간복잡도 측면에서 유리하다.
3. Tree
1) 용어
(1) 수준 (level)
루트노드로부터 몇 개의 edge를 거쳐서 해당 노드로 올 수 있는지.
루트노드는 level 0이다.
(2) 트리의 높이(height) = 깊이(depth)
최대 수준(level) + 1이다.
(3) 차수 (Degree)
각 노드의 차수는 자식(서브트리)의 개수이다.
차수가 0인 노드는 leaf node이다.
(4) 이진 트리 (Binary Tree)
모든 노드의 차수가 2이하인 트리이다.
(5) 포화 이진 트리 (Full Binary Tree)
모든 레벨에서 노드들이 모두 채워져 있는 이진 트리.
높이가 k인 포화이진트리는 전체 노드가 2^k -1 개이다.
(6) 완전 이진 트리 (Complete Binary Tree)
높이가 k인 완전 이진 트리는, 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리이고
레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리이다.
2) Traversal (순회)
(1) DFS (깊이 우선 순회, depth first traversal)
재귀함수로 구현 가능.
스택으로 구현.
- 전위 순회 (pre-order traversal) : 부모 -> 왼 -> 오른
- 중위 순회 (in-order traversal) : 왼 -> 부모 -> 오른
- 후위 순회 (post-order traversal) : 왼-> 오른 -> 부모
(2) BFS (넓이 우선 순회, breadth first traversal)
수준이 낮은 노드를 우선으로 방문.
큐로 구현.
3) BST (이진 탐색 트리 = Binary Search Tree)
- 모든 노드에 대해서,
왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고,
오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리.
이 강의에서는 같은 값을 갖는 데이터는 없다고 가정.
- 데이터 검색을 쉽게 할 수 있다. Binary Search(정렬된 배열을 이용하는 탐색 방법)와 비슷하다.
- (장점) 데이터 원소의 추가, 삭제가 용이하다.
- (단점) 공간 소요가 크다.
4. Heap (힙)
이진 트리의 한 종류.
루트 노드가 언제나 최댓값 또는 최솟값을 가진다.
완전 이진 트리이다. (Full Binary Tree) -> 배열로 구현하는 것도 좋다.
1) 새 원소 삽입
- 힙의 맨 끝에 새로운 원소 삽입
- 부모노드의 키 값과 비교하며 힙 재정렬
2) 원소 삭제
- 힙의 루트 노드 삭제
- 힙의 맨 마지막 노드를 루트 자리로 끌어올림
- 루트노드부터 자식 노드의 키 값과 비교하며 힙 재정렬
3) 부모노드와 자식노드의 관계
왼쪽 자식 인덱스 = (부모 인덱스) * 2
오른쪽 자식 인덱스 = (부모 인덱스) * 2 + 1
부모 인덱스 = (자식 인덱스) / 2 (몫만 취함)
5. 파이썬 문법
1) 두 변수의 값 바꾸기
a, b = b, a