[알고리즘] 이코테 - 다이나믹 프로그래밍(동적 계획법)

다이나믹 프로그래밍(동적 계획법)

• 메모리 공간을 약간 더 사용함으로써 연산속도를 비약적으로 증가시킬 수 있는 방법
• 대표적 예시는 피보나치 수열, 점화식을 사용하여 간결히 표현할 수 있는 특징. 프로그래밍에서는 배열이나 리스트로 표현 가능함. 재귀적으로 피보나치를 작성하면 n이 커질 수록 수행 시간이 기하급수적으로 늘어나는 문제. O(2^n)의 지수 시간이 소요된다.

#재귀 형식의 피보나치 수열
def fibo(n):
  if n==1 or n==2:
    return 1 # 함수 종료
  else:
    return fibo(n-1)+fibo(n-2)

 

• 다이나믹 프로그램의 사용 조건
  • 큰 문제를 작은 문제로 나눌 수 있다.(최적부분구조)
  • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.(중복되는 부분문제)
• 피보나치에 동적 계획법을 사용하기(O(N))
  • 탑다운 - 메모이제이션(캐싱) 기법 사용: 다이나믹 프로그래밍을 구현하는 방법 중 한 종류. 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져온다.
  • 한 번 푼 문제는 그 결과를 저장해놨다가 나중에 동일한 문제를 풀어야 할 때 이미 저장한 값을 반환한다.
  • 재귀함수를 사용하면 컴퓨터 시스템 상 함수를 다시 호출했을 떄 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드 발생 가능. 재귀함수 대신 반복문을 사용하면 더 성능이 좋다.

#캐싱 적용 피보나치 수열
d=[0]*10000

def fibo(n):
  if n==1 or n==2:
    return 1

  if d[n]!=0:
    return d[n]

  d[n]=fibo(n-1)+fibo(n-2)
  return d[n]

 

• 다이나믹프로그래밍: 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법.
• 퀵정렬: 정렬을 수행할 때 정렬할 리스트를 분할하여 전체적으로 정렬될 수 있는 것. 즉 분할 정복divide and conquer 알고리즘.
• 동적 계획법과 퀵 정렬의 차이점: 다이나믹은 문제들이 서로 영향을 끼친다.하지만 퀵정렬은 피벗이 자리를 변경하면 그 피벗값을 다시 처리하는 문제는 존재하지 않느다. 동적 계획법은 한 번 해결했던 문제를 다시금 해결한다. 그러므로 이미 해결된 부분 문제에 대한 답을 저장해 놓고 이 문제는 이미 해결이 되었던 것이기 때문에 다시 해결할 필요없다고 반환.
• 탑다운 방식(하향식): 재귀 함수를 이용하여 다이나믹 프로그래밍 소스 코드를 작성하는 방법, 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식.
  • 메모이제이션은 탑 다운 방식에 국한되어 사용되는 표현
  • 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념. 한 번 계산된 결과를 어딘가에 담아 놓고 다이나믹 프로그래밍을 위해 활용하지 않을 수 있다.

---

 

• bottom up 방식(상향식): 단순히 반복문을 이용하여 소스코드를 작성하는 경우, 작은 문제부터 차근차근 답을 도출한다. 다이나믹 프로그래밍의 전형적 형태. 이때 결과 저장용 리스트는 DP 테이블이다.

# 반복문 사용 피보나치 수열
d=[0]*100
d[1]=1
d[2]=1
n=99

for i in range(3, n+1):
  d[i]=d[i-1]+d[i-2]

print(d[n]) #answer

 

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하자. 특정 문제를 완전 탐색 alg로 접근했을 때 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는 지에 대해 해결하고자 하는 부분문제들의 중복 여부 확인
• 일단 재귀 함수로 비효율적 프로그램 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법.
• 보텀업으로 구현하는 것을 권장하는 데 그 이유는 시스템 상 재귀 함수의 스택 크기가 한정되어 있어 recursion depth와 관련된 오류가 발생할 수 있기 때문이다.

 

---

 

e.g., 1로 만들기: 연산 4개를 적절히 사용해서 1을 만드려고 할때, 연산을 사용하는 횟수의 최솟값을 출력하시오

1. 5로 나눠떨어지면 5로 나눈다.

2. 3로 나눠떨어지면 3로 나눈다.

3. 2로 나눠떨어지면 2로 나눈다.

4. 1을 뺀다

# 1로 만들기
n=int(input()) #26

d=[0]*30001

for i in range(2,n+1):
  #현재의 수에서 1을 빼는 경우
  d[i]=d[i-1]+1
  #현재의 수가 나누어 떨어지는 경우
  if i%2==0:
    d[i]=min(d[i],d[i//2]+1) #+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[i])

print(d[n]  )#3