조이의 개발 성장 다이어리

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]보다 크면, 즉 오름차순으로 정렬되어있지 ..

#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; //조건 연산자 사용하여 왼쪽의 최대값과 오른쪽의 최대값을 비교하여 더 큰것을 반..

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

사이클 길이? 어떤 정수 n이 짝수면 2로 나누고 홀수면 3을 곱한 다음 1을 더한다. 이런 과정을 반복하면서 n=1이 되면 멈춘다. 이 때 1이 나올 때까지 만들어진 수의 개수를 (n과 1 포함) 사이클 길이라고 한다. 입력 : 22 출력 : 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 사이클 길이는 16 위와 은 수열을 출력하고 사이클 길이를 리턴해주는 함수를 순환을 이용하여 작성하시오. int get_cycle_number(int n) { int cycle_length = 1; printf("%d ", n); //수열을 만들면서 숫자 출력 if (n == 1) return count; else if (n % 2 == 0) //n이 짝수이면 cycle_length+=g..

하노이탑 문제 막대 A, B, C가 있고 막대 A에 아래에서부터 크기가 큰 순서대로 원판이 쌓여있다. 막대 A의 원판들을 막대 C에 옮겨야한다. 이 때 지켜야할 3가지 조건이 있다. 한 번에 하나의 원판만 이동할 수 있다. 맨 위에 있는 원판만 이동할 수 있다. 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다. 중간의 막대를 임시적으로 이용할 수 있으나 이 역시 앞의 조건들을 지켜야 한다. 원판이 3개일 경우 A에서 C로 이동하는 과정을 그림으로 그리면 다음과 같다. 원판의 개수가 n개라고 할 경우, 다음과 같이 단순하게 생각할 수 있다. A에 쌓여있는 위에서부터 n-1개의 원판을 B에 이동하고, 제일 밑에 있는 하나의 원판을 C로 옮긴다. 그리고 다음으로 B에 있던 n-1개의 원판을 C로 옮긴다. 이를..

순환(recursion) 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 ex 1) 팩토리얼 int factorial(int n) { if (n