최대 힙의 성질최대 힙은 완전히 크기 순서대로 정렬되어 있지는 않다. 따라서 탐색 연산은 지원하지 않는다.루트 노드가 항상 최댓값을 가진다.완전 이진 트리이다.최대 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 최대 힙이다.배열을 이용한 이진트리의 표현왜 트리와는 다르게 heap은 배열을 사용하여 표현할까?Tree를 구현할 때 흔히 사용하는 linked list 방식으로 하면 마지막 인덱스에 데이터 추가하는 일이 쉽지 않다.마지막 리스트를 찾기위한 연산의 복잡도는 트리의 높이만큼 탐색해야하기 때문에 O(h)임.힙은 완전 이진트리라는 것이 보장된 형태이 기 때문에, 마지막 레벨을 제외한 모든 레벨의 노드가 가득 채워져있다. 따라서 완전 이진트리의 삽입은 배열 끝 인덱스에 append해주는 것과 같으며,..

이진 트리의 삭제 조건이진 트리의 remove는 3가지 조건을 따로 살펴보아야한다.삭제되는 노드가말단(leaf) 노드인 경우자식을 하나만 가지고 있는 경우자식을 둘 가지고 있는 경우1. 말단(leaf) 노드인 경우말단 노드가 위치하는 부모노드의 참조를 (left or right) None으로 변경해주기만 하면됨.즉, 말단 노드가 왼쪽에 있는지 오른쪽에 있는지 확인 후 부모 노드의 참조값만 None으로 변경.2. 자식을 하나만 가지고 있는 경우삭제되는 노드 자리에 그 자식을 대신 배치즉, 자식이 왼쪽에 있는지 오른쪽에 있는지 확인 후 부모 노드에 자식을 배치3. 자식을 둘 가지고 있는 경우삭제되는 노드(A)보다 바로 다음 큰 key를 가지는 노드(B)를 찾는다.삭제하고자 하는 노드(A)와 key를 가지는 ..

넓이 우선 탐색의 원칙수준 (level) 이 낮은 노드를 우선으로 방문한다.같은 수준의 노드 사이에서는부모 노드의 방문 순서에 따라 방문왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문  한 노드를 방문했을 때, 나중에 방문할 노드들을 순서대로 기록해두어야한다. → 큐(queue)를 이용해보자.넓이 우선 순회 알고리즘 설계A를 큐에 넣고 dequeue()A의 자식 노드를 왼쪽에서 부터 enqueue() | B , C |B를 dequeue()B의 자식 노드를 왼쪽 부터 enqueue() | C , D , E |C를 dequeue() | D , E |C의 자식 노드를 왼쪽 부터 enqueue() | D , E , F , G |… 반복 , 큐에 남은 노드가 없으면 종료결과넓이 우선 순회 알고리즘 구현(빈 리스트 초..

트리트리들은 데이터베이스 시스템 또는 검색 엔진 등에서 아주 많이 이용된다.트리를 딱딱하게 말하면, 순환하는 길이 없는 그래프 (graph) 로 정의된다.트리 용어노드 (nodes)간선 (edges)루트 노드 (root node), 리프 노드 (leaf nodes), 내부 노드 (internal nodes)부모 (parent) 노드와 자식 (child) 노드노드의 수준 (level)노드의 차수 (degree)트리의 높이 (height) - 또는, 깊이 (depth) -부분 트리 (서브트리; subtrees)이진 트리 (binary trees)포화 이진 트리 (full binary trees)완전 이진 트리 (complete binary trees)트리 종류포화 이진트리완전 이진트리 (리프 노드 위는 모두..

우선순위 큐무조건 선입선출의 개념에 의한 것이 아닌, 우선순위가 높은 순서대로 dequeue 되는 것을 의미한다.이는 운영체제에서 CPU 스케줄러를 구현에서 사용하고 전공 강의에서 접해본 적이 있다. 우선순위 큐는 크게 두가지 접근 방법이 있다.큐에 원소를 넣을 때 (enqueue 할 때) 우선순위 순서대로 정렬해 두는 방법큐에서 원소를 꺼낼 때 (dequeue 할 때) 우선순위가 가장 높은 것을 선택하는 방법1번, enqueue할 경우 우선순위 순서대로 정렬해 두는 방법이 복잡도 차원에서 좀 더 유리하다. 그 이유는 이미 큐를 정렬 상태로 두기 때문에 우선순위에 따라 큐를 정렬하기 위한 삽입 연산을 줄일 수 있기 때문이다. 즉, 이미 정렬 되어 있기에 큐의 모든 원소의 우선순위를 조회할 필요가 없기 때..

큐큐의 동작방식은 선입 선출(FIFO)이다.동작 방식동작방식의 도식화는 아래와 같다. enqueue() : 후순위로 밀어 넣다. - 복잡도 O(1)dequeue() : 선순위를 빼낸다. - 복잡도 O(n)배열에서의 dequeue()를 맨 앞의 원소를 빼면 다른 모든 원소를 한칸씩 이동해야하기 때문에 복잡도는 O(n)이다.→ 따라서 이를 해결하기 위해 환형 큐를 이용한다.사용처큐는 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우에 사용한다.  나도 프로젝트를 이용하면서 많은 Message queue를 사용해본적이 있으며, 실제로 네트워크 강의를 들으면서 패킷이 전송이 큐(버퍼)를 통해 이루어지는 것을 학습했었다.환형 큐배열에서 dequeue()의 복잡도(O(n))을 줄이기 위해..

후위 표기 수식 계산이전 강의에서는 중위표현식을 후위 표기식으로 전환하는 알고리즘을 학습했다.이제는 전환된 후위 표기식을 스택을 이용해 계산해보자.스택 기반 후위 표기식을 이용하여 계산 효율성을 높일 수 있다는 것을 이해해보자.후위 표기식의 계산쉽게 생각해서 피연산자를 순차적으로 스택에 넣은 다음 연산자를 만날 경우 해당 피연산자를 연산하면 된다.계산 알고리즘 순서수식을 왼쪽부터 차례대로 스캔한다피연산자가 나타나면, 스택에 넣어 둔다.연산자가 나타나면 , 스택에 들어 있는 피연산자를 두 개 꺼내어 연산한다.그 결과를 스택에 다시 넣어 둔다.스캔이 끝나면 가장 마지막 값을 pop한다.실습 class ArrayStack: def __init__(self): self.data = [] ..

스택 & 후위 연산자스택자료를 보관할 수 있는 선형 구조를 말한다. 단, 넣을 때 같은 입구에 밀어 넣어야하고, 꺼낼 때에도 같은 입구로 뽑아 꺼내야하는 제약이 있다. (밀어 넣다 → push, 뽑아 올리다 → pop)컴퓨터 내부에서 프로그램이 실행할 때 함수 호출이 일어나고 함수들이 리턴하면 마지막 호출된 곳으로 돌아가는 동작을 구현하는 데에도 스택을 사용한다."재귀 함수" 가 줄줄이 호출되었다가 줄줄이 리턴하는 모습호출 시: 함수가 호출되면 현재 함수의 상태가 스택에 푸시(push)된다.리턴 시: 함수가 리턴되면 스택에서 해당 함수의 상태가 팝(pop)되고, 이전에 호출된 함수로 돌아간다.1. 호출: factorial(4) [ factorial(4) ] 2. 호출: factorial(3) ..

더미 양방향 연결리스트 구조class Node: def __init__(self, item): self.data = item self.prev = None self.next = Noneclass DoublyLinkedList: def __init__(self): self.nodeCount = 0 self.head = Node(None) self.tail = Node(None) self.head.prev = None self.head.next = self.tail self.tail.prev = self.head self.tail.next = None더미 양방향 연결리스트의..