지난 학기들의 기록/알고리즘28 [실습] 삽입식 힙 생성 삽입식 힙 생성 포스트에 게시된 것은 알고리즘 수업자료에 대한 기록입니다. 제가 작성한 소스코드에 대한 카피를 금지합니다. 힙은 이진트리로 구현된 우선순위 큐다. 여기서 이진트리를 배열을 이용해서 구현하면 순차트리 형태, ==> 순차힙 연결리스트를 이용하면 연결트리 형태로 구현할 수 있다. ==> 연결힙 우선순위 큐의 각 항목은 (키, 원소) 쌍이며 이진트리의 각 노드로 구현된다. 이진트리의 루트에 최소 키를 저장한 경우 최소힙, 반대로 최대 키를 저장한 경우 최대힙이라고 부른다. 힙 생성은 삽입식과 상향식의 두 가지 방식이 있다. 삽입식은 모든 키 들이 미리 주어진 경우, 또는 키들이 차례로 주어지는 경우 양쪽에 적용이 가능하다. 상향식은 모든 키 들이 미리 주어진 경우에만 적용 가능하다. 즉, 다시 .. 2021. 9. 5. [강의노트] 우선순위 큐와 힙 우선순위 큐 우선순위 큐가 무엇인가? 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조. 데이터를 우선순위에 따라 처리하고 싶을 때 사용함. 스택 : 가장 나중에 삽입된 데이터를 추출 큐 : 가장 먼저 삽입된 데이터를 추출 우선순위 큐 : 가장 우선순위가 높은 데이터를 추출 우선순위 큐를 구현하는 방법 1. 단순히 리스트를 이용하여 구현. 2. 힙을 이용하여 구현 힙(Heap)의 특징 힙은 완전 이진 트리 자료구조의 일종이다. 여기서 완전 이진 트리란 힙의 높이를 h라 했을때 i=0 , . . ., h-1 에 대해 깊이 i인 노드가 2^i개 존재 하고 깊이 h-1 에서 내부노드(자식이 있는 노드)들은 외부노드(자식이 없는 노드)들의 왼쪽에 존재하는 트리 쉽게 말하면 루트 노드부터 시작해서 자식노드가 .. 2021. 9. 2. [C 알고리즘] 힙 정렬 - Heap Sort Algorithm 힙 정렬 알고리즘 - heap sort algorithm 2020. 9. 5. [C 알고리즘] 병합 정렬 - Merge Sort Algorithm 정렬 알고리즘에서 퀵 정렬을 배운뒤 병합정렬 알고리즘을 접해보았습니다. 나동빈님의 블로그와 유튜브 강의를 통해 개념을 학습했는데 설명이 잘되어있어서 참고용으로 기록을 하기 위해 포스트를 씁니다. 이해한 내용을 저만의 언어로 설명하면서 학습해보겠습니다 출처: https://blog.naver.com/ndb796/221227934987 7. 병합 정렬(Merge Sort) 지난 시간까지 시간 복잡도 O(N ^ 2)인 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘을 공부했습니다. 이어... blog.naver.com 병합 정렬은 시간복잡도 O(N*logN)을 가집니다. 코드에서도 알수있듯이 정렬을 분할해서 하기때문에 대표적인 분할정복 알고리즘이면서, 어떠한 경우에도 반씩 나누기때문에 최악의경우에도 시간복잡도 N.. 2020. 6. 14. 이전 1 ··· 3 4 5 6 7 다음
