[방송대 알고리즘]동적 프로그래밍

※ 방송대 교재의 예제를 참고하여 작성하였습니다. 디테일한 내용은 교재를 참고 바랍니다.

동적 프로그래밍

상향식 접근 방법으로 소문제를 이용하여 보다 큰 크기의 문제를 해결하는 방법

동적 프로그래밍 방법을 적용하려면 최적성의 원리를 적용해야함

최적성의 원리: 주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다.

피보나치 수

동적 프로그래밍을 이용하면 O(n)

연쇄 행렬 곱셈 문제

행렬의 곱셈에 결합법칙이 성립됩을 이용

n개의 행렬을 곱하는 최적의 순서는

n개의 행렬의 어떤 부분집합을 곱하는 최적의 순서를 포함

C(i,j) → i,j 범위 내의 최소의 코스트

크기가 nxm 인 행렬과 mxk인 행렬을 곱하면 필요한 연산 수는 nmk 이다!

P(i,j) → 최적의 곱셈 순서를 알기 위한 2차원 배열로, 해당 값은 i 부터 j까지의 행렬을 곱할때 쪼개지는 위치를 의미

O(n^3) = O(n(n-1)(n+1)/6)

정리

문제의 크기가 작은 소문제에 대한 해를 테이블에 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법

• 소문제들이 서로 독립일 필요는 없음
• 최적성의 원리를 만족하는 문제에 대해서만 적용 가능

스트링 편집거리

두 문자열 X와 Y사이의 편집거리

• 두 문자열 사이의 근접성 또는 유사성을 판단하는 척도
• 문자열 X를 Y로 변환하는 데 필요한 전체 편집 연산에 대한 최소 비용
• 새로운 문자를 삽입하는 연산 e_i
• 문자를 삭제하는 연산 e_d
• 특정 위치의 문자를 다른 문자로 변경하는 연산 e_c

최적성의 원리

X와 Y사이의 편집 거리는 이들의 부분 문자열 사이의 편집 거리를 포함

X의 마지막 글자가 삭제된 경우

Y의 마지막 글자가 삽입된 경우

→ 3개의 케이스가 그대로 점화식으로 이용됨

점화식

E(i,j) = min[E(i-1, j) + e_d, E(i, j-1) + e_i, E(i-1, j-1) + (0 or e_c)]

성능 분석

O(nm)

특징

P(i,j)란 배열을 만들어 선택되는 최솟값들이 어떤 연산으로 결정되는지를 표시할 수 있음

→ 적용된 편집 연산을 구할 수 있음

모든 정점 간의 최단 경로

두 정점 간의 최단 경로

• 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로
• 유형
• 단일 출발점 최단 경로 → 하나의 특정 정점에서 다른 모든 정점으로의 최단 경로(다익스트라)
• 모든 정점 간의 최단 경로 → 모든 조합의 두 정점 간의 최단 경로(플로이드)

플로이드 알고리즘

• 동적 프로그래밍 방법 적용
• 가정 → 가중치의 합이 음수인 사이클이 존재하지 않음
• 경유할 수 있는 정점의 범위가 1인 경로부터 시작해서 |V|까지인 경로까지 하나씩 범위를 늘려 가면서 모든 정점 간의 최단 경로를 한꺼번에 구하는 알고리즘
• 인접 행렬을 통하여 그래프를 표현

점화식

d_ij = min(d_ij, d_ik, d_kj)

i에서 j까지의 최단경로는, i에서 j로 바로 가는 경로와 i에서 k를 거치고 j로 가는 경로 중 작은 값

성능

V^3

저울 문제

• 양팔 저울, n개의 추, 각 추의 무게 w_i
• 무게 M인 물체를 양팔 저울로 달 수 있는지 확인하는 문제

가정 → 추의 무게 w_i와 물체의 무게 M은 모두 정수

최적성의 원리

n개의 추로 무게 M인 물체를 확인하는 문제

→ k개의 추가 선택 → M = w_s1 + ... + w_sk

선택된 추에 n번 추가 포함되지 않는다면

• 1~n-1 번까지의 추를 이용하여 무게 M인 물체를 달 수 있는지의 문제

선택된 추에 n번 추가 포함된다면

• 1~n-1 번까지의 추를 이용하여 무게 M-w_sk 인 물체를 달 수 있는 문제

점화식

S(i, k) = max[S(i-1, K), S(i-1, k-w_i)]

성능 분석

O(nm)

특징

• 무게 k의 증가를 추의 무게의 최대공약수 단위로 증가시키면 더 효율적
• 테이블 S와 w_i를 이용하면 사용된 추를 구할 수 있음
• 물체의 무게가 2^n보다 크면 모든 경우를 따져 보는 직관적인 방법보다 비효율적
• M과 w_i가 정수가 아니면 동적 프로그래밍 방법 적용 불가 → 되추적 알고리즘(8장)으로 해결

동적 프로그래밍

상향식 접근 방법으로 소문제를 이용하여 보다 큰 크기의 문제를 해결하는 방법

동적 프로그래밍 방법을 적용하려면 최적성의 원리를 적용해야함

최적성의 원리: 주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다.

피보나치 수

동적 프로그래밍을 이용하면 O(n)

연쇄 행렬 곱셈 문제

행렬의 곱셈에 결합법칙이 성립됩을 이용

n개의 행렬을 곱하는 최적의 순서는

n개의 행렬의 어떤 부분집합을 곱하는 최적의 순서를 포함

C(i,j) → i,j 범위 내의 최소의 코스트

크기가 nxm 인 행렬과 mxk인 행렬을 곱하면 필요한 연산 수는 nmk 이다!

P(i,j) → 최적의 곱셈 순서를 알기 위한 2차원 배열로, 해당 값은 i 부터 j까지의 행렬을 곱할때 쪼개지는 위치를 의미

O(n^3) = O(n(n-1)(n+1)/6)

정리

문제의 크기가 작은 소문제에 대한 해를 테이블에 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법

• 소문제들이 서로 독립일 필요는 없음
• 최적성의 원리를 만족하는 문제에 대해서만 적용 가능

스트링 편집거리

두 문자열 X와 Y사이의 편집거리

• 두 문자열 사이의 근접성 또는 유사성을 판단하는 척도
• 문자열 X를 Y로 변환하는 데 필요한 전체 편집 연산에 대한 최소 비용
• 새로운 문자를 삽입하는 연산 e_i
• 문자를 삭제하는 연산 e_d
• 특정 위치의 문자를 다른 문자로 변경하는 연산 e_c

최적성의 원리

X와 Y사이의 편집 거리는 이들의 부분 문자열 사이의 편집 거리를 포함

X의 마지막 글자가 삭제된 경우

Y의 마지막 글자가 삽입된 경우

→ 3개의 케이스가 그대로 점화식으로 이용됨

점화식

E(i,j) = min[E(i-1, j) + e_d, E(i, j-1) + e_i, E(i-1, j-1) + (0 or e_c)]

성능 분석

O(nm)

특징

P(i,j)란 배열을 만들어 선택되는 최솟값들이 어떤 연산으로 결정되는지를 표시할 수 있음

→ 적용된 편집 연산을 구할 수 있음

모든 정점 간의 최단 경로

두 정점 간의 최단 경로

• 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로
• 유형
• 단일 출발점 최단 경로 → 하나의 특정 정점에서 다른 모든 정점으로의 최단 경로(다익스트라)
• 모든 정점 간의 최단 경로 → 모든 조합의 두 정점 간의 최단 경로(플로이드)

플로이드 알고리즘

• 동적 프로그래밍 방법 적용
• 가정 → 가중치의 합이 음수인 사이클이 존재하지 않음
• 경유할 수 있는 정점의 범위가 1인 경로부터 시작해서 |V|까지인 경로까지 하나씩 범위를 늘려 가면서 모든 정점 간의 최단 경로를 한꺼번에 구하는 알고리즘
• 인접 행렬을 통하여 그래프를 표현

점화식

d_ij = min(d_ij, d_ik, d_kj)

i에서 j까지의 최단경로는, i에서 j로 바로 가는 경로와 i에서 k를 거치고 j로 가는 경로 중 작은 값

성능

V^3

저울 문제

• 양팔 저울, n개의 추, 각 추의 무게 w_i
• 무게 M인 물체를 양팔 저울로 달 수 있는지 확인하는 문제

가정 → 추의 무게 w_i와 물체의 무게 M은 모두 정수

최적성의 원리

n개의 추로 무게 M인 물체를 확인하는 문제

→ k개의 추가 선택 → M = w_s1 + ... + w_sk

선택된 추에 n번 추가 포함되지 않는다면

• 1~n-1 번까지의 추를 이용하여 무게 M인 물체를 달 수 있는지의 문제

선택된 추에 n번 추가 포함된다면

• 1~n-1 번까지의 추를 이용하여 무게 M-w_sk 인 물체를 달 수 있는 문제

점화식

S(i, k) = max[S(i-1, K), S(i-1, k-w_i)]

성능 분석

O(nm)

특징

• 무게 k의 증가를 추의 무게의 최대공약수 단위로 증가시키면 더 효율적
• 테이블 S와 w_i를 이용하면 사용된 추를 구할 수 있음
• 물체의 무게가 2^n보다 크면 모든 경우를 따져 보는 직관적인 방법보다 비효율적
• M과 w_i가 정수가 아니면 동적 프로그래밍 방법 적용 불가 → 되추적 알고리즘(8장)으로 해결

 

참고 문제

 

• 피보나치 수 2 - 2748 :: 정답
• 행렬 곱셈 순서 - 11049 :: 정답
• 최소 편집 - 15483 :: 정답
• 플로이드 - 11404 :: 정답
• 양팔 저울 - 2629 :: 정답