조이의 개발 다이어리

삽입정렬이란? 배열의 두번째 원소부터 시작해서 오름차순 혹은 내림차순으로 정렬했을 때 알맞은 자리를 찾고, 오름차순일 경우에 삽입하고자 하는 수보다 큰 수들을 뒤로 밀어낸다. 그리고 알맞은 자리에 넣고자 하는 수를 삽입하고, 이 과정을 수가 모두 정렬될 때까지 반복하는 방법이 삽입 정렬이다.(내림차순일 경우 작은 수들을 뒤로 밀어냄) void insertion_sort(int list[], int n) { int i, j, k; int temp; for (i = 1; i ..

버블 정렬이란? 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이 과정이 한번 완료되면 가장 큰 값이 배열의 오른쪽 끝으로 이동한다. 버블 정렬(bubble sort)은 이러한 비교-교환 과정을 배열 전체가 정렬될 때까지 계속하는 방법이다. void bubble_sort(int list[], int n) { int i, j; for (i = 0; i list[j + 1]) { //list[j]가 list[j+1]보다 크면, 즉 오름차순으로 정렬되어있지 ..

선택 정렬이란? 오름차순으로 정렬할 경우, 가장 작은 숫자를 선택하여 왼쪽으로 이동하거나 가장 큰 숫자를 선택하여 오른쪽으로 이동하는 정렬 방법이다. (내림차순의 경우, 가장 작은 숫자는 오른쪽으로, 가장 큰 숫자는 왼쪽으로 이동한다) 즉, 배열에서 최소값을 찾아 이 최소값을 배열의 첫 번째 요소와 교환하고 그 다음에는 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하여 두 번째 요소와 교환한다. (최대값을 찾아 배열의 마지막 요소와 교환하고 그 당므에는 마지막 요소를 제외한 나머지 요소들 중에서 가장 큰 값을 선택하여 마지막에서 두 번째 요소와 교환한다.) 이 과정을 (배열의 크기-1) 만큼 반복하여 배열이 모두 정렬될 때까지 반복한다. 최소값을 찾아 교환하는 방식 void selec..

동적 메모리 할당이란? int a[100]과 같이 고정된 크기로 필요한 메모리 할당을 하는 방법을 정적 할당이라고 한다. 그러나 프로그램을 작성하면서 얼마나 많은 입력이 있을지 알 수가 없는 경우가 많다. 만약 고정된 크기보다 더 큰 입력이 들어온다면 프로그램을 처리하지 못하며, 더 작은 입력이 들어온다면 메모리를 낭비하게된다. 따라서, 이러한 문제를 해결하기 위해 실행 중에 필요한 만큼의 메모리를 운영체제에서 할당받아 사용하고, 사용이 끝나면 다시 시스템에 메모리를 반환하는 기능을 동적 메모리 할당(dynamic memory allocation)이라고 한다. 이 때, 동적 메모리가 할당 되는 공간은 힙(heap)이다. 힙은 운영체제가 사용되지 않는 메모리 공간을 모아 놓은 곳이다. 동적 메모리 할당 형..

포인터란? 다른 변수의 메모리 주소(바이트 단위)를 가지고 있는 변수 정수형, 실수형, 문자형 등 여러 가지 자료형으로 선언될 수 있다. 주소연산자 : & 간접 (참조) 연산자 : * ex) int *p; // 정수형 포인터 선언 int a = 200; //정수형 변수 선언 p = &a; //포인터 p는 a의 메모리 주소를 가리킨다. 즉, p는 변수 a를 가리킨다. p의 값은? : 변수 a의 주소값 *p의 값은? : 변수 a가 실제로 가지고 있는 값(200) 위 코드에 *p = 20을 마지막에 추가하면 a의 값은? : 20으로 바뀐다. 포인터 p는 변수 a를 가리키고 있어서 값을 복사하는 것이 아니다. 따라서 *p의 값을 변경하면 a의 값도 같이 바뀐다. 널 포인터 어떤 객체도 가리키지 않는 포인터이다...

구조체란? 타입이 다른 데이터를 묶는 방법 구조체 정의 - 구조체 명 struct student { int id; char name[20]; int midterm; int final; }; student : 구조체와 구조체를 구별해주는 식별자. 구조체 태그 라고도 함 id, miterm, name, final : 구조체 멤버 구조체 변수 선언 : struct student aStudent; -> 이렇게 선언해야만 메모리가 잡힘 구조체 변수 선언과 초기화 동시에 : struct student aStudent = {20191111, "율짱", 100, 90}; 구조체 정의 - 구조체 타입 typedef struct student{ int id; char name[20]; int midterm; int fin..

배열이란? 동일한 타입의 데이터를 한 번에 여러개 만들 때 사용하는 자료형 배열을 사용하면 연속적인 메모리 공간이 할당되고, 배열 인덱스가 주어지기 때문에 인덱스를 사용하여 쉽게 접근이 가능하다. C언어에서의 1차원 배열 선언 : 자료형 배열이름[배열 요소의 개수] // int list[6], char string[7], Student sList[6]; 값 설정 : 배열이름[인덱스] = 값 // list[0] = 100; 값 반환 : 값을 저장할 변수 = 배열이름[인덱스] //Student s1 = sList[0]; 인덱스는 0부터 시작한다. 메모리 주소는 배열의 첫번째 요소가 기본 주소가 되고, 그 다음 요소부터 기본주소+n*sizeof(자료형)이 된다. ex: int list[6]에서 list[0]의..

#include int max(int list[], int low, int high) { //순환 int middle; int max_left, max_right; if (low == high) return list[low]; //절반으로 나눈 끝에 low=high이면 자기 자신 반환 middle = (low + high) / 2; max_left = max(list, low, middle); //중앙에서 왼쪽 부분의 최대값 max_right = max(list, middle + 1, high); //중앙에서 오른쪽 부분의 최대값 return max_left >= max_right ? max_left : max_right; //조건 연산자 사용하여 왼쪽의 최대값과 오른쪽의 최대값을 비교하여 더 큰것을 반..

순차 탐색? 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 차례대로 하나씩 검사하여 원하는 항목을 찾아가는 방법 #include int seq_search(int key, int low, int high){ int i; for (i=low; i

이진탐색이란? 배열의 중앙에 있는 값을 알아내어 찾고자 하는 항목이 중앙의 왼쪽에 있는지 오른쪽에 있는지를 알아내어 탐색의 범위를 반으로 줄이는 방법 단, 배열이 반드시 정렬이 되어있어야하기 때문에 고정된 데이터에 적합하다. 위의 예시는 34를 찾는 경우이다. 1. 34는 중앙값인 27보다 크므로 오른쪽 부분에서 탐색한다. 2. 다시 오른쪽 부분의 중앙값인 38과 비교한다. 38보다 작으므로 왼쪽 부분에서 탐색한다. 3. 다시 왼쪽 부분의 중앙값인 30과 비교한다. 30보다 크므로 오른쪽 부분에서 탐색한다. 4. 다시 오른쪽 부분의 중앙값인 34과 비교한다. 찾고자 하는 값이 중앙값과 일치한다. 즉, 중앙값과 비교하면서 찾고자하는 항목이 중앙값보다 작으면 왼쪽에서 다시 중앙값과 비교하고, 크면 오른쪽에서..