본문 바로가기

알고리즘(C언어)40

(4)실습4주차_힙과 힙정렬(2)_1_문제1번,문제2번 ##노트 정리 PDF ##문제 풀기 전 알아야 할 개념(요약) :1_ 상향식 힙 생성 :과정 :Heap에 한꺼번에 여러 원소를 저장한다.맨 마지막 노드의 부모노드부터 역순으로 루트노드까지 DownHeap과정을 거친다.2_ 힙트리 + 제자리힙정렬 (중복된 키들이 들어간 힙트리도 적용된다.):- 언제 쓰이는 지의 상황 : 상향식 힙트리 생성 과정을 거친 힙트리일 때,- 과정 :루트노드와 마지막 노드 Swap맨마지막 노드를 삭제루트노드를 대상으로 DownHeap과정을 거친다.1~3번 과정을 Heap의 Size가 1이 될때 까지 반복- 과정을 거친 후 결과 :최대 힙 트리 → 오름차순으로 정렬된 Heap 배열최소 힙 트리 → 내림차순으로 정렬된 Heap 배열##코드 :123456789101112131415161.. 2024. 9. 5.
(4)실습3주차_힙과 힙정렬(1)_2_문제2번 ※문제에 대한 PDF는 아래의 링크에 있습니다.https://kojammin.tistory.com/87 (3)실습3주차_힙과 힙정렬(1)_1_문제1번##기억해야할 내용 :UpHeap()메소드- 이론 :  맨 마지막 노드에 값을 삽입 후, 최대 힙 규칙에 맞춰, 적절한 위치로 부모노드로 올리는 메소드- 매개변수 : Heap 구조체 포인터, 해당 조정할 노드의 인kojammin.tistory.com #이 문제를 풀기 위해 알아야 할 개념 :1_ 상향식 힙 생성 :1_1) 정의 : 우선 키의 개수와 키들을 한꺼번에 입력한 뒤, 리프 노드의 이전 레벨의 모든 노드를 DownHeap()과정을 거쳐 힙트리를 구성하는 방식이다.1_2) 자세한 과정 :ex_ 키의 개수 : 6 , 키의 구성 : 24 17 33 50 6.. 2024. 9. 2.
(3)실습3주차_힙과 힙정렬(1)_1_문제1번 ##기억해야할 내용 :UpHeap()메소드- 이론 :  맨 마지막 노드에 값을 삽입 후, 최대 힙 규칙에 맞춰, 적절한 위치로 부모노드로 올리는 메소드- 매개변수 : Heap 구조체 포인터, 해당 조정할 노드의 인덱스(i)- 코드상 순서 :1_ Parent(i)의 노드와 i의 노드 SWAP2_ i노드를 Parent(i)노드로 업데이트3_ while로 i가 루트 도달 전 && 자식노드의 data > 부모노드의 data라면, 반복  DownHeap()메소드- 이론 :  해당 노드 값에서, 최대 힙 규칙에 맞춰, 적절한 위치로 자식노드로 내리는 메소드- 매개변수 : Heap 구조체 포인터, 해당 조정할 노드의 인덱스(i)- 코드상 순서 :1_ △구조로, 부모노드를 (Best==i), 왼쪽자식(L), 오른쪽 자.. 2024. 9. 1.
(2)실습2주차_우선순위 큐(선택 & 삽입 정렬)_2_문제3의 코드와 노트 [문제3]##질문들에 대한 필요한 자료 :### **질문 A: 정렬되지 않은 데이터가 주어지는 경우** 1. **a) 동일한 n으로 여러 번 실행하여, 어느 정렬이 더 빠른지 비교해보자:**    - 정렬되지 않은 데이터에 대해 선택 정렬과 삽입 정렬 중 어느 것이 더 빠른지 비교하는 것이 목표입니다.    - 선택 정렬은 데이터의 초기 상태와 상관없이 항상 \(O(n^2)\)의 시간 복잡도를 가지며, 삽입 정렬은 부분적으로 정렬된 데이터에 대해 더 나은 성능을 보일 수 있습니다. 하지만, 두 알고리즘 모두 최악의 경우에는 \(O(n^2)\) 시간이 걸리기 때문에 성능 차이가 크지 않을 수 있습니다.    - 동일한 크기의 n에 대해 여러 번 프로그램을 실행해보고, 어느 알고리즘이 더 빠른지 실행 시간을.. 2024. 9. 1.

티스토리툴바