Study/Data Structure4 [자료구조] 수식의 전위, 중위, 후위 표기법 수식의 표기법 전위(prefix) 표기법 연산자를 먼저 표시한 후, 피연산자를 나중에 표시 ex) +AB 중위(infix) 표기법 피연산자 사이에 연산자 표기, 대수학에의 표기법 ex) A+B 후위(postfix) 표기법 피연산자를 먼저 표시, 연산자를 나중에 표시 ex) AB+ 전위 표기법 변환 > A*B+(C-D)*E 1. 중위 표기법에서 순서(우선순위)에 맞게 괄호로 묶어 준다. ((A*B)+((C-D)*E)) 2. 연산자를 해당 괄호 바로 앞(왼쪽)로 옮긴다. +(*(AB)*(-(CD)E)) 3. 괄호를 제거한다. +*AB*-CDE 후위 표기법 변환 > A*B+(C-D)*E 1. 중위 표기법에서 순서(우선순위)에 맞게 괄호로 묶어 준다. ((A*B)+((.. 2021. 7. 21. [자료구조] 데큐(deque; double-ended queue) 데큐(deque; double-ended queue) 리스트의 양쪽 끝에서 삽입과 삭제를 모두 허용하는 자료의 구조. 이것은 스택과 큐의 자료 구조를 복합한 형태 Deque import 및 생성 from collections import deque # deque 생성 deq = deque() Deque 원소 삽입 # item을 deque 오른쪽 끝에 삽입 deq.append(item) # item을 deque 왼쪽 끝에 삽입 deq.appendleft(item) Deque 원소 삭제 # deque 오른쪽 끝에 있는 item을 pop한 후 삭제 deq.pop() # deque 왼쪽 끝에 있는 item을 pop한 후 삭제 deq.popleft() # item을 deque에서 찾아 삭제 deq.remove(i.. 2021. 7. 19. [자료구조] 우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue) 들어간 순서에 상관없이 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 스택 : 원소들은 후입 선출 순으로 처리된다. (LIFO; Last In First Out) 큐 : 원소들은 선입 선출 순으로 처리된다. (FIFO; First In First Out) 우선순위 큐를 구현하는 방법 1. List(리스트) : 삽입 - O(1), 삭제 - O(N) 2. Heap(힙) : 삽입 - O(logN), 삭제 - O(logN) 우선순위 큐 import 및 생성 from queue import PriorityQueue # 우선순위 큐 생성 que = PriorityQueue() 우선순위 큐 원소 추가 - .put() que.put(1) que.put(3) que.put.. 2021. 7. 19. [자료구조] 힙(heap) 힙(heap) 최댓값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree) * 이진 트리 : 한 노드의 자식 노드가 최대 2개인 트리 * 완전 이진 트리 : 노드를 삽입할때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 * 이진 탐색 트리 : 왼쪽 자식 노드 값이 가장 작고, 그 다음은 부모, 그 다음은 오른 쪽 자식 노드가 가장 크다. 리스트에 데이터를 넣고, 최댓값과 최소값을 찾을 때 시간 복잡도 : O(n) 힙에 데이터를 넣고, 최댓값과 최소값을 찾을 때 시간 복잡도 : O(logn) 최소힙 (Min Heap) 각 노드의 값이 자식 노드보다 작거나 같다. 자식 노드 값은 오른쪽이 클수도, 왼쪽이 클수도 있다. 위의 힙을 리스트의 형태로 구현하면 [-.. 2021. 7. 8. 이전 1 다음
