🏀 概要

アルゴリズムの探索部分は学習を続ける.
注意:
これは東彬またはYouTubeチャンネルをベースに整理されていますので、YouTubeリンクを添付します.
YouTubeにリンク

💡 方法

「整列」-整列、挿入、およびクイック整列を選択します.
ソート結果を使用する場合もあれば、ソート中に計算する場合もあります.したがって、通常サポートされるPython配列.sort()と各プロシージャが分かれば使用されます.
ナビゲーション→バイナリナビゲーション
シーケンシャルプローブとは異なり、プローブ範囲を縮小し続けるため、パフォーマンスに優れています.
しかし、きちんと並ぶと、このような条件があります.
問題の最適化に使用します.答えとして,可能な事例と最適化値を用いて,答えの事例範囲を縮小し,答えを探し出す.この点に対する理解は,問題を解くことで明らかになった.
条件によって答えの範囲を探して、範囲を縮小して答えを探します!まずはこれに集中しよう

💎 ソート選択、ソート挿入、およびクイックソート

選択ソート

重要なアイデア:最小のデータを選択!だから範囲の一番前に送ります.
コード:

for i in range(len(array)): # i를 통해서 범위 내 맨 앞 값을 지정
	min_idx = i # 가장 작은 값의 인덱스를 지정할 변수
    for j in range(i+1,len(array)): # min_idx 선택을 위한 반복
    	if array[j] < array[min_idx]:
        	min_idx = j
    array[i], array[min_idx] = array[min_idx], array[i] # 맨 앞과 min swap
 

利点:実装が容易である.欠点:for文が重なる.すなわち時間的複雑度O(N^2)は,性能が悪い.

挿入ソート

重要なアイデア:最初の値が整列していると仮定し、残りの値の位置を選択して挿入します.
選択した位置の基準は、値の大きさで挿入され、小さいものは左側、大きいものは右側です.
最終的には、右、左に位置決めして挿入することが理解される.
コード:

for i in range(1,len(array)): # 1부터 시작하는 이유는 첫 번째는 정렬되어있다고 가정하기 때문
	for j in range(i,0,-1): # 실제로 비교 대상이 되는 값을 의미한다. 가장 적합한 위치를 찾기 위한 반복문
    		if array[j] < array[j-1]:
        		array[j], array[j-1] = array[j-1], array[j] #swap
        	else:
        		break # 작지 않은 경우 적합한 위치를 찾았다고 생각하고 종료!

クイックソート

重要なアイデア:Pivotという基準データ(最初のデータ)を選択し、基準データより大きいデータを左側から
「≪検索｜Find｜Planning≫」を選択し、右側から「≪小さいデータ｜Small Data｜Planning≫」を選択します.
終了条件はleft>right,すなわちインタリーブの場合である.この場合、終了するとこれらの値は分割され、左側はPivotより小さい値に分割され、右側は大きな値に分割されます.
コード:

def quick_sort(array):
	# 재귀함수를 이용할 것이므로 종료 조건을 줘야한다.
    if len(array) <= 1:
    	return array
    
    pivot = array[0] # 기준 값, 첫 번째 원소
    target = array[1:] # 기준 값을 제외한 분할 대상 값
    
    left_side = [x for x in target if x < pivot] # 작은 값은 왼쪽으로 분할
    right_side = [x for x in target if x > pivot] # 큰 값은 오른쪽으로 분할
    
    return quick_sort(left_side) + pivot + quick_sort(right_side)

💎 バイナリナビゲーション

重要なアイデア:
中間値を基準に値を比較し、範囲を狭める.start,end,midの3つの値を基準に考えればよい.
コード:

def binary_search(array,target,start,end):
	while start <= end: # start > end가 되면 종료조건
    		mid = (start + end)//2 # 소수점은 버림. 즉 몫을 이용
        	if array[mid] == target:
        		return mid
        	elif array[mid] > target:
        		end = mid - 1
        	else:
        		start = mid + 1
     	return None # 반복문 안에서 값을 찾지못할 경우, target은 존재 하지 않는다.

🔧 例題

バイナリ探索例題でYouTubeで紹介したトッポッキの長さの問題が良い例だと思います.
私たちはハッカーランキングで以下の質問に答え、整理します.

ソート

Mark and Toys 問題のショートカット

def maximumToys(prices, k):
    prices.sort()
    i = 0
    while True:
        k -= prices[i]
        if k < 0:
            break
        i += 1

    return i

これは典型的なsort結果値を用いる問題である.
Sorting: Comparator 問題のショートカット

class Player:
    def __init__(self, name, score):
        self.name = name
        self.score = score
        
    def __repr__(self):
        pass
        
    def comparator(a, b):
        if a.score > b.score:
            return -1
        elif a.score == b.score:
            if a.name > b.name:
                return 1
            elif a.name == b.name:
                return 0
            else:
                return -1
        else:
            return 1

これは比較関数を定義する問題で、問題の要求に従ってソートできます.簡単!

ナビゲーション

Swap Nodes Algo 問題のショートカット
ツリー、順番にナビゲートする問題なので...解けたけどここで飛び越えて
Triple sum 問題のショートカット
最初から問題を見てすぐに解決する方法は

# Complete the triplets function below.
def triplets(a, b, c):
    a = list(set(a))
    c = list(set(c))
    a.sort()
    c.sort()
    b = list(set(b))
    b.sort(reverse=True)
    answer = 0
    for q in b:
        tempa = []
        tempc = []
        for p in a:
            if p <= q:
                tempa.append(p)
            else:
                break
        for r in c:
            if r <= q:
                tempc.append(r)
            else:
                break
        answer += (len(tempa) * len(tempc))
    return answer

これはfor文で比較する方法です.同様にタイムアウトも発生し,それを最適化するためにバイナリ探索法を導入した.

def check_cnt(array,target,start,end):
    if array[0] > target:
        return 0

    while start <= end:
        mid = (start + end)//2
        if array[mid] == target:
            return (mid+ 1)
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    else:
        return end + 1

def triplets(a, b, c):
    a= list(set(a))
    b= list(set(b))
    c = list(set(c))
    a.sort()
    b.sort(reverse=True)
    c.sort()
    
    answer = 0

    for q in b:

        a_cnt = check_cnt(a,q,0,len(a)-1)
        c_cnt = check_cnt(c,q,0,len(c)-1)

        answer += (a_cnt * c_cnt)

    return answer

バイナリ検索により、比較自体の回数が大幅に減少します.だから一時停止の問題を解決することができます.
問題条件に従って重複値を削除し、バイナリ・ナビゲーションをソートして使用し、バイナリ・ナビゲーションを実行します.
両方の場合、完全に一致しない場合、すべての場合が常に値より小さいため、idx+1を使用してcntを計算できます.