CS知識TIL(2)

6876 ワード
CS TIL テキストリンク

データ構造とアルゴリズム


1.BSTの最悪の場合の例と時間の複雑さを説明してください。


  • 答え
    BSTの挿入順序によっては、最悪の場合、ツリーは斜線ツリーになります.平均O(log 2 n)、最悪O(n)であり、バイナリナビゲーションツリーを完全バイナリツリーに変換できる場合、最悪の場合を解消することができる.

    • 2.コードでフィボナッチ数列を実装する方法を説明してください。


  • 答え
    数学の概念では,フィボナッチ数の第1項と第2項は1であり,後のすべての項は前の2項の和である.
    注記生成とは、再帰関数で計算された値が演算されなくなり、不要な演算が解消され、演算効率が向上し、再帰関数のフォーマットに従って高毒性コードが記述される方法である.
    アノテーション化により、再帰関数を実行するパフォーマンスが大幅に向上します.
    from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

n = 50
print('Fibonacci({}): {}'.format(n, fib(n)))

  • Pythonの機能は、無限数の数列を処理するための装置で、加速器と呼ばれています.他の関数とは異なり、返されず、収益率があります.気持ちよく屈服するときはaを折り返し車と考えればいいまた、私のウィジェットはウィジェットのすべての性質を持っており、forサイクルに入れることができます.
    def fibo3(n):
    # 제너레이터를 사용한 버전
    # 캐시가 필요없다.
    # O(N)
    a, b = 1, 1
    for n in range(n):
        yield a
        a, b = b, a + b

for n in fibo3(3):
    print(n)

    • 3.ソートとナビゲーションについて説明してください。


  • 答え
    ナビゲーションまたはソートは、要素の検索において同じですが、アルゴリズムでは、線形ナビゲーションとバイナリナビゲーションがより効果的です.リニア・ナビゲーションは、ソートされていないリストとソートされたリストで使用できますが、バイナリ・ナビゲーションはソートされたリストでのみ期待される効率を提供するため、ソートはバイナリ・ナビゲーションの1つの用途と考えられる場合があります.
    すなわち,ソートの目的は最終的にソートと呼ばれる動作によって検索する値(ナビゲーション)を迅速に検索することにあると考えられる.

  • ソートの目的:要素ナビゲーション時に効率的にナビゲーションを行う(特にバイナリナビゲーションでは線形ナビゲーションにも制限がある)

  • 探求の目的:できるだけ早く欲しい要素を見つける.線形およびバイナリ検索では、通常、バイナリ検索がより効果的です.
    https://www.codeit.kr/community/threads/5410

    • ネットワーク


    1.TCPとUDPの違いを説明します。


  • 答え

  • TCPは接続向けであり,UDPは無接続プロトコルである.

  • TCPは、送信された情報を確認するために有用なデータを送信する際に高い信頼性を提供する.失われたパケットがある場合は、再送信されます.UDPの場合、パケットが失われた場合、ターゲットコンピュータは、再転送を必要とせずに破損したデータを受信します.したがって,UDPは信頼できないプロトコルである.

  • UDPと比較して、TCPはデータを転送する前に接続が確立され、パケットの正確な転送が保証されるため、速度が遅い.逆に、UDPは、送信されたデータが受信されたかどうかをチェックしない.

  • UDPヘッダのサイズは8バイトであり、TCPヘッダのサイズはTCPヘッダの2倍以上である.TCPヘッダのサイズは20バイトであるため、TCPヘッダにはオプション、パディング、チェックサム、タグ、データオフセット、チェック番号、シーケンス番号、ソースポート、ターゲットポートが含まれる.

  • TCPもUDPもエラーをチェックできますが、TCPのみが混雑とトラフィック制御を持っているため、エラーを修正できます.
    https://ko.gadget-info.com/difference-between-tcp

    • 2.TCP 3、4番の握手を紹介します。


  • 答え
    3番の握手の過程は以下の通りです.

  • クライアントはSYNパケットを送信し、サーバへの接続を要求します.このとき、クライアントはSYNを送信し、SYN/ACK応答を待ってSYN SENT状態になる.

  • サーバは、ACKを送信し、SYN要求を受信してクライアントの要求を受信し、クライアントがACKに再応答するのを待つことを示すSYNタグが設定されたパケットを送信する.この時点で、サーバはSYN RECEIVED状態になります.

  • クライアントは、ACKをサーバに送信することから接続およびデータ交換を開始する.このとき,サーバ状態はESTABLISHEDである.
    4ウェイ握手プロセス

  • クライアントは、FINタグを送信して接続を終了します.

  • サーバは、FINパケットが正常に受信されたことを示すACKをクライアントに送信する.その後、サーバーはCLOSE-WAIT状態に入ります.

  • 接続が完了すると、サーバはFIN flagをクライアントに送信します.

  • サーバからFINタグを受信したクライアントは、確認したACKをサーバに送信し、一定期間TIME−WAIT状態に入る.

  • クライアントからACKを受信したサーバはソケットを閉じ、2つのTCP間のセッションを終了する.

  • TIME-WAITのクライアントは、サーバからのFINを受信すると、到着していないパケットを待つセッションをしばらく保持します.

    • 3.HTTPとHTTPSの違いを説明します。


  • 答え
    暗号化機能が付加されていないため、HTTPのセキュリティが悪く、HTTPSは安全にデータを送受信することができる.しかし、HTTPSの速度は、暗号化/復号化が必要であるため、HTTPよりも遅い.△今はほとんど違いを感じない.HTTPSはまた、証明書の発行と維持に追加の費用を支払う必要があります.
    個人情報などの機密データを送信および受信する必要がある場合は、HTTPSを使用します.簡単な情報クエリーのみを処理する場合は、HTTPを使用します.
    [MangKyu's Diary]
    https://mangkyu.tistory.com/98
    • 7-4ビッグデータ処理技術(下図実装)
    [fluf]下部ウィジェット