[アルゴリズム]貪欲(Greedy,Greedy)

🕯️コンセプト

今の状況では、今は良いものだけを選ぶ方法です.
グリディアルゴリズムは、基準に基づいて選択されたアルゴリズムであり、問題の中で「最大順」、「最小順」などの基準を自覚せずに与える.一般に、この基準は、ソートアルゴリズムを用いる場合に満たすことができるので、gridyアルゴリズムは、ソートアルゴリズムとペアを組むことが多い.
多くのGRADYアルゴリズム問題では,問題を解決するための最低限の考え方を考え,その正当性を検討してこそ,答えが得られる.
 

👩‍💻 コード#コード#

つり銭問題

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
	n %= coin

print(count)

→通貨種別がK個の場合、時間複雑度はO(K) 

💭 いつ必要ですか。

GRADYアルゴリズムを使用するために必要な条件!

の貪欲な選択が常に安全であることを保証しなければならない.

問題の最終的な解決方法は、一部の問題に対しても最適な解決方法であるべきである.

 

👑 例

[プログラマー-スポーツウェア]

def solution(n, lost, reserve):
    
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]
    
	  # 정렬 꼭 필요
    _lost.sort()
    _reserve.sort()
    
    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
            
    return n - len(_lost)

 
[プログラマー-JOYSTIC]

def solution(name):
    answer = 0

    changed = []
    for c in name:
        changed.append(min(ord(c)-ord('A'), ord('Z')-ord(c)+1))
    
    idx = 0
    while True:
            
        answer += changed[idx]
        changed[idx] = 0
        
        if sum(changed) == 0:
            break

        left, right = 1, 1
        while changed[idx-left] == 0:
            left += 1
        while changed[idx+right] == 0:
            right += 1
        
        if left <= right:
            answer += left
            idx -= left
        else:
            answer += right
            idx += right
    
    return answer

置換アルファベットの最小値(上下最小距離)

を求める

頃最短距離を求めて追加

から置換が必要なアルファベットが現れるまで犯罪距離を求め、その最小値の方向に

を変換する.
すべてのアルファベット

を調整すると、結果値

が返されます.
→まだ全てのテックを通過していないウウウウ