내 소식

태그

내 태그

입시

학습

생활

클럽

직업·취업

Epioptimus

Centurion

✨컴공주✨ [1052682] · MS 2021 (수정됨) · 쪽지

2022-11-06 01:56:44
조회수 3,090
0

컴공 일기200

게시글 주소: https://dev.orbi.kr/00059195297

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

팔로우 157

0 XDK (+0)

유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

✨컴공주✨ [1052682]

쪽지 보내기

최근 게시글 · 더보기
10 0 03/13 14:48 컴공 무물
14 0 02/18 12:41 컴공 무물
15 1 25/12/16 14:09 컴공 일기279
1 0 25/05/31 00:19 컴공 일기278
6 0 25/04/19 02:22 컴공 일기277

알림
스크랩
신고

홀붕 · 1153156 · 22/11/06 02:00 · MS 2022

저는 얼마전에 heap sort 처음 짜봤는데

좋아요 0 답글 달기 신고
✨컴공주✨ · 1052682 · 22/11/06 02:01 · MS 2021 (수정됨)

힙정렬... 배열에 대한 이해도가 굉장히 중요하죠. 이진 트리의 구조를 배열로 치환해야 하는 거니까요. 결국 Heap이라고 하는 구조가 링크드리스트보다는 배열로 구현하는 것이 훨씬 더 유리하기 때문이 아닐까 합니다.

좋아요 0 답글 달기 신고
홀붕 · 1153156 · 22/11/06 02:03 · MS 2022

그냥 bubble sort만 썼었는데 여러개 배우고나니까 확실히 가장 쉽긴해도 가장 효율적인건 아니더라구요

좋아요 0 답글 달기 신고
✨컴공주✨ · 1052682 · 22/11/06 02:06 · MS 2021 (수정됨)

버블 정렬 같은 경우는, 자료 데이터 수가 급증하면 시간 복잡도가 극악적으로 늘어난다는 것이 치명적 단점으로 작용하죠. 그래서, 1차원적 그러니까 선형적 자료(배열)에서 정렬을 할 때, 만약 "성능"의 문제를 치밀히 고려해야 한다면 Quicksort나 Heapsort 같은 것들이 등장하는 것이겠구요.

자료구조라는 것이 결국은 "성능"과 "효율"을 생각했을 때 더 중요한 분야가 아닌가 합니다. 그런 관점에서 어떤 때는 알고리즘보다 자료구조의 이해가 더 적확한 사람들이 개발자로서 더 많은 능력을 함유한 것이 아닌가 할 때도 있어요. 학부따리의 생각이긴 합니다만..

좋아요 0 답글 달기 신고
홀붕 · 1153156 · 22/11/06 02:08 · MS 2022

그래서 결국은 수학을 잘해야 하는듯 해요..

좋아요 1 답글 달기 신고
✨컴공주✨ · 1052682 · 22/11/06 02:08 · MS 2021

맞는 것 같습니다 ㅜㅜ 결국은 수학적 사고력...

좋아요 0 답글 달기 신고