조이의 개발 성장 다이어리

조합, 순열, 중복조합, 중복순열은 모두 n 개의 item에서 m개를 뽑고자 하는 경우이다. 즉, 4가지 경우 함수의 모양이 조금 다를 뿐 큰 틀은 같다. 조합(combination) : 순서와 상관없다. (0 1 2 와 2 1 0 은 같은 수로 여긴다) 순열(permutation) : 순서에 상관있다. (0 1 2 와 2 1 0 은 다른 수로 여긴다) 중복조합 : 조합이되 중복된 수가 나올 수 있다. 즉, 같은 item을 여러번 뽑을 수 있다. 중복순열: 순열이되 중복된 수가 가능하다. 즉, 같은 item을 여러번 뽑을 수 있다. 문제의 해결 순서 m개를 뽑을 공간을 미리 할당한다. (bucket) m을 뽑을 함수 (pick 함수)의 모양은 ' pick(item 정보, bucket 정보, k(앞으로 뽑..

10개의 난수(100보다 작은)를 발생시키고 몇 번째 작은 수를 찾을 것인가를 입력받은 후 그 수를 출력하는 프로그램을 작성하라. 입력 : Enter the number of numbers : 10 몇번째로 작은 수 : 4 출력 : 894 250 65 688 99 966 296 649 455 305 4번째로 작은 수는 296 #include #include #include void init_array(int list[], int n) { srand(time(NULL)); for (int i = 0; i < n; i++) *(list + i) = rand() % 100; } void print_array(int list[], int n) { for (int i = 0; i < n; i++) printf("..

퀵 정렬이란? 퀵 정렬(quicksort)은 평균적으로 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬 또한 분할-정복법에 근거한다. 2개의 부분 리스트로 분할한 후 각각의 부분 리스트를 다시 퀵 정렬한다. 그러나 리스트를 비균등하게 분할한다. 먼저, 리스트의 한 요소를 피봇(pivot)으로 선택한다. (여기서는 마지막 요소를 선택한 경우와 첫 번째 요소를 선택한 경우를 다룬다.) 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로 옮겨지고, 피봇보다 큰 요소는 모두 피봇의 오른쪽으로 옮겨진다. 이 상태에서 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 각각 정렬하면 전체 리스트가 정렬된다. 맨 마지막 요소를 pivot으로 하는 경우 - 첫번째 알고리즘 i는 left-1부터, j는 left부터 시작하여 이동한..

합병 정렬이란? 합병 정렬(merge sort)은 하나의 배열을 두 개의 균등한 크기로 분할하고 각 분할된 배열을 정렬한 다음, 두 개의 정렬된 부분 배열을 합하여 전체가 정렬된 배열을 얻고자 하는 것이다. ※ 합병 정렬은 분할정복기법(divide and conquer)에 바탕을 두고있다. 분할 정복 기법은 문제를 작은 2개의 문제로 분리하여 그 문제를 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 합병 정렬에서의 분할 정복 기법은, 분할(divide) : 중간 크기를 구하여 이를 기준으로 2개의 부분 배열로 분할한다. 정복(conquer) : 각각의 부분 배열을 정렬한다. 병합(combine) : 정렬된 부분 배열들을 하나의 배열로 통합한다. 합병 정렬은 순환 알고리즘을 적용할 수..

삽입정렬이란? 배열의 두번째 원소부터 시작해서 오름차순 혹은 내림차순으로 정렬했을 때 알맞은 자리를 찾고, 오름차순일 경우에 삽입하고자 하는 수보다 큰 수들을 뒤로 밀어낸다. 그리고 알맞은 자리에 넣고자 하는 수를 삽입하고, 이 과정을 수가 모두 정렬될 때까지 반복하는 방법이 삽입 정렬이다.(내림차순일 경우 작은 수들을 뒤로 밀어냄) 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..