[파이썬 코테 대비 동아리]개념을 공부하자_DP편

DP란 무엇인가?

: DP = Dynamic Programming. 동적 계획법이라고 한다. 큰 문제를 작은 문제로 나누어 푸는 문제이다. 큰 문제를 작은 문제로 나누는 문제인데 왜 “동적”이란 말이 붙었는가 하면,,, 멋있어서 부여했다고 한다 ㅋㅋ

Divide and Conquer과 비슷한데, Dynamic Programming과의 차이점이라 하면 중복의 유무이다.

분할 정복은 그냥 큰 문제를 나누어 푸는 개념이라 하나의 답을 이전에 찾았어도, 같은 문제가 있으면 이전 답을 참고하지 않고 다시 푼다. 하지만 DP는 이전 답을 참고해서 문제를 풀어나간다.

또 그리디와의 차이는 최적해의 유무이다. 그리디는 최적해가 안 나올 수도 있지만, DP는 항상 최적해가 나온다.

DP의 방법?

: 중복되는 문제가 없어야 한다. 따라서 하나의 답을 구했으면 어딘가 저장해야 하므로 메모리에 저장한다. 다음 단계로 나아갔을 때 같은 문제 발생 시 이 값을 참고한다. 이를 한 단어로 Memoization이라고 한다. 메모이제이션은 하향식의 방법이고, 상향식은 타뷸레이션이다.

DP의 조건은 다음과 같다.

1. 작은 문제의 반복
2. 같은 문제는 같은 답을 가진다.

DP의 가장 유명한 예시?

: 피보나치 수열이다. 피보나치 수열은 다음 수열 = 이 전 수열 + 두 단계 전 수열의 합 이라는 식을 가진다. 여태껏 나는 피보나치 수열을 재귀 함수로 풀어왔다. 하지만 재귀 함수는 n이 무한히 커지면 그 합 또한 기하급수적으로 늘어나기에, 답을 구하기 어렵다.

시간 복잡도 또한 O(2^n)으로,,, 매우 복잡쓰. 중복되는 값을 또 구하고 구해 불필요한 계산이 늘어간다.

이를 Dynamic Programming으로 풀어보자.DP로 풀게 되면 시간 복잡도는 O(n)으로 간단해짐

(https://galid1.tistory.com/507)

n = int(input())
dp = [j for j in range(n + 1)]
for i in range (2, n+1):
	dp[i] = dp[i-1] + dp[i-2]
print(dp[n])

정말..간단하다! n을 입력받은 뒤, dp 에선 n보다 큰 수만큼 값을 저장 할 list를 만들고, for문으로 2부터 ( 피보나치는 원래 n이 2부터다) n+1까지 계산을 저장한다. for문 속 식은 우리가 아는 피보나치와 같은데, dp값들이 분할 정복과는 다르게 이미 저장된 값이 있으면 그 값을 불러온다.

이후 pring dp[n]을 해주면 끝!

이걸 상향식과 하향식으로 풀어보자.

하향식.

참고로 하향식은 재귀와 매우 유사한 메커니즘?이라고 한단다.

그래서 코딩 테스트를 볼 때, 재귀를 사용하는 문제라면

import sys
sys.setrecursionlimit(10**6)

을 꼭! 써야한단다. 파이썬 기본 재귀 깊이 제한이 1000으로 이걸 써 주지 않으면, 이 제한이 걸려서…..문제를 틀리게 됨!!!

import sys

sys.setrecursionlimit(10**8)
n = int(input())

dp = [j for j in range(n+1)]

def fibo(n):
	if n ==0:
		return 0
	if n ==1:
		return 1
	dp[n] = fibo(n-1) + fibo(n-2)
	return dp[n]

print(fibo(n))

상향식

n = int(input())
dp = [j for j in range(n+1)]
dp[0] = 0
dp[1] = 1
dp[2] = 1
def fibo(n):
	for i in range(3,n+1):
		dp[i] = dp[i-1] + dp[i-2]
	return dp[n]
print(fibo(n))

내 생각으론,, 상향식 하향식 차이는 상향식은 리스트의 아랫값을 먼저 채우고 올라가는 방법이고, 상향식은 재귀와 비슷해서 상향식엔 없어도 되는 하향식에 재귀의 제한 값을 늘렸다 !라고 요약할 수 있을 것 같다.

행렬식 피보나치O(logn)도 공부하기

다른 문제들도 풀어보자

https://school.programmers.co.kr/learn/courses/30/lessons/42895#

[N으로 표현]

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)12 = 55 / 5 + 5 / 512 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

https://school.programmers.co.kr/learn/courses/30/lessons/43105

[정수 삼각형]

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

https://www.acmicpc.net/problem/1520

[내리막길]

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

https://upload.acmicpc.net/0e11f3db-35d2-4b01-9aa0-9a39252f05be/-/preview/

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

https://upload.acmicpc.net/917d0418-35db-4081-9f62-69a2cc78721e/-/preview/

https://upload.acmicpc.net/1ed5b78d-a4a1-49c0-8c23-12a12e2937e1/-/preview/

https://upload.acmicpc.net/e57e7ef0-cc56-4340-ba5f-b22af1789f63/-/preview/

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

예제 입력 1

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

예제 출력 1