指導課程CS 50指導第2期第4週

49165 ワード

コーチングスタッフ2期ガイドコース cs50 テキストリンク

📌 アルゴリズム#アルゴリズム#

アルゴリズム#アルゴリズム#

問題を解決する一連の動作の集合またはプロセス

サーチアルゴリズム

線形検索:配列インデックスを最初から最後まで追加して、値が値に属しているかどうかを確認します.

バイナリ検索:配列がソートされている場合は、配列の間のインデックスから開始し、検索する値と比較して、より小さな(より小さな値を格納する)インデックスまたはより大きな(より大きな値を格納する)インデックスに繰り返し移動できます.

アルゴリズムシンボル

Big O表現:Oは「on the order of」の略で、簡単に言えば「~まで大きくなる」ということです.O(n)はnと同じ大きさなので,nの増加とともに線形に増加した.O(n/2)はO(n)とも考えられるが,nが最終的に大きくなると1/2はあまり意味がないからである.

💡 実行時間の上限が低いアルゴリズムのほうがいいですか、下限が低いアルゴリズムのほうがいいですか。

の上限を下回るアルゴリズムがより良い.上限の低いアルゴリズムほど時間効率が高く,より良いアルゴリズムといえる.

アルゴリズムの時間的複雑さ

Big O-最悪の場合、アルゴリズムの実行時間の上限は

です.

メガΩ-最適の場合、アルゴリズムの実行時間の下限は

である.

メガビットプラグ-Oとオメガは、同一の場合、プラグ

として表す.

ソートアルゴリズム

選択ソート
-ソートされていない数の最小数を検索し、最初のソートされていない場所の数と交換します.
- O(n^2)

バブルソート
-2つの隣接数を比較しながら位置を交換するソート
- O(n^2)

連結ソート
-要素が1つの要素になるまで、半分ずつ並べ替えます.
- O(nlogN)

ソートの挿入
-配列内のすべての要素を前から順にソートされた部分と比較し、独自の場所を見つけて挿入するソート方法.
- O(n^2) Ω(n)

ソートアルゴリズムの実行時間

運転時間上限
-O(n^2):選択位置合わせ、泡位置合わせ
- O(n log n)
-O(n):線形検索
-O(logn):バイナリ検索
- O(1)

運転時間下限
-Ω(n^2):選択位置合わせ、泡位置合わせ
- Ω(n log n)
- Ω(n)
- Ω(log n)
-Ω(1):線形検索、バイナリ検索

復帰する

関数呼び出し

💡なぜ重複文を使って再帰を使うことができるのでしょうか。

再帰的な利点は、コードの記述が簡潔で、可読性が高いことである.ただし、再帰的にsystemstackを使用すると、重複文で実現されるコードに比べてメモリの使用効率が低下します.

連結ソート

連結ソートは、1つの要素を連続的に半分に並べ替えてから連結ソートする方法です.

💡 ソートまたはバブルソートの選択と比較して、マージソートにはどのような利点と欠点がありますか?

を並べ替えたbigoタグ法から,他の並べ替えアルゴリズムよりも時間が短いという利点があるが,配列を分割する過程でメモリ使用量が増加し,ある程度並べ替えた場合に効率が低下する.

チームタスク👩🏻‍💻

デジタルAnnerma

を検索
コード

Bubbleを使用してソート

#include <stdio.h>

void bubbleSort(int num[]); // 함수 미리 정의 해주기
void isAnagram(int original[], int num[]);

int main(void){
    // TestCase
    // 입력값: 12345, 54321 -> 출력값: True
    // 입력값: 14258, 25431 -> 출력값: False
    // 입력값: 11132, 21131 -> 출력값: True
   int original[5] = {1,1,1,3,2};
   int num[5] = {2,1,1,3,1};
   // 각각의 배열을 정렬해주기 
   bubbleSort(original);
   bubbleSort(num);
   isAnagram(original, num);   
}

void bubbleSort(int num[] ){
   int temp = 0;
   for(int i = 0; i<5; i++){
      for(int j = 0;  j <5 - i - 1; j++){
         if(num[j] > num[j+1]){
            temp = num[j];
            num[j] = num[j+1];
            num[j+1] = temp;
            }
        }
    }
}

void isAnagram(int original[], int num[]){
   for(int i =0; i < 5; i++){
      if(original[i] != num[i]){ 
            printf("False\n");
            return ;
         }
    }
    printf("True\n"); 
}

コード

入力値

を比較する

#include <cs50.h>
#include <stdio.h>

int main()
{
    int arr1[5];
    int arr2[5];
    int count = 0;

    printf("첫번째 값을 입력하세요\n");
    for(int i =0; i<5; i++){
        arr1[i] = get_int("%d : ",i+1);
    }

    printf("\n두번째 값을 입력하세요\n");
    for(int i =0; i<5; i++){
        arr2[i] = get_int("%d : ",i+1);
    }
    
    for(int i = 0; i<5; i++){
        count = 0;
        for(int j =0; j<5; j++){
            if(arr2[j] != -1 && arr1[i] == arr2[j]){ 
                arr2[j] = -1; // -1로 체크 처리
                break;
            } 
            count++;
        }
        if(count == 5){
            printf("False\n");
            return 1;
        }
    }

    printf("True\n");

    return 0;
}

友達と最短距離で家を探して

問題

は、平均ではなく中心値を使用して解決する必要があります.

#include <stdio.h>
int main(void) {
   int a[5] = {3, 2, 6, 4, 2};
   int n = 5;
   int median, left, right, i, j, temp;
   int sum_dist = 0;
   left = 0;
   right = n-1;
   
   do {
     median = a[left];
     i = left;
     j = right;
     while (i<=j) {
       while (i <= right && a[i] <= median) i++;
       while (j > left && a[j] >= median) j--;
       if (i < j) {
         temp = a[i];
         a[i] = a[j];
         a[j] = temp;
       }
     }
     a[left] = a[j];
     a[j] = median;
     if (j < n/2) {
       left = j+1;
     } else {
       right = j-1;
     }
   }while (j != n/2);
   
   printf("%d\n", median);
   return 1;
}

最短時間で橋を渡る(難易度上)

メソッド1
-1番と2番過去>1番戻り>n-1番とn番過去>2番戻り>(1番と2番過去)
-合計時間:2番+1番+n番+2番(+2番)

メソッド2
-1番とn番過去>1番戻り>1番とn-1番過去>1番戻り>(1番と2番過去)
-合計時間:n番+1番+n-1番+1番(+2番)

// !!!! Ellie코치 3조 코드 !!!!
#include <stdio.h>

void array_sort(int *arr, int n){ // 배열 오름차순 정렬
   for(int i=0; i<n; i++){
     for(int j=0; j<n-i-1; j++){
         if(arr[j]>arr[j+1]){
           int temp= arr[j];
           arr[j] = arr[j+1];
           arr[j+1] = temp;
         }
      }
   }
}

void method_1(int *arr, int n){ // 첫 번째 방법 총 시간 계산
   int total= 0;
   for(int i=n-1; i>2; i-=2){
   	total+= 2*arr[1] + arr[i] + arr[0];
   }
   if(n%2 == 0){
   	total+= arr[1];
   }
   else{
   	total+= arr[0] + arr[1] + arr[2];
   }
   printf("%d\n", total);
}

void print_method_1(int *arr, int n){ // 첫 번째 방법 과정 출력
   for(int i=n-1; i>2; i-=2){
     printf("%d%d\n", arr[0], arr[1]);
     printf("%d\n", arr[0]);
     printf("%d%d\n", arr[i-1], arr[i]);
     printf("%d\n", arr[1]);
   }

   if(n%2 == 0){
     printf("%d%d\n", arr[0], arr[1]);
   }
   else{
     printf("%d%d\n", arr[0], arr[2]);
     printf("%d\n", arr[0]);
     printf("%d%d\n", arr[0], arr[1]);
   }
}

void method_2(int *arr, int n){ // 두 번째 방법 총 시간 계산
   int total= 0;
   for(int i=n-1; i>1; i--)
   {
   total+= arr[0] + arr[i];
   }
   total+= arr[1];

   printf("%d\n", total);
}

void print_method_2(int *arr, int n) // 두 번째 방법 과정 출력
{
   for(int i=n-1; i>1; i--)
   {
     printf("%d%d\n", arr[0], arr[i]);
     printf("%d\n", arr[0]);
   }
   printf("%d%d\n", arr[0], arr[1]);
}

int main()
{
   int n;
   scanf("%d", &n);

   int arr[n];
   for(int i=0; i<n; i++)
   {
     scanf("%d", &arr[i]);
   }

   array_sort(arr, n);


   if(arr[1]*2 < arr[0]+arr[n-2])
   {
     method_1(arr, n);
     print_method_1(arr, n);
     }
   else
   {
     method_2(arr, n);
     print_method_2(arr, n);
   }
}

最大降下距離(難易度)

を探す
各列の上部のボックス数

の右側のスペース数から、最大値

を保存します.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>   

int main()
{
    int n = get_int("N : ");
    int m = get_int("M : ");

    int arr[n];

    int max = 0;
    int count = 0;

    for(int i =0; i<n; i++){
        arr[i] = get_int("%d : ",i);
    }

    for(int i =0; i<n; i++){
        count = 0;
        for(int j = i+1; j<n; j++){
            if(arr[i] > arr[j]){
                count++;
            } 
        }

        if(count > max){
            max = count;
        }   
    }

    printf("%d\n",max);

    return 0;
}

レビュー🏻

おもしろい質問がたくさんあった4週目2番目の問題は考えのない平均値ですよね?次に直接平均値で解き、~ではなく中心値~所与の例では平均値と中心値は同じであるが、{0,0,0,4}の場合、平均値1で全距離の和を6とし、中心値0で全距離の和を4とするので、距離の和の最小の中心値で距離を計算する必要がある.3番目の問題は一番難しいです.ヒントを見ずに答えてはいけない質問です.最短時間には2つのケースがあり、状況に応じてどのケースを選ぶかを決めます.この2つの状況を考え出すのは難しい過程だが、実現するのは難しくない問題だ.4番目の問題は意外に簡単だ.3番より簡単なようですが...もうすぐ4週間!!時間が経つのは早いですね.次の2週間も頑張りましょう.

Reference

この問題について(指導課程CS 50指導第2期第4週), 我々は、より多くの情報をここで見つけました https://velog.io/@sainkr/부스트코스-CS50-코칭스터디2기-4주차

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

プロジェクト内で詳細ページに直接ジャンプしてメインインタフェースに戻る

ホームキーを長く押すと現在のタスクが表示されます