[Python] DP(Dynamic Programming) 알고리즘이 뭘까?/ 개미전사 풀이 / 백준 1463번 1로 만들기 풀이

코딩하는 나

다이나믹 프로그래밍이란?
앞에서 계산한 식을 배열에 미리 저장하여
연산속도를 증가시키는 프로그래밍

계산한 건 다시 계산하지 않는 게 중요하다

DP의  예: 피보나치 수열

DP = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ]

DP[2] == DP[0] + DP[1]

2

DP[3]==  DP[1] + DP[2] 

3

즉, 앞에서 이미 계산된 값을 더해서 수열의 값을 알 수 있다.

 

 

피보나치 수열의 특징

1번째 인덱스와 2번째 인덱스의 값을 알 때, 3번째 값은 앞에 두 값을 더하면 된다

a[i] = a[i-1] + a[i-2]

def fibo(x) :
	if x == 1 or x==2:
    	return 1 #첫번째와 두번째 수열은 1이므로 1을 return
    return fibo(x -1) + fibo (x -2) #3번째 부터는 x-1번째, x-2번째 수열의 합을 통해 수열을 구함

print(fibo(4))

#실행결과 3

 

단순 재귀함수 피보나치 수열 시간 복잡도

 

출처-(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍

 

사진과 같이 f(6)의 피보나치 수열을 구한다고 하면, 동일한 부분이 여러 번 호출될 수 있다.

특히 f(2)는 여러 번 호출 된다. 

따라서 한 번 해결한 문제에 대해, 별도에 메모리 공간에 미리 계산한 값을 담아놔야한다. 

 

DP 프로그래밍의 두가지 요건

 

1. 최적 부분구조

큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결한다.

피보나치 수열은 큰 문제가 작은 문제로 나눠진다 => 큰 문제인 f(6)를 구하기 위해 작은 문제 f(5), f(4)를 모아서 해결할 수 있다

2. 중복 부분 문제

-부분 문제가 말 그대로 중첩되어 등장한다.

-동일한 작은 문제를 반복적으로 해결해야된다.

피보나치 수열에서 f(4)를 구하기 위해 f(3), f(2)

f(3)을 구하기 위해 f(2) f(1)이 호출되는 등

f(2)가 반복 호출되므로 중복 부분 문제가 성립된다

 

다이나믹 프로그래밍 방식

 

1. 탑다운(하향식, 메모이제이션 사용. 위=>아래)

2. 보텀업(상향식. 아래=>위) 두 가지로 구성된다. 

 

탑다운 

(1) 한 번 계산한 결과를 메모리 공간에 메모한다.(메모이제이션)

- 같은 문제를 다시 호출하면, 메모한 결과를 그대로 가져온다

-값을 기록해놓는다는 점에서 캐싱이라고도 함. 보통 dp, d 등의 이름으로 선언된다. 

(2) 재귀함수가 사용된다. 

 

보텀업

 작은 문제 + 작은문제 => 큰 문제가 되는 형식

반복문을 이용한다.

"어떤 방식이든 둘의 답은 같아야한다"

 

다이나믹 프로그래밍 문제 푸는법

 

(1) 다이나믹 프로그밍 유형임을 파악해야함

- 이 문제를 그리디, 구현 완전탐색 등의 아이디어로 해결할 수 있는지 생각해보자

-다른 알고리즘 풀이방법이 생각이 나지 않는다면, DP를 고려한다.

(2) 일단, 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤, 

작은 문제에서 푼 답이 큰 문제없이 그대로 사용될 수 있다면 코드를 개선하는 방법으로 DP를 사용할 수 있다

 

 

실전문제
개미전사

 

문제

• 개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다.
• 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다.
• 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.
• 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.
• 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
• 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자.
  • {1, 3, 1, 5}
• 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다.
• 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다.
• 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

 

입력 조건

• 첫째 줄에 식량창고의 개수 N이 주어진다. (3<=N<=100)
• 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0<=K<=1,000)

출력 조건

• 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

 

아이디어 생각하기

(1) 왼쪽부터 차례대로 식량창고를 털지 안 털지 결정하는 경우

(2) 특정 i번째 식량창고에 대해 털지 안 털지 결정하는 경우

2가지만 고려한다.

ⓐ (i-1)번째 식량창고를 털기로 결정한 경우, 현재의 식량 창고는 털 수 없다 ㅠㅠ

ⓑ  (i-2)번째 식량창고를 털기로 결정한 경우, 현재의 식량 창고는 털 수있다 !

따라서, ⓐ와 ⓑ중, 더 많은 식량을 털 수 있는 것을 고르면 된다. => max(ⓐ,  ⓑ)

 

★ (i-3)번째는 (i-2)를 구하는 과정에서 이미 계산 되었기에, d[i]를 구할 땐 d[i-1],  d[i-2] 만 고려한다.

 

import sys
input = sys.stdin.readline

n = int(input())
food = list(map(int, input().split()))
#다이나믹 프로그래밍 진행(보텀업 방식)
d = [0] * 100 #앞에선 계산된 결과를 저장하는 DP LIST

#첫번째 인덱스에는 식량창고의 첫번째 값을, 두번째에는 식량창고 첫번째에 두번째 중 더 큰 값을 넣는다
d[0], d[1] = food[0],max(food[0], food[1])
 
#반복문
for i in range(2,n):
  d[i] = max(d[i-1], d[i-2]+food[i])

print(d[n-1])

 

1로 만들기 / 백준 1463번 실버 3

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

(1) X가 3으로 나누어 떨어지면, 3으로 나눈다.

(2) X가 2로 나누어 떨어지면, 2로 나눈다.

(3) 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 

2

예제 출력 1 

1

 

 

예제 입력 2 

10

예제 출력 2 

3

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

 

 

아이디어 생각하기

정성스레 PPT로 하나하나 만든 경단

N이 10일 때, ⓐ -1을 하여 9가되는 경우 ⓑ 2로 나눠 5가 되는 경우

ⓐ과  ⓑ 역시 각각 연산 가능한 경우의 수가 계속해서 생기고, F(2) F(3) F(4)와 같은 함수들이 여러 번 호출된다.

이 문제는 최적부분구조와 중복되는 부분문제를 만족하고, 동일한 함수에서 구하는 값들은 동일하므로 DP를 사용할 수 있다.

그리디 문제에서의 1로 만들기와는 차이가 있다. 그리디는 단순히 나누기만 해서 적합한 해가 나오지만, 해당 문제는 여러 방법을 적절히 섞어가며 해를 구해야한다.

 

x = int(input())
d = [0] * (x + 1)  #앞에서 계산한 결과를 저장하기 위한 DP 리스트

for i in range(2, x + 1):  #보텀업 방식
  d[i] = d[i - 1] + 1  #현재 수에서 1을 빼는 경우
  if i % 2 == 0:   #현재 수가 2로 나눠지는 경우
    d[i] = min(d[i], d[i // 2] + 1)   #3가지 경우 중 가장 작은 것을 고른다.
  if i % 3 == 0:  #현재 수가 3으로 나눠지는 경우
    d[i] = min(d[i], d[i // 3] + 1)    #3가지 경우 중 가장 작은 것을 고른다.
print(d[x])