지난 학기들의 기록59 [강의노트] 힙과 힙정렬 - 1 힙과 힙정렬 힙이란? 내부노드에 키를 저장하며 다음 두가지 속성을 만족하는 이진트리 ( 외부노드에는 키를 저장하지 않는다는 것 .) 힙순서(heap-order): 루트를 제외한 모든 내부노드 v에 대해, key(v) >= key(parent(v)) # 즉 자식노드가 부모노드보다 같거나 크다. ( 최소힙의 힙순서를 말함) 완전이진트리(complete binary tree): 힙의 높이를 h라 했을 때, i = 0 , ... , h - 1 에 대해 깊이 i인 노드가 2^i개 존재한다. # 즉 루트노드 부터 시작해서 트리의 하단으로 갈수록 2의 제곱만큼 개수가 늘어나는 것을 말함 깊이 h - 1 에서 내부노드들은 외부노드들의 왼쪽에 존재해야한다. # 왼쪽부터 채워지는 것을 말함 힙의 높이 n개의 키를 저장한 .. 2021. 9. 6. [실습] 삽입식 힙 생성 삽입식 힙 생성 포스트에 게시된 것은 알고리즘 수업자료에 대한 기록입니다. 제가 작성한 소스코드에 대한 카피를 금지합니다. 힙은 이진트리로 구현된 우선순위 큐다. 여기서 이진트리를 배열을 이용해서 구현하면 순차트리 형태, ==> 순차힙 연결리스트를 이용하면 연결트리 형태로 구현할 수 있다. ==> 연결힙 우선순위 큐의 각 항목은 (키, 원소) 쌍이며 이진트리의 각 노드로 구현된다. 이진트리의 루트에 최소 키를 저장한 경우 최소힙, 반대로 최대 키를 저장한 경우 최대힙이라고 부른다. 힙 생성은 삽입식과 상향식의 두 가지 방식이 있다. 삽입식은 모든 키 들이 미리 주어진 경우, 또는 키들이 차례로 주어지는 경우 양쪽에 적용이 가능하다. 상향식은 모든 키 들이 미리 주어진 경우에만 적용 가능하다. 즉, 다시 .. 2021. 9. 5. [강의노트] 우선순위 큐와 힙 우선순위 큐 우선순위 큐가 무엇인가? 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조. 데이터를 우선순위에 따라 처리하고 싶을 때 사용함. 스택 : 가장 나중에 삽입된 데이터를 추출 큐 : 가장 먼저 삽입된 데이터를 추출 우선순위 큐 : 가장 우선순위가 높은 데이터를 추출 우선순위 큐를 구현하는 방법 1. 단순히 리스트를 이용하여 구현. 2. 힙을 이용하여 구현 힙(Heap)의 특징 힙은 완전 이진 트리 자료구조의 일종이다. 여기서 완전 이진 트리란 힙의 높이를 h라 했을때 i=0 , . . ., h-1 에 대해 깊이 i인 노드가 2^i개 존재 하고 깊이 h-1 에서 내부노드(자식이 있는 노드)들은 외부노드(자식이 없는 노드)들의 왼쪽에 존재하는 트리 쉽게 말하면 루트 노드부터 시작해서 자식노드가 .. 2021. 9. 2. [암호학] Miller-rabin test를 통한 소수판별 밀러-라빈(miller-rabin) test를 통한 prime 판별 이번 포스팅에서는 강력한 소수 판별 기법 중 하나인 밀러라빈 소수판별법에 대해서 알아보겠습니다. 밀러라빈 테스트를 요약해서 말한다면, Fermat test와 Fermat factorization을 통해 소수를 판별하는 기법이라고도 할 수 있습니다. Fermat test란 ? 페르마의 소정리(Fermat Little Theorem)를 이용해서, 소수를 판별하고자 하는 것입니다. 페르마의 소정리란 다음과 같습니다 이때 이 역과정을 이용해서 만약 위의 식을 만족하는 p가 존재한다면, p는 소수라고 할 수 있을까? 라는 아이디어를 가지고 소수를 판별한 것입니다. 결과적으로, Fermat test만을 가지고 소수를 판별하는 것을 불가능합니다. F.. 2021. 6. 22. 이전 1 ··· 3 4 5 6 7 8 9 ··· 15 다음
