[알고리즘] 동적 계획법(Dynamic Programming) 기초

timdalxx·2022년 1월 30일
1

algorithm

목록 보기
3/5

SW Expert Academy 1차시~ 5차시 를 참고하여 작성된 글입니다.

1. 피보나치수

Introduction

다음과 같은 조건일 때 n번째 달의 토끼 수는?

  • 첫 달에는 새로 태어난 토끼 한쌍이 존재
  • 두 달 이상 된 토끼는 번식 가능
  • 번식 가능한 토끼는 매달 새끼 한 쌍 낳음
  • 토끼는 죽지 않음

정답

  • n번째 달 : a쌍
  • n+1번째 달 : b쌍(새로 태어난 토끼 포함)
  • n+2번째 달 : a+b쌍(a만큼의 자식을 낳음)
  • 결론 : f(n+2) = f(n)+f(n+1)

Concept

피보나치 수열
0과 1로 시작하고 이전의 두 수의 합을 다음 항으로 하는 수열

Code 1

def fibo(n):
	if n<2:
		return n
	else : 
		return fibo(n-1) + fibo(n-2)

BUT! 피보나치 수를 재귀함수로 구현하는 경우, 엄청난 중복 호출 존재

2. 수학적 귀납법과 비둘기 집의 원리

수학적 귀납법

피보나치 함수의 중복 호출이 얼마나 있는지 알기 위해 이용하는 방법

1) 귀납 기본 : 주어진 등식이 n=1(또는 n=0)일 때 성립함을 증명
2) 귀납 가정 : 임의의 n일 때 성립한다고 가정
3) 귀납 단계 : n+1일 때 성립함을 증명
4) 모든 n에 대하여 성립

증명 : 수학적 귀납법

가정 : 재귀적 알고리즘으로 구성한 재귀 트리의 노드의 수 : T(n)T(n) 라고 하면
n≥2n\geq2인 모든 nn에 대하여 T(n)>2n/2T(n)>2^{n/2}
1) 귀납 기본 : T(2)=T(1)+T(0)+1=3>2=22/2T(2) = T(1)+T(0)+1 = 3>2 = 2^{2/2}
2) 귀납 가정 : 2≤m<n2\leq m < n 인 모든 mm에 대해서 T(m)>2m/2T(m)>2^{m/2} 라고 가정
3) 귀납 단계 :
T(n)=T(n−1)+T(n−2)+1T(n) = T(n-1)+T(n-2)+1
>2(n−1)/2+2(n−2)/2+1> 2^{(n-1)/2} + 2^{(n-2)/2} +1
>2(n−1)/2+2(n−2)/2> 2^{(n-1)/2} + 2^{(n-2)/2}
=2∗2(n/2)−1= 2*2^{(n/2)-1}
=2n/2=2^{n/2}

비둘기 집의 원리

  • 비둘기 : n+1 마리
  • 비둘기 집 : n개
  • 각각 임의의 비둘기 집을 선택하여 들어감
  • 한 개의 집에는 적어도 2마리 이상의 비둘기가 있음

증명 : 귀류법

가정 : n+1n+1 개의 물건을 nn개의 상자에 넣을 때 적어도 한 상자에는 두 개 이상의 물건이 들어 있다
1) nn개의 상자와 n+1n+1개의 물건이 있다고 가정
2) 만약 각 상자에 하나 이하의 물건이 들어있다면, 모든 상자 속 물건의 합계는 많아봤다 nn개 = 가정에 모순되는 결론
3) 따라서 적어도 한 개의 상자에는 두 개 이상의 물건이 있다

증명 : 귀류법

가정 : 피보나치 수열의 중복
1) n번째 피보나치 수를 구하기 위해 알아야 할 값 : fibo(0)fibo(0) ~ fibo(n−1)fibo(n-1)까지의 값
2) n번째 피보나치 수를 구하기 위해 재귀 호출로 작성된 fibo(n)fibo(n)함수 호출
- fibo()fibo() 함수 2n/22^{n/2} 번 이상 호출
- 2n/2>n2^{n/2} > n
3) 위 증명을 통해 피보나치 함수 재귀적 호출이 많은 중복을 야기함을 알 수 있음

결론 : 피보나치 함수의 시간 복잡도는 n이 커질 수록 2n2^n에 비례하여 증가한다.

3. 메모이제이션과 동적 계획법

메모이제이션(memoization)

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술
= 동적 계획법을 적용하기 위해 사용되는 핵심 기술

피보나치 수를 구하는 알고리즘에서 입력 값 n에 대한 계산 결과를 저장하면 실행시간을 O(n)O(n)으로 줄일 수 있다.

Code2

# memo 배열을 할당하고, 모두 0으로 초기화
# memo[0]을 0으로 memo[1]은 1로 초기화

def fibo(n):
	if n>=2 and memo[n] = 0:
    		memo[n] = fibo(n-1) + fibo(n-2) # 처음 계산되는 값이라면 값 저장
	return memo[n]

BUT! 추가 메모리 공간이 필요하므로 n값이 커질 수록 실행 속도가 저하되며, 스택 오버플로우가 발생할 수 있음

동적 계획(Dynamic Programming)

작은 부분에서 큰 부분의 해들을 모두 구하여 최종적으로 원래 주어진 문제를 해결하는 설계 기법

1) 최적화 문제 해결 : 최대값/최소값 구하는 문제, 여러 개의 최적해 중 임의의 최적해 하나를 찾는 것
2) 완전 검색을 좀 더 효율적으로 하는 방법
3) 재귀 + 메모이제이션
4) 점화식을 찾으면 됨 : 문제를 분석하여 재귀적 정의 및 수식 형태 표현 필요

적용 요건

1) 중복 부분문제 구조

- 순환적인 관계(recurrence relation)의 명시적 표현 : 점화식 사용
- 문제의 순환적 성질로 이전에 계산된 작은 문제의 해가 더 큰 문제의 해를 구할 때 중복으로 사용됨
- 메모이제이션 사용
- 이미 해결한 작은 문제의 해가 다시 필요할 때 테이블을 참조하여 중복 계산을 피함

2) 최적 부분문제 구조

- 주어진 문제가 최적화의 원칙을 만족해야 동적 계획법을 효율적으로 적용 가능
- 최적화 원칙 : 어떤 문제에 대한 해가 최적일 대 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 함

최적화 원칙이 적용되지 않는 예 : 최장 경로 문제

- 최장 경로 : 사이클이 없는 단순 경로

분할 정복 vs 동적 계획

특징분할 정복동적 계획
문제 분할주어진 문제를 부분 문제들로 분할부분문제들이 더 작은 부분문제들의 해를 공유
부분문제 해의 목적더 큰 부분 문제들의 해를 구할 때 사용더 큰 부분 문제에 중복하여 속할 수 있음
부분문제 해의 계산부분문제를 재귀적으로 해결하고 필요시 각각의 해를 결합모든 부분문제를 한번만 계산하여 결과 저장
부분문제 해의 활용병합 정렬과 퀵 정렬은 작은 문제의 해가 큰 문제의 해에서 중복해서 사용되지 않음필요시 재사용
부분문제 사이 의존적 관계하향식 방법 : 주어진 큰 문제를 위한 작은 문제들이 존재상향식 방법 : 의존성에 위배되지 않게 작은 문제의 해를 구해 더 큰 문제 해를 구함

동적 계획법 적용 방법

1) 최적해 구조의 특성 파악 : 문제를 더 작은 부분 문제로 나눔
2) 최적해 값의 재귀적 정의 : 부분 문제들의 최적 해를 사용하여 더 큰 문제의 최적해 값 정의(점화식 사용 가능)
3) 상향식 방법으로 최적해 값 계산 : 의존성에 위배되지 않도록 가장 작은 부분문제부터 해를 구하고 테이블 저장, 이를 이용하여 상위 문제 해결

피보나치 수열과 동적 계획법

Code 3

f = [] * n

def fibo_dp(n):
	f[0] = 0
    f[1] = 1
    for i in range(2, n):
    # n=2인 문제부터 시작해서 큰 문제를 해결해나감
    	f[i] = f[i-1] + f[i-2]
    return f[n] # n번째 인덱스에 n번째 피보나치 수가 저장된 상태

결론 : 피보나치 수를 동적 계획법을 적용하면 재귀 알고리즘에 비해 수행속도 빠름(함수 호출 및 중복 계산이 없기 때문)

4. 동전 거스름돈 문제와 이항 계수 문제

동전 거스름돈 문제

동적 계획법의 적용

사용할 수 있는 동전이 1원, 4원, 6원일 때 거스름돈 8원에 대한 최소 동전 개수는 몇 개일까?
그리디 방법 접근 : 6 / 1 / 1 원
최적해 : 4 / 4 원

거스름돈 8원에 대한 재귀적 알고리즘

= 3가지 동전 각각을 선택하여 재귀적으로 해결

  • 1원 + 7원에 대한 최적해
  • 4원 + 4원에 대한 최적해
  • 6원 + 2원에 대한 최적해
  • 3가지 해 중 최소가 되는 해인 최적해를 구함

동적 계획법 접근 : 상향식

  • 1원에 대한 최적해부터 8원에 대한 최적해까지 점차적으로 구해나감
  • 거스름돈 금액 0원~ 원하는 금액까지 1원씩 증가시켜 모든 부분 문제의 해를 구함
change = 0 # 거스름돈
coin = [6,4,1]
memo = []*n

def coin_change(change):
	memo[0] = 0 # 거스름돈이 0일때는 0개의 동전이 필요
    for n in range(1,change):
    		n_min = 9999999 # 무한대
            for i in range(1, len(coin)-1):
            	if n>=coin[i]:
                	if memo[n-coin[i]] < n_min :
                    	#현재 선택한 동전의 금액을 차감한 금액이 최소값인지 계산
                    		n_min = memo[n-coin[i]]
             memo[n] = n_min +1
    return memo[change] # 거스름돈이 change일 때 필요한 최소 동전 갯수를 반환

이항 계수 문제

(x+y)4=x4+4x3y+?x2y2+4xy3+y4(x+y)^4 = x^4+4x^3y+?x^2y^2+4xy^3+y^4
이항정리 : (x+y)n(x+y)^n을 전개 했을 때 xkyn−kx^ky^{n-k}의 계수 값을 구하는 정리
이항계수 : xkyn−kx^ky^{n-k}의 계수는 n개에서 k개를 고르는 조합의 가짓수인 nCknCk

파스칼의 삼각형(이항 계수의 응용)

이항 계수를 삼각형 모양의 기하학적 형태로 배열한 것
규칙

  • n번째 줄 : n개의 숫자
  • 각 줄 양 끝 : 숫자 1
  • 삼각형 내부 숫자 : 윗 양 대각선 숫자의 합

재귀호출을 이용한 이항계수의 계산 = 중복 호출 많음

n = 정수
k = n보다 같거나 작은 수

def bino(n,k):
	if k==0 or n==k:
		return 1
	else:
		return bino(n-1, k-1) + bino(n-1, k)

부분 문제의 의존성

B012...j
0(0,0)
1(1,0)(1,1)
2(2,0)(2,1)(2,2)
...
i??
  • 위 ?? 값을 구하기 위해서는 B[i−1,j−1],B[i−1,j]B[i-1, j-1], B[i-1,j]의 값을 알아야 함
  • 상향식 계산을 위해 의존성에 위배되지 않도록 구해나가야 함
  • 배열을 행 우선으로 탐색해야 함(----->)

동적 계획법을 이용한 이항계수의 계산 = O(nk)

def bino(n,k):
	B = [[] for _ in range(N)]
	for i in range(0,n):
		for j in range(0, min(i,k)):
			if j == 0 or j == i:
				B[i][j] = 1
			else:
				B[i][j] = B[i-1][j-1] + B[i-1][j]
	return B[n][k]
profile
timdalxx
Major in Computer Vision
이전 포스트

[알고리즘] 최단 거리/ 최소 비용 알고리즘

다음 포스트

[알고리즘] 문자열, 투포인터, 그리디(Greedy)

0개의 댓글

관련 채용 정보