W1. D1 그리디 & 구현

(21.06.28)

그리디 알고리즘

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

그리디 해법: 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리게 하므로 정당성 분석이 중요하다.(가장 좋은 것만 반복적으로 선택했을때 최적의 해를 구할수 있는지 확인해야한다.)

---

<기본문제> 노드의 값의 합을 최대로 만들기

가장 큰값만 고르는 경우:5->10->2가 선택된다(5->7->9가 가장 크지만)

▶️일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
▶️하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할수 있어야 풀리도록 출제된다.
즉 코테 그리디 알고리즘은 탐욕법으로 얻은 해가 최적의 해가 되는 경우에 한해서 문제를 출제한다.

<기본문제> 거스름 돈

최적의 해를 빠르게 구하기 위해서 가장 큰 화폐 단위부터 거슬러 준다.(->1WHY?)
500원->100원->50원->10원 순
예)1260원=500x2,100x2,50,10
(1WHY:가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음)

📕chap3 문제

✏️문제3> 1이 될때 까지

n, k = map(int, input().split())

count = 0

while n > 1 :
  if n % k == 0:
    n = n // k
    count += 1
  else:
    n = n - 1
    count += 1
  if n == 1:
    break

print(count)

✏️문제1> 큰 수의 법칙

n, m, k = map(int,input().split())
data = list(map(int,input().split()))

data.sort(reverse=True)
first = data[0]
second = data[1]

answer = 0

while m!=0 :
    for i in range(k) :
        answer += first
        m -= 1

    answer += second
    m -= 1

print(answer)   

✏️문제2> 숫자 카드 게임

n, m = map(int, input().split())

answer = 0
for i in range(n):
  Mcards = list(map(int, input().split()))
  Mnumber = min(Mcards)
  if answer < Mnumber:
    answer = Mnumber
print(answer) 

보완할 점

1.좀 더 글이 가독성 좋도록 꼼꼼히 작성하기.
2.나와 다른 코드중 색다른 코드를 많이 찾아보기.