미성이랑

[자료구조] inserting sort 문제 REVIEW (tistory.com) [자료구조] inserting sort 문제 REVIEW우선 구조체와 포인터를 선언해 준다.  typedef struct record{ int key; char *name; int grade;}record;typedef record *point; record 구조체의 포인터 변수를 point로 두었다.   중요한 건 insert 함수 구현이니, main 함with-mimi.tistory.com 위 포스팅에서 우리는 insert 함수를 통해 key 크기를 오름차순으로 한 sort를 수행하였다. 이번에는 sort 정렬도 하지 않은 상태에서, 곧바로 binary search를 통해 내가 원하는 index의 정보(근데 이제 오름차..

int partition(record arr[], int low, int high) { char* pivot = arr[high].name; int i = (low - 1); for (int j = low; j   우리는 pivot을 배열의 맨 끝 요소로 둘 것이다. 그리고 pivot보다 큰 값은 pivot의 오른편에, pivot보다 작은 값은 pivot의 왼편에 배치해야 한다. 그래서 i=low-1이라는 변수를 두고, pivot보다 작은 값이 나올 때마다 i를 점진적으로 ++시키며 맨 앞자리로 옮겨 주었다.  마지막에는 pivot 값도 알맞은 곳(i+1번째)에 배치해 준 후, 해당 index를 반환값으로 돌려준다. void quickSort(record arr[], int low, i..

우선 구조체와 포인터를 선언해 준다.  typedef struct record{ int key; char *name; int grade;}record;typedef record *point; record 구조체의 포인터 변수를 point로 두었다.   중요한 건 insert 함수 구현이니, main 함수는 먼저 바로 살펴보겠다. int main(){ int n; FILE *f=fopen("in.txt","r"); point arr[10]; fscanf(f,"%d",&n); for(int i=0;iname=(char *)malloc(sizeof(char)*6); } int x=0; int y=0; char name[6]; for(int ..

안녕하세요 ! 오늘은 BST에서 노드를 삭제하는 delete함수만 간단히 작성해보도록 하겠습니다.  typedef struct TreeNode { int key; struct TreeNode *left, *right;} TreeNode;  위 코드는 우리가 지금부터 사용할 노드 하나를 의미하는 구조체입니다.     우리는 노드를 삭제할 때, 생각보다 많은 경우를 고려해야 합니다. 해당 노드가1. 리프 노드일 경우2. 자식이 1개인 노드일 경우3. 자식이 2개인 노드일 경우 지금부터 하나하나 차례대로 따져봅시다.  1. 삭제할 노드가 리프 노드일 경우( root -> left == NULL && root -> right == NULL ): 이 경우는 크게 걱정할 것이 없습니다. 본인 노드만 깔끔..

본격적인 문제 review에 앞서,  BST(binary search tree)와 inorder traversal(중위 순회) 이 무엇인지 함께 알아보자.  BST (binary search tree) = 이진 탐색 트리 : 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴. * BST가 가능하려면, 왼쪽 자식의 노드보다 오른쪽 자식의 노드가 항상 크거나 같아야 한다는 전제조건이 있다.   BST INSERT: 1. 삽입을 하기 전, 검색을 수행한다.   2. 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.   INORDER TR..

더 간단한 풀이 보러가기[자료구조] 문자열 radix sort algorithm 문제풀이 2 (tistory.com) [자료구조] 문자열 radix sort algorithm 문제풀이 2main 함수 int main(){ char words[MAX_WORDS][MAX_COUNT]; FILE *file = fopen("in.txt", "r"); if (file == NULL) { fprintf(stderr, "파일을 열 수 없습니다.\n"); return 1; } char ch[MAX_COUNT]; int n = 0; while (fscanf(file, "%s", ch) != EOF && n = 0with-mimi.tistory.com    이번 문제는, radix sort algorithm을 이용하여 문..

https://mimieee122.github.io/calculator-study/ https://mimieee122.github.io/calculator-study/mimieee122.github.io  1. 기본 계산기2. 조합 계산기3. 글자 수 세기4. 퍼센트 계산5. 날짜 계산  이렇게  5가지 종류의 계산기를 구현해보았고, 사이트 상단에는 간단히 문장 번역 기능을 추가해 보았습니다.

기수 정렬 (radix sort): 실제 숫자들 간의 비교를 통해 정렬을 하는 것이 아니라, 버킷(bucket) 을 이용해 정렬하는 방법.   각 자릿수 별로 0~9까지의 버킷이 있고, 이 버킷에 순서에 맞게 숫자를 넣어가며 분류한다고 생각하면 된다. 우리는 LSD를 사용할 것이므로, 일의 자리 수부터 시작한다.    위 그림을 더 이해하기 쉽게 적어보자면, 1. sort digit 1 : [411],  [954,354] ,  [009]2. sort digit 2 : [009], [411], [954,354]3. sort digit 3 : [009], [354], [411]. [954] 가 되겠다. 가장 낮은 1번째 자리부터 가장 높은 3번째 자리 순으로 정렬하였다. (LSD)   이제 Radix sor..

문제 풀이에 앞서,  힙(heap)이란 무엇인지, 그리고 힙의 종류는 어떤 것들이 있는지부터 먼저 짚어보도록 하자.   힙이란, 완전 이진 트리의 일종으로, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진 트리를 말한다. 여러 개의 값들중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.  힙의 종류 최대 힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같은 완전 이진 트리 최소 힙(min heap): 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리         우리의 문제에서는 현재 내림차순으로 정수 집합을 정렬할 것을 요구하고 있으므로, 위 두 힙 종류 중 최대 힙(max heap)을 이용해 볼 것이다.   문제..

완전 이진 트리(complete binary tree)의 특징    0. 완전 이진 트리에서는 다음과 같은 관계가 성립:n0 = n2 + 1여기서,n0 : 리프 노드(leaf node)의 개수n2 : 2개의 자식 노드를 가진 내부 노드(internal node)의 개수 간단한 증명 : n= n0 + n2n-1 = 2(n2)이 두 식을 정리하면 n0 = n2 + 1   1. 모든 레벨의 노드가 꽉 차 있다. - 마지막 레벨을 제외하면, 모든 레벨의 노드가 채워져 있다.( 각 내부 노드는 무조건 자식 노드를 2개 가져야 한다. )     2. 완전 이진 트리의 마지막 레벨은 이전 레벨들과 달리 불완전할 수 있으나, 이 때 마지막 레벨의 노드들은 왼쪽에서 오른쪽 방향으로 순서대로 채워져야 한다.( 마지막 레벨..