mintuchel mintuchel

위 GIF에서 볼 수 있듯이 최소값(Minimum) 을 찾아 swap 해줌으로써 정렬을 완성해나가는 식이다. 내 기준 선택정렬이 가장 떠올리기 어려운 정렬이다. 이름만으로는 감이 안온다 모든 정렬 알고리즘에서 "선택" 은 항상 존재한다. 따라서 "선택"이라는 단어가 정렬 알고리즘 상에서 매우 보편적인 단어인데 이걸 정렬방법 이름으로 써놨다. 그냥 답이 없다 void SelectSort(int arr[], int n) { int idx; for (int i = 0; i arr[k]) { idx = k; } } int temp = arr[idx]; arr[idx] = arr[i]; a..

void BubbleSort(int arr[], int n) { for (int i = 0; i arr[k + 1]) { int temp = arr[k + 1]; arr[k + 1] = arr[k]; arr[k] = temp; } } } } 대표적인 O(n^2) 정렬이다. [ 시간복잡도 ] [ 점화식 ] N개의 버블정렬은 N-1개의 버블정렬 알고리즘시간에 한 개에 대한 비교연산 N-1번만 더하면 된다. 따라서 위와 같이 나온다. [ 노가다 생각해보기 ] 일단 최악의 경우를 생각해보자. 비교연산이 이중 중첩 반복문 안에 즉, for for 문 안에 있다. 그리고 비교연산에 따른 break문이나 ..

[ 배열 매개변수 ] class A { public: char name[100]; A(char temp[]) { // 여기서 temp는 포인터이므로 temp변수값 자체를 출력해본다 printf("A::temp: 0x%p\n",temp); strcpy(name, temp); } }; C 에서 함수에 배열 매개변수가 있다면 어떻게 됐었는가? 예를 들어 이런 함수라면 void ArrFunc( int arr[] ) { // code } 여기서 arr는 무늬만 배열이고, 실제로는 포인터 변수였다. 따라서 아래와 같은 함수라고 봐도 무방했다! void ArrFunc( int* arr ) { // code } C++ 에서도 마찬가지다! 생성자도 일종의 함수이니 위 클래스의 생성자에서 arr는 포인터이다! 장점 : 코..

수식트리를 구현하기 위해서는 배열에 있는 데이터를 뽑아내서 이진트리로 표현해야한다. 이때 활용할 것이 앞서 배운 STACK이다. 활용할 스택은 BTreeNode를 저장할 스택이다. 즉 우리는 배열에서 뽑아낸 데이터를(수 / 연산자 구별 없이) 모두 BTreeNode 로 만든다음 스택에 저장할 것이다. 이 부분이 가장 중요하다고 생각한다. 그냥 숫자 연산자로 스택에 저장했다가 PUSH POP할때마다 BTreeNode로 바꿔서 넣는 것보다 처음부터 BTreeNode로 보고 진행하는 것이 훨씬 깔끔하고 진행과정이 직관적이다. 위의 쟁반이 바로 BTreeNode 스택이다. 여기다 모든 데이터를 BTreeNode로 만들어 PUSH 연산을 수행한다. 만약 데이터가 연산자면 POP을 통해 STACK에서 두 개의 BT..

이진 트리를 참조하는 함수를 구현할때는 이진 트리의 성질인 "재귀"를 이용하는게 중요함 트리는 위와같은 서브트리가 반복적으로 나오는 구조이기 때문에 "재귀"를 활용할 수 있다. 그럼 단말노드는 어떻게 처리할까 저 2,3은 밑에 아무것도 없지 않은가? 그럼 노드 1개로 봐야하는거 아닌가? 재귀에서 가장 중요하고 반드시 필요한 탈출조건은 어떤 조건으로 구성해야할까 트리의 단말노드는 양쪽에 NULL값의 노드가 있다고 생각하면 된다. 따라서 만약 재귀로 쭉 내려가다 양쪽에서 NULL이 나온다? 이러면 단말노드임을 확신하고 다시 위로 쭉쭉 올라가면 되는거임 즉, 단말노드까지 맨 위 구조로 되어있다고 생각하고 코드를 작성해도 되는 것이다 단말노드까지 재귀를 활용할 수 있게 된다 [이진 트리 기본 ADT 구현] ty..

node를 사용해서 linked-queue라고도 불림 리스트 기반으로도 큐를 구현할 수 있다. 오히려 구현하는데 신경쓸게 별로 없다. 앞선 원형큐보다 간단하다. enqueue dequeue 할때 malloc free 순서 좀만 신경써주면된다. 하지만 노드를 사용하기에 그냥 배열을 사용하는 원형큐보다는 메모리를 더 쓴다 typedef int Data; typedef struct node { Data data; Node* next; }Node; typedef struct queue { Node* front; Node* rear; }Queue; void QueueInit(Queue* pq) { pq->front = NULL; pq->rear = NULL; } int QISEmpty(Queue* pq) { pq..

typedef struct queue { int front; int rear; Data arr[SIZE]; }Queue; void QueueInit(Queue* pq) { pq->front = pq->rear = 0; } int QISEmpty(Queue* pq) { pq->front == pq->rear ? 1 : 0; } int NextPosIdx(int pos) { if (pos == SIZE - 1) return 0; else return pos + 1; } void Enqueue(Queue* pq,Data data) { if (NextPosIdx(pq->rear) == pq->front) { printf("FULL BIN"); } pq->rear = NextPosIdx(pq->rear); pq-..

[원형큐 구현에 대한 이해] 원형규는 어디든지 시작점이 가능하다는게 제일 큰 장점임. 따라서 enqueue를 하든 dequeue를 하든 front와 rear의 위치를 초기화하거나 재배치할 필요가, 아니 애초에 걱정 자체를 할 필요가 없다 [원형큐 보강] 원형큐를 일반적으로 구현하면 빈상태와 꽉찬상태의 구분이 안간다 한번 생각해보면 빈상태가 front==rear인 상태일 것이다. 왜? 아무것도 없으니까 그럼 한 턴의 enqueue는 현 rear자리에 data를 집어넣고 rear++ 하는 방식으로 코드가 짜일 것이다. 그럼 이렇게 enqueue로 쭉쭉쭉 가다가 원형배열이 꽉 찼다. 그럼 rear는 어디에 있을까?? 바로 front 랑 같은 위치를 가리키고 있을 거다. 이때의 enqueue 방식은 입력 후 r..

[Queue] First In First Out ( FIFO ) 먼저 들어간 데이터가 먼저 나오는 "선입선출" 구조 [배열큐 (linear queue)] 선형큐라고도 함. 이렇게 배열큐로 구현하는게 가장 쉬운 방법이지만 명확한 단점이 존재함 dequeue를 할때마다 front를 다시 앞으로 끌어당겨와야한다는 거임 그러면서 front에서 rear 까지 데이터 다 앞으로 복사해야함 그래서 ㅈㄴ 비효율적이라 원형큐 개념이 나옴 [원형큐 (circular queue)] 원형큐 장점 어느 위치에서든 front가 될 수 있다 원은 모든 점이 시작점이 될 수 있기 때문 모든 stl의 queue는 이 원형큐로 구현이 되어있다

우선 복사생성자와 대입연산자를 헷갈리면 안됨 두 개가 호출되는 시점 차이가 있음 ㅇㅇ 대입연산자는 이미 생성된 두 객체 간 대입연산이 진행될때, 기존에 생성된 두 객체 간의 대입연산 시에 호출되는거임 (복사생성자와 호출시점 비교) operator=(Point& ref) 이 형식으로 호출되는 거임. 연산자 오버로딩의 한 종류로 오버로딩 중에서 가장 중요한 놈임! 클래스의 대입연산자는 반드시 정의해주어야한다! 대입연산자는 복사생성자와 동일한 구석이 있다. [대입연산자와 복사생성자의 공통점] 1) 정의하지 않으면 디폴트 가 자동으로 삽입된다 2) 디폴트 는 얕은 복사를 한다 ( 깊은 복사 X ) 3) 연산자 내에서 동적할당을 한다면, 깊은 복사가 필요하다면, 직접 정의해야 한다! 이와 같이 대입연산자와 복사생..