[알고리즘] ep1-4+) O(n + klog(n))의 힙정렬

문제: 중복이 있을 수 있는 n개의 정수들로 이루어진 무순리스트 L을 구축 후, k번째 작은 원소를 O(n + klog(n)) 시간에 찾아 인쇄하라

 

 

프로그램 요구사항:

1. findKthSmallest(L, n, k)
   • 중복이 있을 수 있는 n개 정수 원소들로 이루어진 리스트 L의 원소 가운데 k-번째로 작은 원소를 찾아내 반환한다.
2. buildList(n, min, max)
   • 난수함수를 이용하여 min ~ max 사이의 중복이 있을 수 있는 정수 n개의 무작위, 무순리스트를 만들어 반환한다.
   • 리스트는 1D 배열 또는 단일연결리스트 가운데 하나를 자유롭게 선택하여 구현한다.
3. main()
   • buildList(10, 1, 100)을 호출하여 1과 100 사이의 정수 10개로 이루어진 리스트를 만들어 L에 저장한다.
     • 정수들 사이를 공백으로 구분하여, 리스트 L의 정수들을 한 라인에 출력한다.
     • k = 1, 2, 3을 차례로 인자로 사용하여 findKthSmallest(L, 10, k) 함수를 총 3회 호출한 결과를 모아 1개의 라인에 순서대로 출력한다.
     • buildList(100000, 1, 1000000)을 호출하여 1 ~ 100만 사이의 정수 10만개로 이루어진 리스트를 만들어 L에 저장한다.
     • 이번엔 생성된 리스트 L을 출력하지 않는다.
     • k = 1, 100, 99900, 99999를 차례로 인자로 사용하여 findKthSmallest(L, 100000, k) 함수를 총 4회 호출한 결과를 실행시간과 함께 4개의 라인으로 출력한다.
4. 위 함수들은 필히 작성해야 하며, 이외에도 writeList 등 필요하다고 판단되는 추가적인 함수를 작성하라.

 

 

힌트:

1. 원문제의 실행시간 조건 O(n + k log n)은 요구사항이기도 하지만 힌트도 된다는 점을 잘 생각해서 작성할 것.
2. 알고리즘:
   • Alg main()
     1. L ← buildList(10, 1, 100) {build a list of size 10}
     2. writeList(L) {write 10 elements in 1 line}
     3. for k ← 1 to 3 {mini test runs}
        • output[k] ← findKthSmallest(L, 10, k)
     4. write(output[1], output[2], output[3]) {write 3 elements in 1 line}
     5. L ← buildList(100000, 1, 1000000) {build a list of size 100,000}
     6. karray ← {1, 100, 99900, 99999} {an array of k values}
     7. for k ← 0 to 3 {main test runs}
        • StartClock()
        • e ← findKthSmallest(L, 100000, karray[k])
        • StopClock()
        • t ← CPUtime()
        • write(e, t) {write e and t in 1 line}
     8. return

 

주의:

1)  프로그램 전체를 통해 단 한 개의 findKthSmallest 함수만 작성하고 호출해야 함.

2)  findKthSmallest(L, n, k)의 인자 L은 항상 최근의 buildList에 의해 구축된 초기 리스트 L이어야 함.

3)  1 ≤ k ≤ n 이다. 즉, L의 중복 키들에 대해서도 k 순위가 누적된다. 예를 들어서 L = {1, 1, 3, 5, 5, 5, 14}인 경우, findKthSmallest(L, 7, 2)는 1을, findKthSmallest(L, 7, 6)은 5를, findKthSmallest(L, 7, 7)은 14를 각각 반환해야 한다.

4)  요구한 실행시간 O(n + k log n)에 미달하는 알고리즘은 요구 미충족으로 30% 감점. 이 실행시간은 k가 n에 근접한 경우를 제외하고는 O(n log n)보다 일반적으로 빠르다. 좀 더 쉽게 말해서, 작은 k 값에 대한 수행시간이 큰 k 값에 대한 수행시간보다 "상당히" 작지 않으면 요구 미충족 판정을 받게 됨.

5)  main()을 실행하면 총 6개 라인을 인쇄해야 함.

 

 

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

해결방안: 최소힙(min-heap)
리스트의 모든 요소를 heap에 삽입하는 데 O(n) 시간, k번째로 작은 요소를 찾는 데 O(klog(n)) 시간이 걸린다

 

 

(전체코드) - Windows에서만 실행 가능

// 프로그램 요구사항: k번째 작은 원소를 O(n + klog(n)) 시간에 찾아 인쇄
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#pragma warning (disable:4996)

typedef struct NODE {
    int e;
    struct NODE* next;
} NODE;

NODE* newNode(int e);
void writeList(NODE* head);
void freeList(NODE* head);

NODE* buildList(int n, int min, int max);
int findKthSmallest(NODE* head, int n, int k);
void Heapify(int* heap, int heapSize, int i);

int main() {
    srand(time(NULL));
    LARGE_INTEGER ticksPerSec;
    LARGE_INTEGER start, end, diff;
    int output[4]; // k번째 작은 값을 저장할 배열
    NODE* L = buildList(10, 1, 100);
    writeList(L);
    for (int k = 1; k < 4; k++) {
        output[k] = findKthSmallest(L, 10, k); // k번째 작은 값 찾기
    }
    printf("%d %d %d\n", output[1], output[2], output[3]);

    freeList(L); // 재사용 전에 free 해주기

    L = buildList(100000, 1, 1000000);
    int karray[4] = {1, 100, 99900, 99999}; // k값 배열
    int e;
    for (int k = 0; k < 4; k++) {
        QueryPerformanceFrequency(&ticksPerSec); // 시간 측정 빈도 설정
        QueryPerformanceCounter(&start);
        e = findKthSmallest(L, 100000, karray[k]);
        QueryPerformanceCounter(&end);
        diff.QuadPart = end.QuadPart - start.QuadPart;
        printf("%d %.9lf\n", e, ((double)diff.QuadPart / (double)ticksPerSec.QuadPart));
    }

    freeList(L);
    return 0;
}

NODE* newNode(int e) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
    newNode->e = e;
    newNode->next = NULL;
    return newNode;
}

void writeList(NODE* head) {
    while (head != NULL) {
        printf("%d ", head->e);
        head = head->next;
    }
    printf("\n");
}

void freeList(NODE* head) {
    while (head != NULL) {
        NODE* cur = head;
        head = head->next;
        free(cur);
    }
}

NODE* buildList(int n, int min, int max) {
    // 첫 노드 생성
    NODE* L = newNode(rand() % (max - min + 1) + min);
    NODE* cur = L;
    // 나머지 노드 생성
    for (int i = 0; i < n - 1; i++) {
        cur->next = newNode(rand() % (max - min + 1) + min);
        cur = cur->next;
    }
    return L;
}

// k번째 작은 원소를 찾는 함수
int findKthSmallest(NODE* head, int n, int k) {
    int heapSize = 0;
    int* heap = (int*)malloc((n + 1) * sizeof(int)); // 힙 배열 생성 (인덱스 0은 비워놓는다)
    if (heap == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }

    NODE* cur = head;
    while (cur != NULL) { // 리스트의 원소를 힙 배열에 복사
        heap[++heapSize] = cur->e; // 인덱스 1부터 시작
        cur = cur->next;
    }

    // 힙을 생성하고 k번째 작은 원소를 찾기 위해 정렬
    for (int i = heapSize / 2; i >= 1; i--) {
        Heapify(heap, heapSize, i); // 힙 생성
    }

    for (int i = 0; i < k - 1; i++) {
        heap[1] = heap[heapSize--]; // 루트를 힙의 마지막 원소로 대체
        Heapify(heap, heapSize, 1); // 힙 재정렬
    }

    int kthSmallest = heap[1]; // k번째 작은 원소
    free(heap);
    return kthSmallest;
}

// 힙을 재정렬하는 함수
void Heapify(int* heap, int heapSize, int idx) {
    int smallestIdx = idx; // 가장 작은 원소의 인덱스
    int leftChildIdx = 2 * idx; // 왼쪽 자식 노드의 인덱스
    int rightChildIdx = 2 * idx + 1; // 오른쪽 자식 노드의 인덱스

    if (leftChildIdx <= heapSize && heap[leftChildIdx] < heap[smallestIdx]) {
        smallestIdx = leftChildIdx; // 왼쪽 자식이 더 작으면 인덱스 갱신
    }

    if (rightChildIdx <= heapSize && heap[rightChildIdx] < heap[smallestIdx]) {
        smallestIdx = rightChildIdx; // 오른쪽 자식이 더 작으면 인덱스 갱신
    }

    if (smallestIdx != idx) {
        int temp = heap[idx];
        heap[idx] = heap[smallestIdx];
        heap[smallestIdx] = temp;
        Heapify(heap, heapSize, smallestIdx); // 재귀 호출로 힙 재정렬
    }
}

 

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님)