컴공 일기200
게시글 주소: https://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
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
분리변표 가산점 등등 고려했을때 과탐 2,3등급 <<<사탐만점 임?
-
이제 오르비가 현생 비스무리한 게 되어버렸어 아무래도..
-
1/1+sinx 부정적분이 1-sinx/1-sinx곱해서 식변형 해야한다는데...
-
수학 잘하고 싶다 12
ㄹㅇ
-
국어 잘하고싶다 0
국어 밥 먹듯이 1뜨는 사람들이 젤 부럽네요... 하 내 독해력 진짜 ㅠㅜ 어릴 때...
-
어떻게 해석해야하는지 잘 모르겠어요
-
3모 98인데 4덮 81임ㅋㅋㅋㅋ 심지어 난 현장에서 다맞은줄암
-
선착순 7분께 덕 11
담 한마디씩 해드리고 자겠습니다
-
많다 많아.. 0
한국 인구수 세계 28위 한국 치의수 세계 11위 치대로 국가 인재들 치새 만들어...
-
집에서 모고 풀 땐 차분하게 푸니까 잘 풀려서 안정 2등급 정도 나오는데(omr...
-
탈릅하지 않는 이유 => 덕코가 0이되면 탈릅
-
자러 갑니다 2
내일 시험 3개라 치타는 체력보충을
-
아직 공부 시작 안 함ㅋㅋㅋㅋ전공인데ㅋㅋㅋ이제 해야지
-
영어 통달함 16
10월까지 유기해야지
-
선착순 10분께 16
2000덕씩 댓글 고
-
. 0
퇴궁
-
갑자기 먹고싶네
-
추합 너무 많이 받아줘서 엄청나게 뜯기는 기분인데...
-
자러 갑니다 1
오늘은 좀 일찍 잘거임 내일이 할일이 많음
-
버럭코
-
선착순 5명 질문해드림 20
-
생명 유전 비유전 같이 나가도 되나요?아님 비유전 마스터하고 유전 해야하나욤
-
선착순 5분께 15
저의 사랑을 듬뿍 드리도록 하겠습니다
-
기하도 많이 쓰나여?..
-
나두 선착 3명 24
5000덬!
-
몇 달 전에 자퇴해서 내년 4월 검고 볼 예정인데 검고 전에2주만 해도 괜찮을까요?...
-
참 힘이 많이 되는 좌우명
-
확통으로 유도했다 사탐인데 왜 기하를 해
-
2024년 4월 3주차 韓日美全 음악 차트 TOP10+α (+4월 2주차 주간VOCAL Character 랭킹) 3
2024년 4월 2주차 차트: https://orbi.kr/00067885886...
-
그림 ㅇㅈ 4
본인이 고딩때 그린걸로 추정
-
왜 그렇게 생각하는거에요??
-
멋모르고자퇴해서인생말아먹는사람!!!
-
https://youtu.be/L-IZmSj3zqc?si=fIX7Af
-
셤만 아니였어도 2
글 싸는 머신(아님)이였을거시다..
-
질러 VS 말어
-
리젠이없어..
-
성공! 근데 하루죙일함 적분이 젤 어려워요
-
수학 기출 기간 0
이미지쌤 공통과목 기출 다 풀엇는데 양이 너무 적은거같아서 김기현쌤 기출...
-
고1 끝나기 전까지 평가원 기준 국어 영어 고정 1등급 만들어 놓으면 정시로 돌려도...
-
고의적인 부정행위가 아닌 수행평가 규칙을 제대로 확인하지 못한 제 불찰로 인해...
-
누구는 하하호호 거리면서 연애하고 손붙잡고 다니는데 누구는 헤어진 전남친 무서워서...
-
카투사 제외 육해공최전방중 가고싶은 곳과 이유적어주세요
-
소세지랑 치즈2번 추가해서
-
“개저씨들 나 죽이겠다고” 민희진, 135분 격정토로 1
“하이브가 날 배신...내부고발했더니 감사” “일잘한 죄밖에...사담 짜깁기해 날...
-
하지만 가지 않으면 수능 성적이 안 오른다
-
슈둘기 ㄷㄷ 0
분명 창가에서 비둘기 소리가 들리는데 창 밖을 보면 아무것도 없고 집 밖에서 확인해...
-
G.N. 0
-
지금 대기 넣으면 언제쯤 들어갈 수 있나요? 그리고 수업난이도는 어떤가요 작수 미적...
힙정렬... 배열에 대한 이해도가 굉장히 중요하죠. 이진 트리의 구조를 배열로 치환해야 하는 거니까요. 결국 Heap이라고 하는 구조가 링크드리스트보다는 배열로 구현하는 것이 훨씬 더 유리하기 때문이 아닐까 합니다.
그냥 bubble sort만 썼었는데 여러개 배우고나니까 확실히 가장 쉽긴해도 가장 효율적인건 아니더라구요
버블 정렬 같은 경우는, 자료 데이터 수가 급증하면 시간 복잡도가 극악적으로 늘어난다는 것이 치명적 단점으로 작용하죠. 그래서, 1차원적 그러니까 선형적 자료(배열)에서 정렬을 할 때, 만약 "성능"의 문제를 치밀히 고려해야 한다면 Quicksort나 Heapsort 같은 것들이 등장하는 것이겠구요.
자료구조라는 것이 결국은 "성능"과 "효율"을 생각했을 때 더 중요한 분야가 아닌가 합니다. 그런 관점에서 어떤 때는 알고리즘보다 자료구조의 이해가 더 적확한 사람들이 개발자로서 더 많은 능력을 함유한 것이 아닌가 할 때도 있어요. 학부따리의 생각이긴 합니다만..
맞는 것 같습니다 ㅜㅜ 결국은 수학적 사고력...