[알고리즘] 탐욕법(그리디, Greedy)

연수·2022년 3월 18일
0

algorithm

목록 보기
3/6

🕯️개념

현재 상황에서 지금 당장 좋은 것만 고르는 방법

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로', ‘가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘은 정렬 알고리즘과 자주 짝을 이뤄 출제된다.

대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 


👩‍💻 코드

예제) 거스름돈 문제

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)

 


💭 언제 필요해?

그리디 알고리즘을 사용하기 위해 필요한 조건!

  1. 탐욕적인 선택이 항상 안전하다는 것이 보장되어야 한다.
  2. 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이어야 한다.

 


👑 예제

[프로그래머스 - 체육복]

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)

 

[프로그래머스 - 조이스틱]

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
  1. 알파벳 바꾸기의 최소값 구하기 (상하 최소 거리)
  2. 좌우로 최소 거리 구해서 더해주기
    1. 바꿔줘야 하는 알파벳이 나오기까지 죄우 거리를 구하고, 그 중 최소값이 되는 방향으로 전환
  3. 모든 알파벳이 조정된 경우 결과값 반환

→ 아직 모든 테케를 통과하지 못했다 ㅠㅠ

 

profile
DCDI

0개의 댓글