written by yechoi

생성자 클래스의 이름과 함수의 이름이 동일하다 반환형이 선언돼 있지 않으며, 실제로 반환하지 않는다 객체 생성시 딱 한 번 호출된다 오버로딩이 가능하다 class SimpleClass { private: int num1; int num2; public: SimpleClass() { num1 = 0; num2 = 0; } SimpleClass(int n) { num1 = n; num2 = 0; } SimpleClass(int n1, int n2) { num1 = n1; num2 = n2; } }; 첫번째 방식의 생성자를 쓰려면 SimpleClass sc1; SimpleClass *ptr1 = new SimpleClass; SimpleClass *ptr = new SimpleClass(); # forbidd..

기수 정렬 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘 1의 자리수를 기준으로 오름차순으로 정렬 그 데이터를 다시 10의 자리수를 기준으로 오름차순으로 정렬 ... 반복 정렬하는 법 bucket[10] 에 자리수 별로 count 함. 19이면 bucket[9]++ 이런 식. 이 버켓을 누적함. bucket[i + 1] = bucket[i] + bucket[i + 1] 뒷 숫자부터 버켓에 담긴 인덱스 대로 집어 넣음. 맨 뒷 숫자가 37이고, bucket[7]이 3이라면 세번째 배열(result[2])에 넣는 것. 결과물 배열을 다시 원 배열에 복사 이 과정을 반복 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도 #define MAX 10000 void radixSort(int *a, ..

퀵 정렬 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법 편향된 분할이 발생할 때 연산의 양이 O(N^2) c++의 algorithm 라이브러리에 sort() 함수는 퀵 정렬을 기반으로 하며 O(NlogN)을 보장 void quickSort(int start, int end) { if (start >= end) return ; int key = start; int i = start + 1; int j = end, int temp; while (i j) // 엇갈리지 않았다면 두 값을 서로 바꿔줌 swap(&a[key], &a[j]) else // 엇갈렸으면 피봇값과 작은 값을 바꿔줌 swap(&a[i], &a[j]) } quickSort(start, j - 1); quickSort(j + 1..

선택정렬 가장 작은 것을 선택해 앞으로 보내는 정렬 기법 가장 작은 것을 선택하는 데 N번, 앞으로 보내는 데 N번 0(N^2)의 시간복잡도 int main(void) { int n, min, index; scanf("%d", &n); for (int i= 0; i a[j]) { min = a[j]; index = j; } swap(&a[i], &a[index]); } } 삽입정렬 각 숫자를 적절한 위치에 삽입하는 정렬 기법 들어갈 위치를 선텍하는 데 N번, 선택하는 횟수로 N번 총 O(N^2)의 시간 복잡도 int main(void) { int n, min, index; scan..

큐 뒷쪽으로 들어가서 앞쪽으로 나오는 자료구조 먼저 들어간 게 먼저 나옴 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용 기본적인 형태의 자료구조 연결리스트로 큐 구현하기 큐 삽입함수(push) 새 노드를 마지막 노드 뒤에 넣고 새 노드의 next가 rear를 가리키게 typedef struct { int data; struct Node *next; } Node; typedef struct { Node *front; Node *rear; int count; } Queue; void push(Queue *queue, int data) { Node *node = (Node *)malloc(sizeof(Node)); node->data = data; node->next = NULL; if (queue->cou..