［計算機アルゴリズム］Ch.1アルゴリズムの第一歩

사진을 클릭하면 PDF 정리본 다운로드 링크로 이어집니다.

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

9世紀頃、ペルシャの数学者アルコリズミの名前に由来し、

最初のアルゴリズム:BC 300年前ユークリッドのGCDアルゴリズム

問題の段階的解決
ステップ

に従って、所定の問題の解(調理法と同様)

を検索する.

効率的なアルゴリズム設計は非常に重要です
与えられた

の問題については、複数のアルゴリズムがあるかもしれないが、より効率的なアルゴリズムを常に考慮することは非常に重要である

である.

🧐 1.1最大数値の検索

に質問

トランプゲームで非常に簡単な最大の数字を見つけたいと思っています.10枚の札が地面に広げられている.

45, 60, 90, 75, 20, 55, 85, 35, 10, 25

最大の数字が書かれたカードを見つける方法の1つは、カードの数字を1つずつ比較しながら、この数字の中で最大の数字を覚えることです.最後のカードの数字を見た後、記憶の中で最大の数字が印刷されたカードを地面から1枚取った.

👨🏻‍🔬

この方式をシーケンス検索と呼ぶ.

카드를 한 장씩 차례대로(주어진 순서대로) 읽어가며 찾는 방법이다.

👩🏻‍💻 意図コード表現なら?

Alg findMax(A)

    input array A of size n
    output integer max

1. max <- A[0]

2. for i <- 1 to n-1
    if(A[i] > max)
        max = A[i]

3. return max

🧐 1.2任意の数値の検索

に質問

特定の数字が書かれたカードを探してみてください.

45, 20, 60, 35, 10, 55, 90, 85, 75, 25

最大の数字を探すように、頭の中で数字を覚え、地面に展開されたカードを順番に読み、数字が書かれたカードを探す.

👨🏻‍🔬

1.1の問題と同様に,順序探索を用いて解く方法である.

に質問

同じ10枚の札を昇順に並べておきます.順序探索よりも効果的な方法はありますか?
1枚の中間カードを読むと数字と比較し,1枚目のカードを読む順番探索よりも速くターゲットに近づく.

👨🏻‍🔬

この方式をバイナリ検索と呼ぶ.
昇順に並べられたデータを半分に分け、半分に分け、この過程を繰り返し、欲しいデータを探す探索アルゴリズム.

👩🏻‍💻 意図コード表現なら?

재귀 호출 방식

Alg binarySearchRecur(A[], left, right, key)

int mid;
static int count = 0;

if(left <= right)
{
    count++;
    mid = (left+right)/2;
   
    if(key == A[mid])
        return count;
    else if(key < A[mid])
        return binarySearchRecur(A, left, mid-1, key);
    else
        return binarySearchRecur(A, mid+1, right, key);
}

return 0;

반복 방식

Alg binarySearchIter(A[], left, right, key)

int mid, count = 0;

while(left <= right)
{
    count++;
    mid = (left+right)/2;
    if(key == A[mid])
        return count;
    else if(key < A[mid])
        right = mid - 1;
    else
        left = mid + 1;
}

return 0;

🧐 1.3おつり

に質問

買い物に小銭が必要コインの場合、最も少ないコインがほしい場合が多いです.どうすれば一番少ないコインを見つけることができますか?
残りのおつりの額を超えない前提で、最大額のコインを選択し続けてください.

👨🏻‍🔬

この方式をGreedyアルゴリズムと呼ぶ.詳細は4.1節で続きます.

🧐 1.4ブラシ

に質問

ある点から、すべての幹線道路を一度通って、起点に戻るが、軌跡を描くとき、鉛筆は紙から落ちることができない.何度も訪問してみてはいかがでしょうか.どのようにして絵を描く解決方法を見つけますか?
現在の点から始まる点から、現在の点を返すループを探します.

🧐 1.5迷宮を探す

に質問

誰も手伝ってくれなかったり、糸の塊がなかったりした場合、暗い迷宮から出られる方法は何ですか?
現在の位置で方向を選択し、右手を壁に置きます.そして出口が出るまで壁から離れずに歩きます.

🧐 1.6偽札を探す

に質問

多くのコインの山の中に偽のコインが挟まっている.偽札は目が見えず、普通の硬貨より軽い.両腕秤を使う回数を最小限に抑えるには、偽札を見つけるにはどうすればいいですか?

撤退する

1枚の硬貨を秤の左側に置き、残りの硬貨を1枚ずつ右側に置いて偽物を探します.
👨🏻‍🔬 哲洙はせいぜいn-1 n-1 n-1号秤と呼ぶ.

👩🏻‍💻 意図コード表現なら?

Alg cheolsu(A)

    input array A of size n
    output integer count

for i <- 1 to n-1
    count++
    if(A[0] != A[i])
        return count

영희2つのコインをペアにして、n/2 n/2 n/2ペアをそれぞれ秤に入れて偽札を探します.
👨🏻‍🔬 英姫は最大n/2 n/2 n/2号秤を量る.

👩🏻‍💻 意図コード表現なら?

Alg younghui(A)

    input array A of size n
    output integer count

for(i = 0; i < n; i += 2)
    count++
    if(A[i] != A[i+1])
        return count;

광수コインの山を半分に分けて、秤の両側に置いて、もっと軽い面だけを半分に分けて、半分に分けて、秤の上に置き続けます.
👨🏻‍🔬 光洙のアルゴリズムは運がいい時ではない.いつも最後に偽のコインを見つけているからだ.nnnコインがあるときは、いつもlog 2 nlog 2 nlog 2 n号秤に掛けて偽札を探します.

👩🏻‍💻 意図コード表現なら?

Alg kwangsu(A, left, right)

    input array A of size n, integer left, integer right
    output integer count

1. while(left != right)
      count++
      mid = (left + right) / 2
      if(sum(A, left, mid) < sum(A, mid + 1, right))
          right = mid
      else
          left = mid + 1

2. return count

🧐 1.7有毒な酒場

に質問

nnnは1つの酒壇に肉眼では確認できない毒薬しかない.毒のある酒を少しだけ味わって、正確には1週間後に死ぬなら、犠牲者を最小限に抑えて、毒のある酒壇を見つけるにはどうすればいいのだろうか.

Hint! 입력의 크기가 아주 작을 때 문제의 답을 찾아보자.

各壇は二進数0で、各人は酒1を味わい、酒0を味しないで、壇と人をペアにします.

ex) 단지1: 00 / 2: 01 / 3: 10 / 4: 11

👨🏻‍🔬

nn園区があれば、log 2 nlog 2 nlog 2 n人は上記の方法で味わうことができ、1週間後には必ず有毒な酒園区を見つけることができ、犠牲者は最低0人、最大log 2 nlog 2 nlog 2 n人である.

💡 サマリ

👋 シーヶンスサーチ주어진 순서에 따라 차례로 탐색한다.👋 バイナリサーチ정렬된 항목들에 대해서 중간에 있는 항목을 비교하여 그 결과에 따라 같으면 탐색을 마치고, 다르면 작은 항목들이 있는 부분 또는 큰 항목들이 있는 부분을 같은 방식으로 탐색한다.👋 小銭の問題가장 액면이 높은 동전을 항상 선택(욕심내어 선택)한다. 그리디(Greedy) 알고리즘은 4장에서 다룬다.👋 1つの問題.오일러 서킷(Euler Circuit) 문제와 같다. 알고리즘의 핵심은 현재 점에서 다음으로 이동 가능 한 점을 선택할 때에는 반드시 현재 점으로 돌아오는 사이클이 존재하여야 한다는 것이다.👋 偽札をさがす동전 더미를 반으로 분할하여 저울에 달고, 가짜 동전이 있는 더미를 계속해서 반으로 나누어 저울에 단다. 이는 분할 정복(Divide-and-Con quer) 알고리즘의 일종이며, 분할 정복 알고리즘에 대해서는 3장에서 상세히 설명한다.👋 有毒な酒壇問題2진수를 활용하여 그 해를 찾는다.