컴공 일기200

200번째의 글로 치닫고 있습니다. 과제하랴, 개인 공부하랴, 수업 들으랴, 대학 생활하랴, 너무 정신이 없었던 최근이었네요. 개인적으로, 몸은 많이 힘들고 지치긴 합니다만, 좋아하는 공부와 일상을 건축해나가고 있는 듯해서 뿌듯한 것도 사실입니다. 

수험생, 그 사람들 만큼은 아니겠지만 대학생으로서 숨 쉬는 나도 '젊음'이라는 관념을 놓치고 싶지 않았습니다. 그런 고상한 정신 때문이었을까. 종종, 과분하게도 주변 사람들은 나를 호되게 칭찬하면서, 어떻게 그렇게 열심히 할 수 있냐고 묻더군요. 그런데, 사실 이 의지의 발현이 가능했던 것은 내가 다른 사람들에 비해 우수한 측면(말하자면 재능)을 갖고 있었기 때문은 아닙니다.  

어떤, 대단한 수치적 목표가 있는 것은 아니거든요. 연봉 2억 어치 개발자가 되겠다고, 창업을 해서 시가 총액 몇 순위 안에 드는 리더가 되겠다고, 그런 거창한 꿈을 갖고 사는 삶의 형태가 아닙니다. 다만, 공학 공부를 하는 내내 호기심을 가지고, 주어진 예제를 푸는 것이 굉장히 재미있을 뿐입니다. 말하자면, "순수성"에 입각한 일상의 의지, 그 이상 그 이하도 아니라는 것. 

4수의 경험 끝에 내가 얻은 것 중 하나는, 우리네 인생에서 "수치"가 말해줄 수 있는 것은 생각보다 미미하다는 점입니다. 점수와 학벌에 입각한 레테르 조각들 가지고 그 사람의 수준과 배경을 판단하곤 하지만, 기실 그것은 참고 사항일 뿐, 그 자체의 존재를 논증할 수 있을 만큼 정확하지 않다는 것. 그러기에 존재의 이력서는 숫자가 아니라 그 사람의 냄새, 소리, 분위기, 감정, 어조 등 보이지 않는 영역에 있음을 잊지 말자고 늘 다짐합니다. 

수능이라는 것은, 결국 '수치'에 불과하니, 이것 하나 망친다고 해서 우리의 존재가 사그라드는 것이 아님을 인지해야 할 것입니다. 수능을 4번 망해도, 태양은 언제나 나의 부끄러운 정수리를 보다듬으며 어둠과 싸우더이다.

최소 히프(Min Heap)의 절차지향적 구현 

Heap.c 

#include "Heap.h"

Heap* HEAP_Create(int InitialSize)

{

    Heap* NewHeap = (Heap*)malloc(sizeof(Heap));

    NewHeap->Capacity = InitialSize;

    NewHeap->UsedSize = 0;

    NewHeap->Nodes = (HeapNode*)malloc(sizeof(HeapNode) * NewHeap->Capacity);

    printf("size : %d\n", sizeof(HeapNode));

    return NewHeap;

}

void HEAP_Destroy(Heap* H)

{

    free(H->Nodes);

    free(H);

}

void HEAP_Insert(Heap* H, int NewData)

{

    int CurrentPosition = H->UsedSize;

    int ParentPosition = HEAP_GetParent(CurrentPosition);

    if (H->UsedSize == H->Capacity)

    {

        H->Capacity *= 2;

        H->Nodes = (HeapNode*)realloc(H->Nodes, sizeof(HeapNode) * H->Capacity);

    }

    H->Nodes[CurrentPosition].Data = NewData;

    //부모노드가 더 크다면 바꿔야 한다.

    while (CurrentPosition > 0 && H->Nodes[CurrentPosition].Data < H->Nodes[ParentPosition].Data)

    {

        HEAP_SwapNodes(H, CurrentPosition, ParentPosition);

        CurrentPosition = ParentPosition;

        ParentPosition = HEAP_GetParent(CurrentPosition);

    }

    H->UsedSize++;

}

void HEAP_SwapNodes(Heap* H, int Index1, int Index2)

{

    int CopySize = sizeof(HeapNode);

    HeapNode* Temp = (HeapNode*)malloc(CopySize);

    memcpy(Temp, &H->Nodes[Index1], CopySize);

    memcpy(&H->Nodes[Index1], &H->Nodes[Index2], CopySize);

    memcpy(&H->Nodes[Index2], Temp, CopySize);

    free(Temp);

}

//최솟값을 삭제하는 함수

void HEAP_DeleteMin(Heap* H, HeapNode* Root)

{

    int ParentPosition = 0;

    int LeftPosition = 0;

    int RightPosition = 0;

    //최솟값 노드가 루트 노드라서, 이 쪽을 일단 초기화하고, 최우측 노드와 교환 준비

    memcpy(Root, &H->Nodes[0], sizeof(HeapNode));

    memset(&H->Nodes[0], 0, sizeof(HeapNode));

    H->UsedSize--;

    //최우측 노드와 교환

    HEAP_SwapNodes(H, 0, H->UsedSize);

    LeftPosition = HEAP_GetLeftChild(0);

    RightPosition = LeftPosition + 1;

    while (1)

    {

        int SelectedChild = 0;

        if (LeftPosition >= H->UsedSize)

            break;

        //마지막 끝 계산인 경우인데, 이 경우 LeftPosition이 마지막 노드라서 Selected가 자연스레 선택될 수밖에 없다.

        if (RightPosition >= H->UsedSize)

        {

            SelectedChild = LeftPosition;

        }

        else

        {

            if (H->Nodes[LeftPosition].Data > H->Nodes[ParentPosition].Data)

                SelectedChild = RightPosition;

            else

                SelectedChild = LeftPosition;

        }

        if (H->Nodes[SelectedChild].Data < H->Nodes[ParentPosition].Data)

        {

            HEAP_SwapNodes(H, ParentPosition, SelectedChild);

            ParentPosition = SelectedChild;

        }

        //타겟 인덱스의 데이터가 그 부모의 데이터보다 크다면 정상적인 배치가 완료되었다고 볼 수 있다. 그러므로 break.

        else

            break;

        LeftPosition = HEAP_GetLeftChild(ParentPosition);

        RightPosition = LeftPosition + 1;

    }

    if (H->UsedSize < (H->Capacity / 2))

    {

        H->Capacity /= 2;

        H->Nodes = (HeapNode*)realloc(H->Nodes, sizeof(HeapNode) * H->Capacity);

    }

}

int HEAP_GetParent(int Index)

{

    return (int)((Index - 1) / 2);

}

int HEAP_GetLeftChild(int Index)

{

    return (2 * Index + 1);

}

void HEAP_PrintNodes(Heap* H)

{

    int i = 0;

    for (i = 0; i < H->UsedSize; i++)

    {

        printf("%d ", H->Nodes[i].Data);

    }

    printf("\n");

}

main.c 

//최소 히프의 테스트를 위한 코드 

#include "Heap.h"

int main(void)

{

    Heap* H = HEAP_Create(3);

    HeapNode MinNode;

    HEAP_Insert(H, 12);

    HEAP_Insert(H, 87);

    HEAP_Insert(H, 111);

    HEAP_Insert(H, 34);

    HEAP_Insert(H, 16);

    HEAP_Insert(H, 75);

    HEAP_PrintNodes(H);

    HEAP_DeleteMin(H, &MinNode);

    HEAP_PrintNodes(H);

    HEAP_DeleteMin(H, &MinNode);

    HEAP_PrintNodes(H);

    HEAP_DeleteMin(H, &MinNode);

    HEAP_PrintNodes(H);

    HEAP_DeleteMin(H, &MinNode);

    HEAP_PrintNodes(H);

    HEAP_DeleteMin(H, &MinNode);

    HEAP_PrintNodes(H);

    HEAP_DeleteMin(H, &MinNode);

    HEAP_PrintNodes(H);

}

테스트 실행결과 :  

size : 4

12 16 75 87 34 111

16 87 75 111 34

34 87 75 111

87 111 75

75 111

111