개발 및 기술 블로그

선택 트리가 왜 필요할까?? 위 그림과 같이 정렬된 데이터 리스트 k개가 있다고 가정해 보자. 이 8개의 리스트를 전부다 합칠것인데 오름차순으로 정렬을 하여 합친다면 시간 복잡도는 k * k-1가 되는데 너무 많은 연산을 해야한다. 이러한 문제를 해결하기 위해 합병 정렬에 사용하는 특수한 트리가 있는데 그것을 선택트리 라고 한다. 선택 트리의 종류 2가지 1. 승자 트리 -승자 트리:== 부모 노드가 두 자식 노드보다 작은 값을 갖는 완전 이진 트리 -작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사 -트리의 각 노드는 두 자식 노드 값이 승자를 자신의 값으로 함 -결과적으로 루트의 값이 트리에서 가장 작은값 2.패자 트리 -패자 트리:== 각 노드가 두 자식 노드보다 더 작은 값을 갖는 완전 이진 ..

힙을 설명하려면 먼저 우선순위 큐를 알아야 한다. 우선순위 큐 큐: 먼저 들어간 데이터가 먼저 삭제되는 자료구조 (FIFO: First In First Out) 우선순위 큐: 대기 리스트에서 항상 우선순위가 높은 사람이 먼저 서비스를 받는 구조 삽입과 삭제 삽입: 기존 큐와 같이 rear에 데이터를 삽입한다. 삭제: 기준 큐와 달리 우선순위를 고려하여 우선수위가 가장 높은 데이터를 삭제한다. -삭제 명령이 실행되면 저장된 데이터 중에서 가장 우선 순위가 높은것이 삭제된다. -나머지 데이터는 어떤 순서로 저장되든 문제가 되지 않는다. 그렇다면 힢을 한번 알아보자 힢의 정의 -피라미드 모양으로 쌓아 올린 더미 -무엇인가를 쌓아놓은 더미이고 항상 가장 위에 있는것을 우선 꺼내는 구조 -부모-자식 노드사이에서 ..

1. c로 연결리스트를 구현해봄 2. unix계열 운영체제 MAC에서 C/C++ 컴파일러에 대한 공부와 디버깅하는법에 대해 공부함 3. 알고리즘 문제 풀이_codesignal싸이트

#include #include struct NODE { struct NODE *next; //다음 노드의 주소를 저장할 포인터 int data; }; void addFirst(struct NODE *target, int data) { struct NODE *newNode = malloc(sizeof(struct NODE)); newNode->next = target->next; newNode->data = data; target->next = newNode; } void removeFirst(struct NODE *target) { struct NODE *removeNode = target->next; target->next = removeNode->next; free(removeNode); } int..