알고리즘 강의 (22) 썸네일형 리스트형 [알고리즘 강의] 파트15. 환형 큐(Circular Queues) 큐(Queue)의 활용 - 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로(asynchronously) 일어나는 경우 - 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 - 자료를 이용하는 작업이 여러 곳에서 일어나는 경우 - 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우 - 자료를 처리해서 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우 환형 큐 (Circular Queue) - 정해진 개수의 저장 공간을 빙 돌려가며 이용 - 큐가 가득 차면? -> 더이상 원소를 넣을 수 없음 (큐 길이를 기억하고 있어야) - rear: 데이터를 집어 넣는 부분 (포인터) - front: 데이터를 꺼내는 부분 (포인터) Q.enqueue(.. [알고리즘 강의] 파트14. 큐(Queues) 큐 (Queue) 자료 (data element)를 보관할 수 있는 (선형) 구조 선입선출 (FIFO - First-In First-Out) 특징을 가지는 선형 자료구조 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 -> 인큐(enqueue) 연산 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음 -> 디큐(dequeue) 연산 큐의 동작 Q = Queue() # 초기 상태 - 비어 있는 큐 (empty queue) Q.enqueue(A) # 데이터 원소 A를 큐에 추가 Q.enqueue(B) # 데이터 원소 B를 큐에 추가 r1 = Q.dequeue() # A를 꺼냄 r2 = Q.dequeue() # B를 꺼냄 큐의 추상적 자료구조 구현 (1) 배열 (array) 을 이용하여 구현 - Pyth.. [알고리즘 강의] 파트13. 스택의 응용: 후위 표기 수식 계산 중위 표기법과 후위 표기법 중위 표기법 (infix notation) - 연산자가 피연산자들의 사이에 위치 (A + B) * (C + D) 후위 표기법 (postfix notation) - 연산자가 피연산자들의 뒤에 위치 A B + C D + * 후위 표기식의 계산 알고리즘의 설계 후위 표현식을 왼쪽부터 한 글자씩 읽어서 피연산자이면 스택에 push 연산자를 만나면 스택에서 pop -> (1), 또 pop -> (2) (2) 연산 (1) 을 계산, 이 결과를 스택에 push 수식의 끝에 도달하면 스택에서 pop -> 이것이 계산 결과 실습 과제 - 후위표현 수식 계산 class ArrayStack: def __init__(self): self.data = [] def size(self): return l.. [알고리즘 강의] 파트12. 스택의 응용: 수식의 후위 표기법 중위 표기법과 후위 표기법 중위 표기법 (infix notation) - 연산자가 피연산자들의 사이에 위치 - 우리가 익숙한 표기법 후위 표기법 (postfix notation) - 연산자가 피연산자들의 뒤에 위치 중위 표현식 -> 후위 표현식 - 피연산자는 그냥 출력 - 첫 연산자는 스택에 푸시 - 다음 연산자의 경우 스택에 들어있던 연산자의 우선순위가 같거나 높으면 스택에 들어있던 연산자를 pop한 후에 스택에 푸시, 우선순위가 낮을 경우 그냥 스택에 푸시 - 수식이 끝나는 지점에서 스택에 남아있는 연산자들을 모두 pop 괄호의 처리 [중위] (A + B) * C [후위] A B + C * 여는 괄호는 스택에 push 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop [중위] A * (B + C) .. [알고리즘 강의] 파트11. 스택(Stacks) 스택(Stack) - 자료 (data elemenet)를 보관할 수 있는 (선형) 구조 - 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 -> 푸시 (push) 연산 - 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있음 -> 팝 (pop) 연산 - 후입 선출 (LIFO - Last-In First-Out) 특징을 가지는 선형 자료구조 스택의 동작 S=Stack() S.push(A) S.push(B) r1 = S.pop() # B가 꺼내짐 r2 = S.pop() # A가 꺼내짐 스택에서 발생하는 오류 1) 비어 있는 스택에서 데이터 원소를 꺼내려 할 때 -> 스택 언더플로우 오류(stack underflow) 2) 꽉 찬 스택에 데이터 원소를 넣으려 할 때 -> 스택 오버플로우 오류(stack o.. [알고리즘 강의] 파트10. 양방향 연결 리스트(Doubly Linked Lists) 양방향 연결 리스트 (Doubly Linked Lists) 한 쪽으로만 링크를 연결하지 말고, 양쪽으로! -> 앞으로도 (다음 node) 뒤로도 (이전 node) 진행 가능 Node의 구조 확장 class Node: def __init__(self, item): self.data = item self.prev = None self.next = None 리스트 처음과 끝에 dummy node를 두자! -> 데이터를 담고 있는 node들은 모두 같은 모양 class DoublyLinkedList: def __init__(self, item): self.nodeCount = 0 self.head = Node(None) self.tail = Node(None) self.head.prev = None self.h.. [알고리즘 강의] 파트9. 연결 리스트(Linked Lists) (3) 연결 리스트가 힘을 발휘할 때 - 삽입과 삭제가 유연하다는 것이 가장 큰 장점 - 그런데 잠깐, 지난번에 구현한 코드는 삽입과 삭제에 효율적이지 못함 삽입과 삭제가 유연하다는 장점을 살리기 위해 새로운 메서드들을 만들자: - insertAfter(prev, newNode)-> 근데 맨 앞에는 어떻게? - popAfter(prev) -> 근데 맨 앞에서는 어떻게? 해결 방법: 조금 변형된 연결 리스트 class LinkedList: def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail = None self.head.next = self.tail 연산 정의 1. 길이 얻어내기 2. 리스트 순회 3. 특정 원소 참조(k번째) 4. 원소.. [알고리즘 강의] 파트8. 연결 리스트(Linked Lists) (2) 연결 리스트 연산 - 원소 삽입 def insertAt(self, pos, newNode): 1) pos가 가리키는 위치에 (1 prev 없음 -> Head 조정 피료 (2) 삽입하려는 위치가 리스트 맨 끝일 때 -> Tail 조정 필요 (3) 빈 리스트에 삽입할 때? -> (1), (2) 두 조건에 의해 처리됨 #참고: 전체 코드 class Node: def __init__(self, item): self.data = item self.next = None class LinkedList: def __init__(self): self.nodeCount = 0 self.head = None self.tail = None def __repr__(self): if self.nodeCount == 0: retu.. 이전 1 2 3 다음
