[알고리즘] 그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘

 

현재 상황에서 지금 당장 좋은 것만 고르는 방법인 탐욕적으로 문제를 푸는 알고리즘

대부분 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없을 가능성이 높기 때문에 알고리즘으로 문제의 해법을 찾았을 경우 정당한지 검토해야 한다.

 

예제 3- 1 거스름돈 코드 : 시간 복잡도 O(화폐의 갯수)

직접 작성한 코드에서 수정할 부분

- C언어에서 for문을 통해 배열을 사용하는 방법에서 벗어나서 for문을 in과 함께 사용하여 list 데이터를 변수로 바로 꺼내쓸 수 있도록 한다.

ex) for coin in coin_type

- 7번째 줄 → N %= coin[i]로 간단하게 작성 가능 

 

 

실전문제 -  큰수의 법칙

처음에 m//k로 계산 실수 --> m//(k+1)로 변경

(배열의 크기로 나눠줘야 했다)

 

실전문제 -  숫자 카드 게임

 

수정해야 할 부분 

-> 모든 카드 숫자를 저장할 필요 없이 for문 하나로 min값만 저장 가능하도록

 

실전문제 -  1이 될 때까지

N, K = map(int, input().split())
count = 0

while N>1:
    N = N//K if N%K==0 else N-1
    count+=1

print(count)

 

수정해야 할 부분 

-> n >= k 일때까지만 n이 k로 나누어지는지 검사하면 된다. 그리고 마지막에 남은 수에 대해서 1씩 빼준다. 빨리하기 위해서 남은 수 - 1을 count에 더해주면 된다.

-> n이 k로 나누어떨어지지 않을때까지 1을 뺀 후 나누면 된다. 이 부분을 빨리 하기 위해서 나누어떨어지는 몫을 구하고 나머지를 n에서 빼주면 빠르게 실행 가능

 

 

 

 

참고하는 책 : < 이것이 취업을 위한 코딩 테스트다 >