배열이란 같은 자료형을 가진 변수를 하나로 묶어서 사용함 int arr[10]; // 타입 변수명[크기]; int arr[3] = {1, 3, 5}; cout

정적 메모리 할당 int arr[100]; 위와 같이 메모리를 정적으로 할당할 수 있습니다. 처음 프로그램을 만들었을 때 100칸의 배열로 유저들을 수용하려고 했습니다. 근데 100명이상의 유저들이 들어온다면 프로그램을 수정해서 200으로 변경해서 해결할 수도 있습니다. 하지만 또 300명 400명으로 된다면 매번 변경해야하며, 변경하는것이 번거로워서 1000, 10000으로 공간을 많이 만들어 놓을 수도 있습니다. 이때 200명의 사람들만 이용중이라면 공간(메모리)가 낭비될 수 있습니다. 이럴 때 동적으로 메모리를 할당할 수 있습니다. #include #include int main() { int size; scanf("%d", &size); int *arr=malloc(sizeof(int)*size)..

구조체란 타입이 다른 데이터를 하나로 묶는 방법 #include struct student { int age; char name[10]; char gender; }; int main() { struct student s1 = {14, "LJS", 'M'}; struct student s2 = {12, "KML", 'W'}; printf("%d %s, %c\n", s1.age, s1.name, s1.gender); printf("%d %s, %c\n", s2.age, s2.name, s2.gender); return 0; } // 14 LJS, M // 12 KML, W 구조체는 다음의 모양으로 만들 수 있습니다. struct 구조체명 { 변수1 변수2 .... }; 사용할 때는 다음과 같이 사용 할 수 ..

포인터란 메모리의 주소값을 저장하는 변수 *역참조 : 포인터가 가르키는 값을 가져오는것 이중 포인터란 포인터 변수의 주소를 저장하는 변수 int n = 100; // 변수의 선언 int *p = &n; // 포인터의 선언 int a = 10; int *b = &a; int **c = &b; printf("%d\n", a); // 10 printf("%p\n", &a); // 0x20 printf("%p\n", b); // 0x20 printf("%p\n", &b); // 0x24 printf("%d\n", *b); // 10 printf("%p\n", c); // 0x24 printf("%p\n", &c); // 0x28 printf("%p\n", *c); // 0x20 printf("%d\n", **c..

시간 복잡도란(Time complexity)? 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간 시간 복잡도는 주로 빅오 표기법을 사용 최선, 평균, 최악으로 나누어서 표기함 최선 : 실행 시간이 가장 빠른 경우 평균 : 평균 수행 시간 최악 : 실행 시간이 가장 느릴 경우 ex) 퀵정렬의 경우 최선, 평균 시간복잡도는 O(nlogn)이며, 최악 시간복잡도는 O(n²) 빅오 표기법 알고리즘의 효율을 분석하고 비교하는데 쓰이는 개념 최악의 경우를 고려하여 쓰여짐 상한 점근 표기법 계수와 낮은 항을 제외시킴 ex) 3n² + 2n -1 => O(n²) ex) 3n => O(n) ex) 10 => O(1) 공간 복잡도란(Space complexity)? 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 ..

정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘 대표적 정렬 - 선택 정렬 - 삽입 정렬 - 거품 정렬 - 힙 정렬 - 퀵 정렬 - 합병 정렬 정렬 방법 안전 정렬 - 정렬 후 중복값 순서가 유지 제자리 정렬 - 추가적인 메모리를 거의 사용 하지 않음 비교 정렬 - 상대적 크기관계를 통해 정렬 정렬 알고리즘 선택 정렬 삽입 정렬 거품 정렬 힙 정렬 퀵 정렬 합병 정렬 최선 n^2 n n nlogn nlogn nlogn 평균 n^2 n^2 n^2 nlogn nlogn nlogn 최악 n^2 n^2 n^2 nlogn n^2 nlogn 메모리 1 1 1 1 logn ~ n n 안정 X O O X X O 제자리 O O O O O X 비교 O O O O O O

비교 정렬 하나의 추상적인 비교 동작을 통해 목록 요소들을 읽어내는 정렬 알고리즘 데이터들간의 상대적 크기관계만을 이용해서 정렬하는 알고리즘 데이터들간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용가능 ex) 삽입정렬, 선택 정렬, 거품 정렬, 힙 정렬, 병합 정렬, 퀵 정렬 ... 시간복잡도가 O(nlogn)보다 빠를 수 없음 비비교 정렬 데이터들간의 상대적 크기관계로 정렬하지 않고 데이터에 대한 사전지식을 이용하는 정렬 알고리즘 ex) bucket sort, counting sort, radix sort 제자리 정렬 정렬에 추가적인 메모리 공간이 들지 않음 (거의 무시할 정도의 메모리를 사용) ex) 삽입, 선택, 버블, 퀵, 힙

안정 정렬 알고리즘은 반복되는 요소를 입력 때와 동일한 순서로 정렬 불안정 정렬 알고리즘은 반복되는 요소를 입력 때와 동일한 순서로 정렬을 보장하지 못함 위의 그림에서 처럼 중복되는 값이 있을 경우 안정정렬은 정렬 후에도 중복된 값들이 이전 정렬의 순서를 유지합니다. 그에 반해 불안정 정렬은 중복된 값들이 이전 정렬의 순서가 유지 되지 않을 수 있습니다. 대표적인 정렬 삽입 정렬 - 안정 버블 정렬 - 안정 합병 정렬 - 안정 선택 정렬 - 불안정 퀵 정렬 - 불안정 힙 정렬 - 불안정