그리디 알고리즘 & 구현

😆 동빈나 님의 이코테 2021 강의 몰아보기를 보면서 공부한 내용을 정리하고 있습니다. 책은 이것이 취업을 위한 코딩 테스트다 with 파이썬을 참고하여 학습했습니다.😊

그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

• 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. (만약 현재의 선택이 나중에 미칠 영향을 고려해야 하는 경우는 그리디로 풀 수 없어)

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

→ 그리디 해법은 그 정당성 분석이 중요!

🎈 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하자!

하지만 그리디 알고리즘은 일반적인 상황에서는 최적의 해를 보장할 수 없을 때가 많다!

• 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제한다! (많은 유형을 접해보고 문제를 풀어보며 훈련해야함)

문제에 대한 정당성 분석이 매우 중요

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

문제를 풀 때의 마인드셋

→특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지 파악해보자.
→그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’ , ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다.
즉 그리디 알고리즘 문제는 대체로 정렬 알고리즘과 짝을 이뤄 출제되니까 생각하면서 풀자.

그리디 알고리즘의 대표적인 문제들
→거스름돈 문제

• 편의점 알바가 500, 100, 50, 10 원짜리 동전을 무한정 가지고 있다.
• • 손님에게 거스름돈을 최소한의 동전개수로 거슬러주기 위해서는 어떻게 해야할까??

→해결

• 풀이
  • 돈의 단위가 큰 동전부터 우선적으로 거술러주면 된다.
  • 예를 들어 거스름돈이 1,250 원일 경우, 총 5개의 동전으로 거술러 주는 것이 동전 수를 최소화 하는 방법이다.
    • 500 * 2
    • 100 * 2
    • 50 * 1
• 정당성 분석
  • 왜 큰 화폐단위부터 거슬러주는게 최적의 해를 보장하는 것일까?
  • 가지고 있는 동전 중에서 가장 큰 단위가 항상 작은 단위의 배수가 되므로 작은 단위의 동전을 종합해서 다른 해가 나올 수 없기 때문이다. → 이걸 빠르게 판단했어야 해
  • 예를 들면 800원이 거스름 돈이라고 할 때, 500원, 400원, 100원이 있다면,
    • 그리디로 풀게되면 500 1 + 100 3 = 총 4개의 동전이 답이 된다.
    • 하지만 정답은 400*2 = 2개이다.
    • 이 경우, 500원이 400원의 배수가 아니기 때문에 400원을 조합해서 다른 해가 나올 수 있게 되는 것!
• 그리디 알고리즘 정리
  1. 문제 풀이를 위해서 최소한의 아이디어 떠올리기
  2. 그 해답이 정당한지 분석하기

n = 1260
count = 0
#큰 단위 화폐부터 차례대로
coin_types = [500,100,50,10]
for coin in coin_types:
	count += n    #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
	n %= coin

print(count)

코딩테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자
→ 처음에 문제를 만났을 때는 다양한 아이디어를 고려해야한다.

아이디어를 코드로 바꾸는 구현

코딩테스트에서 구현이란 ‘머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정’이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

• 보통 알고리즘 대회에서 구현 유형의 문제
  • 풀이를 떠올리는 건 쉬운데 소스코드로 옮기기 어려운 문제
• 대표적인 유형들
  • 알고리즘은 간단하지만 코드가 지나칠만큼 길어지는 문제
  • 실수 연산을 다루고 특정 소수점 자리까지 출력해야하는 문제
  • 문자열 특정한 기준에 따라서 끊어 처리해야하는 문제
  • 적절한 라이브러리를 찾아서 사용해야하는 문제

👻 구현 문제 풀 때는 규칙성을 어느정도 생각할 필요가 있다 !!