컴공 일기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를 선물하세요.
-
고생대때는 산소 농도가 높아서 8 3
몸길이 9cm짜리 바퀴벌레랑 날개폭 70cm 잠자리가 날라다녔다고함 ㅈㄴ무서움
-
허수일기(32) 12 2
내일도 화이팅!
-
작년 수능 전날 0 0
재수생분들 보면서 내가 막 떨리고 그랬는데 올해 나네..?
-
내가 인증하면 안되는 이유 6 0
오르비 차단 당한 순위 1등됨
-
얼리버드 고2께 내년 수능까지 55고 환급형임 근데 그 10월인가 12월달에...
-
오늘의공부7일차 6 1
게도둑할머니
-
뭔가 완전히 털리면 기분 좋음 2 3
애매하게 같은 유형을 실수를 하면 ㅈㄴ 빡치는데 완전하게 내 논리가 잘못됨을...
-
ㅇㅈ 11 1
종강때 찍은사진 ㅇㅈ 절대 안돌아가고싶음
-
좆됏다시발!!!!!!!!
-
국어 과외 0 0
받아보고 싶다... 쿠팡 하루뛰고 단기과외 같은거 받아볼까
-
진짜 존나재밌었음 ㅋㅋ 그 대가리 뾰족한새기가 실시간 글도쓰고
-
앉아 있었는데 위에서 뭐가 톡-,,, 벌레겠거니 무심하게 털었는데,,,, 니가 왜...
-
초등학생때 3 1
50미터 13초 난 전력질주했다
-
ㅇㅈ 12 4
ㅋ
-
아이큐 검사 0 0
결과보고 지금까지 공부한게 다 거짓이 되고 물거품이 된 느낌. 생각보다 매우낮게나옴..
-
으어어 얼마만에 만든 수면패턴을
-
이게 아이린인지 모르는 사람이 있다고 12 3
ㅈㄴ예쁘다 근데
-
ㅇㅈ 7 1
설효림씨랑 약속을 해버려서.. 폰 바꿔서 옛날 사진이 없어가지고 지금 찍어서...
-
반수생이고 작수 84졈입니다 현재 스블 수1 수2 미적 다 들었어요 범 이새기거...
-
방금찍음 8 1
듀듀
-
나 사시인가 2 0
왜 눈이 약간 안맞지
-
프사추천해줄게 10 1
잠이드릅게 안오네 원하는 느낌같은거 말해주면 반영해줄게요옹
-
국어수학 좋은 교육청 1 0
모고잇나요 알려주시면 감사하겟습니다
-
님들 최애곡 뭐임 16 1
그리고 그 곡이 최애곡인 이유는 머임
-
번아웃 개씨게옴 0 0
이번주 한 3일 공부한듯 정신차려야하는데 어카지..
-
수학 어느정도 하는데 등급 잘 안 뜨는 사람 찾아요 0 1
제가 수학 과외슨생인데 고민이 하나 있어요 지금껏 70명 넘게 가르쳤는데 감이...
-
공부인증 2일차 3 2
아무것도하기싫다ㅏㅏㅏㅏㅏ ㄹㅈㄷ 작심1일
-
내가 보기엔 잇올이 0 0
시대 기숙 이런데보다 행정 못함
-
ㅇㅈ 12 1
-
저는 인증 한번 한 후 1 0
무료과외 제안서 정리하는데만 한달이 걸렸더랬죠
-
꿈을 품고 익사해라 0 0
끄ㅓ걱ㄱ
-
인증 해줘 ㅜㅜ 2 1
올만에 ㅇㅈ메타ㅏ
-
잘자시오 옯붕이들 4 0
-
내 ㅇㅈ 보는법 7 1
옯스타 친친에 들어가기
-
넌 꼭 설의가라 3 0
못생겨서 그래야겠다
-
수학 공부 훈수 부탁드립니다 0 1
지금 N티켓 시즌1 풀고 있습니다 수2, 확통은 할만해서 금방 끝냈는데 수1은 너무...
-
공부기록(102) 18 3
-
아니 아이린 사진 올렸는데 8 3
와 아이린 닮음은 뭐꼬 ㅋㅋㅋㅋ 갸웃김
-
방학첫날 1 0
모고 풀고 성찰하는 시간 좀 가져야겠음 요즘 메타인지가 잘 안되는듯 ㅇㅇ
-
이제 네 달 남았어 13 1
다들 반수하자
-
”여장“을 의미한다고 규정하겠습니다 앞으로 ㅇㅈ이라고 제목을 작성하고 여장한 사진이...
-
아니 에피들은 2 2
왜 다 존잘남임 ㅅㅂ 나가라 ㅅㅂㅅㅂ5ㅂㅅㅂㅅㅅㅂ
-
내신 마무리하고 뒤늦게 수능준비합니다. 6모 12221 7모 12211 입니다....
-
ㅇㅈ 14 3
어 누나야~
-
ㅇㅈ 1 2
은 없지만 6모 대회 결과는 곧 나옴 덕코 지급은 내일이나 모레 중으로..
-
.
-
하루살이특 8 2
하루 넘게 살음 하..어디서 자꾸 리스폰되는거야 오늘만 10마리 잡은거같은데
-
세지질문 3 1
‘서양’이 도대체 어디임 사설 거긴한데 바빌로니아 점토판 지도가 서양에서 제작되었다...
-
페드로 포로의 스페인 우승기원 1 2
포로 우승하고 월드컵에서 돌아와서도 잘해줬으면
-
하...
저는 얼마전에 heap sort 처음 짜봤는데힙정렬... 배열에 대한 이해도가 굉장히 중요하죠. 이진 트리의 구조를 배열로 치환해야 하는 거니까요. 결국 Heap이라고 하는 구조가 링크드리스트보다는 배열로 구현하는 것이 훨씬 더 유리하기 때문이 아닐까 합니다.
그냥 bubble sort만 썼었는데 여러개 배우고나니까 확실히 가장 쉽긴해도 가장 효율적인건 아니더라구요
버블 정렬 같은 경우는, 자료 데이터 수가 급증하면 시간 복잡도가 극악적으로 늘어난다는 것이 치명적 단점으로 작용하죠. 그래서, 1차원적 그러니까 선형적 자료(배열)에서 정렬을 할 때, 만약 "성능"의 문제를 치밀히 고려해야 한다면 Quicksort나 Heapsort 같은 것들이 등장하는 것이겠구요.
자료구조라는 것이 결국은 "성능"과 "효율"을 생각했을 때 더 중요한 분야가 아닌가 합니다. 그런 관점에서 어떤 때는 알고리즘보다 자료구조의 이해가 더 적확한 사람들이 개발자로서 더 많은 능력을 함유한 것이 아닌가 할 때도 있어요. 학부따리의 생각이긴 합니다만..
그래서 결국은 수학을 잘해야 하는듯 해요..맞는 것 같습니다 ㅜㅜ 결국은 수학적 사고력...