→ 중복되는 연산을 줄이자. 연산 속도와 메모리 공간을 최대한 으로 활용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효울적인 알고리즘을 작성해야 한다.
- Top down\탑 다운
- Bottom Up\바텀 업
- Memoization
다이나믹은 '프로그램이 실행되는 도중에'라는 의미이다. 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이다.
ex) 피보나치 수열
an = an-1 + an-2, a1 = 1, a2 = 1
⇒ 프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문이다.
피보나치 수열을 재귀적으로 구현한 코드
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(4))*문제점
⇒ f(n) 함수에서 n이 커지면 커질수록 재귀적으로 수행 시간이 기하급수적으로 늘어난다. 시간 복잡도를 계산해보면 O(2^n)의 시간 복잡도를 갖는 것을 확인할 수 있다.
- 해결
⇒ 이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들수는 있지만, 단순히 매번 계산하도록 하면 문제를 효울적으로 해결할 수 ㅇ벗다. 이러한 문제는 다이나믹 푸로그래짐을 사용하면 해결할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모이제이션
다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 말한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다.
다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 사실 큰 문제를 작게 나누는 방법은 퀵 정렬에서도 소개된 적이 있다. 퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다. 이는 분할 정복 알고리즘으로 분류된다.
재귀함 수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다.
재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 말한다.
반면에 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업 방식 이라고 한다.
탑다운
→ 메모이제이션, 방식은 하향식이라고도 하며, 보텀업 방식은 상향식이라고도 한다. 다이나믹 프로그래밍의 전형적은 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
수열은 배열이나 리스트로 표현할 수 있다고 했는데, 메모이제이션은 떄에 따라서 다른 자료형, 예를 들어 사진(DICT)자료형을 이용할 수도 있다. 모든 an-1 이전의 수열이 필요한게 아니라 an만 필요한 경우가 있다. 이럴 떄에는 사전 자료형을 사용하는 게 더 효과적이다.
1로 만들기
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
- X가 5로 나누어 떨어지면, 5로 나눈다.
- X가 3으로 나누어떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- X에서 1을 뺀다.
# 못품 / 수열 식을 세워라잉..
x = int(input())
d = [0] * 30001
# i가 x와 동일하듯이 작동한다.
for i in range(2, x+1):
d[i] = d[i-1] + 1
if i % 2 == 0:
d[i] = min(d[i], d[i // 2]+1)
if i % 3 == 0:
d[i] = min(d[i], d[i // 3]+1)
if i % 5 == 0:
d[i] = min(d[i], d[i // 5]+1)
print(d[x])바닥 공사
가로의 길이가 n, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1x2, 2x1, 2x2 덮개를 이용해 채우고자한다.
# 바닥 공사 품
n = int(input())
d = [0] * 1001
d[1] = 1
d[2] = 3
for i in range(3, n+1):
# 2x1은 마지막에 하나 올 수 있고 앞에 길이가 i-1 그외에 나머지 두개는 모두 i-2에다가 붙임
d[i] = (d[i-1] + d[i-2]*2)%796796
print(d[n])