[자료구조와알고리즘with파이썬] ch.9 억지기법과 탐욕적 전략

9-1 문제 해결 과정

[알고리즘 개발 과정]

문제의 이해	예외 경우, 해답 생각해보기
설계 방향 설정	순차적 처리 / 병렬적 처리, 최적해 / 근사해 근사해: 정확한 해를 구할 수 없음. 계산량이 너무 많아짐. 알고리즘의 중간단계.
알고리즘 설계	억지(brute-force)기법, 탐욕적(greedy)기법, 분할 정복, 동적 계획법, 공간으로 시간을 버는 전략, 백트래킹과 분기한정 기법
알고리즘의 정확성	다양한 입력을 통해 틀린 경우를 찾기, 수학적 귀납법 등으로 증명하기
알고리즘의 구현	정확성  입증 후 특정 프로그래밍 언어로 구현하기

---

9-2 억지 기법 (brute - force)

• 순차탐색: 처음부터 마지막까지 순서대로 리스트에서 어떤 킷값을 가진 레코드를 찾는 방법
• 선택정렬: 숫자를 크기순으로 나열

---

9-3 탐욕적 기법 (greedy method)

'그 순간에 최적'이라고 생각되는 답을 선택한다. (그리고 그 선택은 이후의 단계에서 다시 변경될 수 없다.)

• 최적해를 구하는 경우 (최소비용신장트리를 위한 프림 알고리즘, 최단 경로거리를 구하는 다익스트라 알고리즘
• 시간적, 공간적 제약이 있는 경우 (분기 한정 기법)

1) 거스름돈 동전 최소화

액면가가 서로 다른 m가지의 동전이 있다. 거스름돈으로 v원을 동전으로만 돌려주어야 한다면 최소 몇 개의 동전이 필요한지를 구하시오. 단, 모든 동전은 무한히 사용할 수 있고, 액수가 크 것부터 내림차순으로 순서대로 정렬되어 있다.

 

→ 액면가가 가장 높은 동전부터 탐욕적으로 최대한 사용하면서 거스름돈을 맞춘다.

→ 60원짜리 동전이 있는 경우, 최소한으로 필요한 동전의 수가 달라질 수 있다.

 

→ 최적해를 구하기 위한 조건

동전의 액면가 중에서 어떤 두 개를 고르더라도 큰 액면가를 작은 액면가로 나누어 떨어지는 동전 체계를 갖는다면 최적해가 보장된다. 작은 액면가를 여러 개 모으면 반드시 큰 액면가를 만들 수 있기 때문이다.
ex) 500원은 100원 5개를 모아서 만들 수 있다.

 

 2) 분할 가능한 배낭 채우기

• 무게와 상관없이 가장 비싼 물건부터 넣는 방법
• 단위 무게당 가격이 가장 높은 물건부터 넣는 방법

→ 어떤 리스트가 입력되면 무게당 가치를 내림차순으로 정렬한다. 

→ 그리고 단가가 가장 높은 것부터 최대한 많이 탐욕적으로 담는다.

→ 가장 가치가 낮은 것은 담기지 않을 수도 있다.

---

9095 1, 2, 3 더하기 

1	1	1
2	1+1, 2	2
3	1+1+1, 1+2, 2+1, 3	4
4	1+1+1+1, 1+2+1, 2+1+1, 3+1, 1+3, 1+1+2, 2+2	7

f(1) = 1
f(2) = 2
f(3) = 4
f(4) = f(1) + f(2) + f(3) = 1 + 2 + 4 = 7
...
f(n) = f(n-3) + f(n-2) + f(n-1)

f(n) = f(n-3) + f(n-2) + f(n-1) 
(n>3)

import sys
input = sys.stdin.readline

def func(x):
  if x==1:
    return 1
  elif x==2:
    return 2
  elif x==3:
    return 4
  else:
    return func(x-1)+func(x-2)+func(x-3)

t = int(input())
for _ in range(t):
  n = int(input())
  print(func(n))

---

[참고자료]

https://velog.io/@greene/%EB%B0%B1%EC%A4%80-9095%EB%B2%88-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC