개념정리3 [개념정리] 스택(Stack) | (python,파이썬) 스택이란? ○스택(stack) ▷ Stack은 가장 최근에 저장된 값 다음에 저장되며, 가장 최근에 저장된 값이 먼저 나가는 자료구조이다. ▷ 스택은 push 연산으로 값을 차례대로 삽입하고, pop연산으로 가장 최근 저장된 값을 삭제한다. → 이 삽입 / 삭제 원칙을 Last-in First-Out 원칙이라고 한다. ▷ 스택의 사용 예시 : 괄호 맞추기, infix수식 → postfix수식 변환, 계산기 등 ○스택(stack) Class구현 class Stack: def __init__(self): self.items = []# 데이터 저장을 위한 리스트 준비 def push(self, val): self.items.append(val) def pop(self): try:# pop할 아이템이 없으면 r.. 2021. 7. 22. [개념정리] 큐(Queue)| (python, 파이썬) 큐(Queue)란? ○큐(Queue) ▷ Queue은 가장 최근에 저장된 값 다음에 저장되며, 가장 처음에 저장된 값이 먼저 나가는 자료구조이다. ▷ 큐는 enqueue 연산으로 값을 차례대로 삽입하고, dequeue 연산으로 가장 처음에 저장된 값을 삭제한다. → 이 삽입 / 삭제 원칙을 First-in First-Out 원칙이라고 한다. ▷ front_index를 마련하여 dequeue 시간을 상수시간으로 관리 할 수 있다 ! ▷ 파이썬에 내장되어있는 자료구조이지만, 한번씩 구현해보며 정확히 이해하자 ! ○큐(Queue) Class구현 class Queue: def __init__(self): self.items = []# 데이터 저장을 위한 리스트 준비 self.front_index = 0# 다음 .. 2021. 7. 22. [개념정리] 유니온 파인드(Union-Find) by "union by rank"| (python, 파이썬) 유니온 파인드(Union-Find) 알고리즘이란 ? ▷유니온 파인드는 그래프 알고리즘 중 하나로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. → "합집합 판별" 이라고 생각하면 편할 거 같다 ! ▷이는 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다. ▷새로운 집합을 생성하는 make_set 연산 노드를 합치는 union 연산과 노드의 루트 노드를 찾는 find 연산으로 이루어진다. ▷생성된 노드의 부모 노드는 자기 자신이다. ▷rank는 union을 할때, 두 집합에 대한 부모, 자식 관계를 결정할때 사용한다.(시간 단축을 위함) → 트리의 높이라고 생각하면 될 거 같다. 노드 Class class Node : def __init__(self,key): self.key.. 2021. 7. 21. 이전 1 다음
