힙정렬3 [알고리즘] ep1-4+) O(n + klog(n))의 힙정렬 문제: 중복이 있을 수 있는 n개의 정수들로 이루어진 무순리스트 L을 구축 후, k번째 작은 원소를 O(n + klog(n)) 시간에 찾아 인쇄하라 프로그램 요구사항:findKthSmallest(L, n, k)중복이 있을 수 있는 n개 정수 원소들로 이루어진 리스트 L의 원소 가운데 k-번째로 작은 원소를 찾아내 반환한다.buildList(n, min, max)난수함수를 이용하여 min ~ max 사이의 중복이 있을 수 있는 정수 n개의 무작위, 무순리스트를 만들어 반환한다.리스트는 1D 배열 또는 단일연결리스트 가운데 하나를 자유롭게 선택하여 구현한다.main()buildList(10, 1, 100)을 호출하여 1과 100 사이의 정수 10개로 이루어진 리스트를 만들어 L에 저장한다.정수들 사이를 공.. 2024. 7. 10. [알고리즘] 정렬 알고리즘 선택 매뉴얼 ㅇ버블정렬 - 실무에서는 아예 사용하면 안된다"제자리 + stable" O(n^2) ㅇ선택정렬: 우선순위 큐 (무순 리스트로 구현)"제자리 + unstable" O(n^2): 느리다 - 소규모 입력에 적합 ㅇ삽입정렬: 우선순위 큐 (순서 리스트로 구현)"제자리 + stable" O(n^2): 느리다 - 소규모 입력에 적합 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ ㅇ힙정렬: 우선순위 큐 (힙으로 구현)"제자리 + unstable" O(nlog(n)): 빠르다 - 대규모 입력에 적합 ㅇ병합정렬: 분할통치"제자리 X + stable" O(nlog(n)): 빠르다 - 초대규모 입력 + stable 결과에 적합 ㅇ퀵정렬: 분할통치"제자리 + unstable".. 2024. 7. 7. [알고리즘] ep1-4) 힙정렬(heap sort) 복습하고 오자!https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep1-3-%ED%9E%99heap [알고리즘] ep1-3) 힙(heap)*완전 이진 트리(Complete Binary Tree): 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리 ㅁ힙(heap): 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 완전 이진 트claremont.tistory.com ㅇ힙정렬(heap sort): 힙을 이용하여 정렬하는 방식"제자리 + unstable" O(nlog(n)) 1. 원소들을 전부 힙에 삽입한다.2. 힙의 루트는 남은 수들 중에서 최솟값(or 최댓값)을 가지므로 루트를 출력하고 힙에.. 2024. 7. 4. 이전 1 다음
