본문 바로가기

전체 글

 (112)
[알고리즘 강의] 파트17. 트리(Trees) 트리 (Tree) 정점 (node) 과 간선 (edge) 을 이용하여 데이터의 배치 형태를 추상화한 자료 구조 용어 정리 - 루트 (root) 노드: A - 리프 (leaf) 노드: G, H, J, E, K - 내부 (internal) 노드 - B,D,C,F - 부모 (parent) 노드 ex. 노드 D는 노드 G,H,J의 부모 - 자식 (child) 노드 ex. 노드 E는 노드 C의 자식 - 노드 G,H,J는 서로 형제간 (sibling) - 조상 (ancestor): 부모의 부모(의 부모의...) - 후손(descendant): 자식의 자식(의 자식의...) 노드의 수준 (Level) Root node가 level 0 이며 아래로 내려갈수록 노드의 level 증가 ex. 위의 트리에서는 위부터 아래 ..
[알고리즘 강의] 파트16. 우선순위 큐(Priority Queues) 우선순위 큐 (Priority Queue) 큐가 FIFO (First-In First-Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식 우선순위 큐의 활용 - 운영체제의 CPU 스케줄러 우선순위 큐의 구현 서로 다른 두 가지 방식이 가능할 듯: (1) Enqueue 할 때 우선순위 순서를 유지하도록 (2) Dequeue 할 때 우선순위 높은 것을 선택 -> 어느 것이 더 유리할까? 1번 서로 다른 두 가지 재료를 이용할 수 있음: (1) 선형 배열 이용 (2) 연결 리스트 이용 -> 어느 것이 더 유리할까? - 시간면에선 (2) - 메모리면에선 (1) -> 시간적으로 유리한 걸 택하는 경우가 많음 실습 과제 - 우선순위 큐의 enqueue 연산 구현 class Node: def..
[알고리즘 강의] 파트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..

티스토리툴바