🧚‍♂️알고리즘🧚‍♂️ - 동적 계획법(DP) 1

DP / 다이나믹 프로그래밍/ 동적 계획법

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것

큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용

 

 - 큰 문제를 작은 문제로 나눌 수 있어야 함
- 동일한 작은 문제들이 반복하여 나타나는 경우/ 이 문제들의 결괏값이 항상 같은 경우 사용 가능
- 메모이제이션 기법: 작은 문제들은 한 번만 계산해 저장해 놓고 재사용
- 톱 다운 방식 / 바텀 업 방식

(Ex: 피보나치 수열)
동적 계획법으로 풀 수 있는지 확인 
(n번째 피보나치 수열을 구하는 문제는 n-1,n-2번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있음 / 수열의 값은 항상 같음)
->
점화식 세우기
( D[N] = D[N-1]+ D[N-2] )
->
메모제이션 원리 이해하기
(같은 문제가 나왔을 때 다시 계산하지 않고 저장해두었던 값을 사용하기)
->
톱 다운 구현 방식 
-위에서부터 문제를 파악해 내려오는 방식 / 재귀 함수 구현
(목표 피보나치 수열 피보나치 함수 안에 바로 입력-재귀함수 형태로 쭉 찾아냄)
or
바텀 업 구현 방식 
-작은 부분부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식/반복문 구현
(피보나치 수열 처음부터 하나하나 구하기)

---

실버5

파스칼의 삼각형

16395번: 파스칼의 삼각형

# 동적 계획법
from sys import stdin
n, k  = map(int,stdin.readline().split()) # 행,번째

pascal = [[1],[1,1]]

for i in range(2,n): #3번째 줄부터 n번째 줄까지
    pascal.append([1]) #새로운 줄 첫번째 1
    for j in range(1,i): # i면 요소 i+1개 (i+1 번째 줄)/처음마지막1 제외
        pascal[i].append(pascal[i-1][j-1]+pascal[i-1][j])
    pascal[i].append(1) #새로운 줄 마지막 1


print(pascal[n-1][k-1])

EDOC 자료 제작한거

 

---

실버3

정수를 1로 만들기

1463번: 1로 만들기

- 바텀-업 방식 사용하기

-현재 목표 수보다 1 작은 수의 연산값 +1 / 현재 목표 수 나누기 2한(가능할 시)수의 연산값 +1 /  현재 목표 수 나누기 3한(가능할 시)수의 연산값 +1=> 중에서 최솟값 선택!

from sys import stdin
from itertools import permutations

N = int (stdin.readline())
onemake = [0,0] # 메모제이션 / 1일 때는 0번 필요
 
for i in range(2, N+1): # 바텀-업 방식
    rere = [onemake[i-1]+1]

    if i % 2 == 0:
        rere.append(onemake[i//2]+1)
    if i % 3 == 0:
        rere.append(onemake[i//3]+1)
    
    onemake.append(min(rere))

print(onemake[N])

---

실버3

퇴사 준비하기

14501번: 퇴사

 

-이번에는 뒤에서부터 앞이 바텁-업 방향! => 목표치가 위치한 곳이 업 방향(상담을 일찍 시작할 수록 수입 업 하므로)

 

- 만약 목표일의 상담 기간이 퇴사일을 넘지 않는다면 목표일+1의 수입과 수입이 같다.

- 목표일의 상담 기간이  퇴사일을 넘는다면, 목표일+1의 수입/ (목표일+목표일의상담기간일)의 수입 +  목표일의상담수입 중 큰 값 선택

from sys import stdin
N = int (stdin.readline())
schedule = [[0]] # 상담스케줄
money = [0 for _ in range(N+2)] #번호맞추기 / 첫번째 if문 N번째 값 오류 해결

for i in range(N):
    A, B = map(int,stdin.readline().split())
    schedule.append([0,A,B])

for i in range(N, 0, -1):
    if i+schedule[i][1]-1 > N :
        money[i] = money[i+1]
    else:
        money[i] = max(money[i+1],money[i+schedule[i][1]]+schedule[i][2])
print(money[1])

---