이것이 코딩 테스트다 - Chapter3 그리디 정리

앞으로 한챕터가 끝나면 해당 챕터의 내용에 대해

간략하게 요약정리를 하며 글을 남기겠다.

 

 

"그리디" 알고리즘이란

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

 

이렇게 부제목이 달려있다.

보통 탐욕법(욕심쟁이 알고리즘) 으로 불리기도 한다.

 

그러면 이제 어떤상황에서 그리디가 사용되는가?

 

✓ 거스름돈 -> 가장 큰 화폐부터 지급 방법
✓ 특정 수를 가장적은 횟수로 쪼개기 -> 정렬이 함께 사용되어 큰수 먼저 쪼개는 방법

 

사실 읽어보면 당연한거 아닌가? 싶은 느낌이 들기도 한다.

 

여기서 개인적으로 느낀 키포인트점은

반복문(while) 내에서 각 케이스에 해당되겠금 접근하는것도 맞는 방법이지만

"빼거나 나누는 큰수의 규칙을 찾아 한번에 계산되는 방법이 있을까?"

이것부터 생각해보는게 중요한 것 같다.

 

첫번째로 거스름돈 문제를 예시로 들겠다.

1260원을 500원, 100원, 50원, 10원으로 최소개수의 동전으로 어떻게 구할 수 있을까?

보통의 경우 500원으로 계속 쪼갠다음 다음으로 100원, 50원, 10원 순으로 순차적으로 줄일 생각이 들 것이다.

이때 보통 while을 생각하여 접근한다.

 

1) while문을 통해 접근하는 방법

while True :
    if Money>500 :
        count += 1
        Money -= 500
    elif Money>100 :
        count += 1
        Money -= 100
    elif Mondy > 50 :
        count += 1
        Money -= 50
    elif Money > 10 :
        count += 1
        Money -= 10
    else :
        break

보통 이런식으로 while문 안에서 특정 케이스에 대해

한번씩 계산을 생각할 것이다.

 

하지만 여기서 이런방법이 있다.

 

2) 나눗셈의 몫과 나머지를 통해 접근하는 방법

data = [500, 100, 50, 10]
for i in data :
    count += Money//i
    Money %= i

 

여기서 중요한 포인트는

"나눗셈의 몫과 나머지를 통해 여러번 계산될 것이 한번에 계산될 수 있다는 점이다."

 

 

또다른 예시를 보이겠다.

총 10번으로 두 수 4, 6을 사용하여 덧셈으로 구할 수 있는 최대수를 구하자. (단, 같은수 최대반복수는 3회다)

이런경우 우리는 직감적으로 4,6 중 6이 더 크므로 6을 3번 반복하여 더하고 4를 더하고 다시 6을 3번 더하고... 이런식을 반복한

6+6+6+4+6+6+6+4+6+6 = 56

 

즉, 똑같이 while문을 사용하여 접근한다면

count = 10
while True :
  for i in range(3) :
    if count == 0 :
      break
    result += 6
    count -= 1
  if count == 0 :
    break
  result += 4
  count -= 1

 

역시 while문 또는 for문을 통해 한번씩 계산하며 확인하는 식이다.

 

그렇다면 여기서 여러번을 한번에 계산가능한 방법이 있을까?

2) 나눗셈의 몫과 나머지를 통해 접근하는 방법

count = 10//(3+1) * 3 + 10%(3+1) #6을 더할 회수를 한방에 구한다
result += count * 6
result += (10-count) * 4

 

살짝 헷갈릴수도 있지만 아래 식을 다시보면 이해가 될것이다.

(6+6+6+4) 이 덩어리가 주기로 계속되어 반복되기 때문에 (최대반복회수 3 + 1) 총회수인 10을 4로나눈 몫을 구하면 덩어리가 반복된 회수를 구할 수 있다. 

이때 이 덩어리 안에 6이 3번 있으므로 3을 곱하면 "주기적으로 더해지는 회수를 통으로 구할 수 있다"

 

즉

"몫" : 제거가능한 회수를 한번에 구하자

이런 관점이 가능하다.

다음으로, 그러면 10에서 4를나눈 몫이 2며 나머지는 2가된다. 이때 2는 "주기를 벗어나 더해지는 회수를 통으로 구할 수 있다"

즉

"나머지" : 주기를 벗어난 회수를 한번에 구하자

이런 관점이 성립된다.

 

 

하지만, 위의 그리디가 가능한 경우가 느물다. 다이익스트라 방법을 사용하는 때도 있기 때문이다.

적절하게 사용하면 될 것 같다.

 

깃허브 - github.com/CodingTestStudy/FreeDeveloper_Cote/tree/main/그리디

CodingTestStudy/FreeDeveloper_Cote