DailyStudyNote

우선순위 큐(Priority Queue) 큐가 FIFO(First-In First-Out) 방식을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 우선 순위 큐 구현 [2가지 방식] 1. Enqueue 할 때 우선순위 순서를 유지하도록 한다. 2. Dequeue 할 때 우선순위 높은 것을 선택한다. → (1) 방식이 더 유리하다. [2가지 구현 방식] 1. 선형 배열 이용 2. 연결 리스트 이용 → (2) 방식이 시간적으로 더 유리하다. 문1. 우선순위 큐의 enqueue 연산 구현 class Node: def __init__(self, item): self.data = item self.prev = None self.next = None class DoublyLinkedList: def ..

'어서와! 자료구조와 알고리즘은 처음이지?' 큐의 활용 1. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비 동기적으로(asynchronously) 일어나는 경우 2. 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 3. 자료를 이용하는 작업이 여러 곳에서 일어나는 경우 4. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우 5. 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우 환형 큐 정해진 개수의 저장공간을 빙 돌려가며 이용하는 큐 환형 큐의 추상적 자료구조 구현 연산의 정의 1. size() - 현재 큐에 들어있는 데이터 원소의 수를 구한다. 2. isEmpty() - 현재 큐가 비어 있는지를 판단한다. 3. isF..

'어서와! 자료구조와 알고리즘은 처음이지?' 큐(Queue) ✔ 자료를 보관할 수 있는 선형 구조 ✔ 데이터 삽입 시에는 한 쪽 끝에서 밀어 넣어야 한다. → 인큐(enqueue) 연산 ✔ 데이터 꺼낼 시에는 반대쪽에서 꺼내야 한다. → 디큐(dequeue) 연산 ✔ 선입선출(FIFO, First-In First-Out) 특징을 가진다. 큐의 추상적 자료구조 구현 1. 배열(Array)를 이용하여 구현한다. → 파이썬 리스트와 메서드를 이용 2. 연결 리스트(Linked list)를 이용하여 구현한다. → 양 방향 연결리스트를 이용 연산의 정의 1. size() - 현재 큐에 들어있는 데이터 원소의 수를 구한다. 2. inEmpty() - 현재 큐가 비어있는지를 판단한다. 3. enqueue(x) - 데..

'어서와! 자료구조와 알고리즘은 처음이지?' 후위 표기 수식 계산 → Stack() ✔ 알고리즘 설계 1. 후위 표현식을 왼쪽 부터 한 글자씩 읽어서 피 연산자이면 스택에 push 2. 연산자를 만나면 스택에서 pop → (1) , 또 pop → (2) (2) 연산 (1) 을 계산 후 이 결과를 스택에 push 3. 수식의 끝에 도달하면 스택에서 pop() → 계산 결과 [ 문1. 후위 표현 수식 계산 ] ''' 1. for 문 돌면서 피 연산자인 경우 스택에 push 2. 연산자 만나면 스택에서 pop --> 1 pop --> 2 (2) 연산자 (1) 을 계산 후 이 결과를 스택에 push 3. 수식의 끝에 도달하면 스택에서 pop ''' class ArrayStack: def __init__(self..

'어서와! 자료구조와 알고리즘은 처음이지?' 중위표기법과 후위표기법 1) 중위 표기법 ✔ 연산자가 피 연산자들의 사이에 위치 (A+B) * (C+D) 2) 후위 표기법 ✔ 연산자가 피 연산자들의 뒤에 위치 AB+CD+* 3) 중위 표현식 → 후위 표현식 : 스택(Stack) 이용 알고리즘 설계 1. 연산자의 우선순위 설정 prec = { '*' : 3, '/' :3, '+' : 2, '-' :2, '(' :1 } 2. 중위 표현식을 왼쪽부터 한 글자 씩 읽어서 피연산자 이면 그냥 출력 3. '(' 이면 스택에 push, ')' 이면 '('이 나올 때까지 스택에서 pop 출력 4. 연산자이면 스택에서 그 보다 높거나 같은 우선 순위 것들을 pop 출력, 현재 만난 연산자는 스택에 push 3. 수식 끝까지..

'어서와! 자료구조와 알고리즘은 처음이지?' 스택(Stack) ✔ 자료(data element)를 보관할 수 있는 선형 구조이다. ✔ 데이터를 넣을 때는 한 쪽 끝에서 밀어넣어야 한다 (push 연산). ✔ 데이터를 꺼낼 때에는 데이터를 밀어 넣었던 쪽과 같은 쪽에서 뽑아 꺼내야 하는 제약이 있다 (pop 연산). ✔ 후입선출(LIFO, Last- In First - Out) 특징을 가진다. 스택에서 발생하는 오류 1. 비어있는 스택에서 데이터 원소를 꺼내려 하는 경우 ✔ 스택 언더 플로우 (Stack underflow) 2. 꽉 찬 스택에 데이터 원소를 넣으려 할 때 ✔ 스택 오버플로우(Stack overflow) 스택의 추상적 자료구조 구현 1. 배열(Array)을 이용하여 구현한다. ✔ Python..

'어서와! 자료구조와 알고리즘은 처음이지?' 양방향 연결리스트(이중 연결리스트) 양 쪽으로 링크를 연결하여 앞으로도 (다음 Node) 뒤로도 (이전 Node) 로도 진행이 가능한 연결리스트이다. 리스트의 처음과 끝에 Dummy Node를 두어 데이터를 담고 있는 Node들이 모두 같은 모양이 되도록 한다. class Node: def __init__(self, item): self.data = item self.prev = None self.next = None class DoubleLinkedList: def __init__(self, item): self.node_count = 0 self.head = Node(None) self.tail = Node(None) self.head.prev = None..

'어서와! 자료구조와 알고리즘은 처음이지?' 드디어 금요일이다........! 😆 연결리스트 장점 삽입과 삭제가 유연하다는 것이 가장 큰 장점 ! "특정 원소의 바로 다음"을 지정하여 원소를 삽입/삭제 하는 연산 정의 # 새로운 메서드 def insert_after(prev, newNode): #--> prev 노드 뒤에 newNode 삽입 def pop_after(prev): # --> prev 노드 뒤에 노드 삭제 맨 앞에 원소를 삽입하거나 삭제하는 연산을 이전과 동일한 방식으로 해결하기 위해 연결 리스트의 맨 앞에다가 데이터 원소를 담고 있지 않은 그냥 자리만 차지하는 노드인 더미 노드(dummy node)를 추가한다. # head가 가리키는 부분이 데이터를 담고 있지 않은 Node(None) 임을..