- 분할정복식 알고리즘은 top-down(하향식) 방법으로써 분할된 부분 간에 상관관계가 없는 문제를 해결하는데 적합하다.
- 피보나치 알고리즘과 같은 분할 부분이 서로 상관관계가 있는 경우 분할정복 방법은 적합하지 않다.
동적계획법 (Dynamic programming)
- 분할된 문제의 답을 도출한다.
- 인덱스를 효과적으로 설정하여 작은 문제들의 중복 해결을 배제한다.
- bottom-up(상향식) 방법
이항계수 구하기
분할정복식 접근방법
-
분할 정복식 방법으로 이항계수를 구하면 재귀적으로 호출하며 같은 계산을 반복해서 수행하기 때문에 효율이 낮다.
-
nCk를 구하기 위해서 이 알고리즘이 계산하는 항(term)의 개수는 2 × nCk - 1 이다.
동적계획식 접근 방법
- 재귀 관계식을 정립한다.
- 앞선 단계에서 구한 값을 이용하여 다음 단계의 값을 구하는데 이용한다. (pascal의 삼각형 이용)
pseudo code
분석
- 단위연산: for-j 루프 안의 문장
- 총 수행 횟수는 1 + 2 + 3 + ... + k + (k+1) * (n - k + 1)
그래프 용어
정점(vertex / node)
- 데이터를 표현
간선, 이음선(edge, arc)
- 정점을 연결한다.
- 방향 그래프에서는 arc, 비방향 그래프에서는 edge로 표현한다.
경로
- 각 정점에서 다음 정점을 잇는 이음선이 존재하는 일련의 정점들
단순 경로
- 같은 정점을 두번 지나지 않는 경로
순환
- 한 정점에서 다시 그 정점으로 돌아오는 경로
순환 그래프
- cycle을 포함하는 그래프
길이
- 경로상에 있는 가중치의 합 또는 경로상의 이음선의 개수
sparse graph
- node의 수가 edge수보다 많은 그래프 : node > edge
dense grapg
- node의 수보다 edge의 수가 많은 그래프 : node < edge
incident node
- 서로 edge로 직접적으로 연결된 node
adjacent edge
- 서로 인접한 node를 연결하는 edge
loop
- 하나의 edge가 하나의 node에 부속해 있을 때
최단 경로 문제 (all-pairs shortest paths problem)
brute-force algorithm
- 정점에서 다른 정점으로 가는 가능한 모든 경로의 길이를 구한 뒤 최소 길이의 경로를 찾는 무작정 알고리즘
- 상당히 비효율적인 알고리즘이다.
동적계획식 접근방법
-
그래프 adjacency matrix의 표현
-
그래프에서 최단 경로 길이의 표현
의 정점들만 이용하여 vi에서 vj로 가는 최단 경로의 길이를 표현한다.
-
설계 절차
-
경우 1은 {v1, v2, ... vk}의 정점들만을 통해서 vi에서 vj로 갈 때 최단 경로가 vk를 거치지 않는 경우
-
경우 2는 {v1, v2, ... vk}의 정점들만을 통해서 vi에서 vj로 갈 때 최단 경로가 vk를 거치는 경우
floyd 알고리즘 1
pseudo code
모든 경우를 고려한 분석
-
단위연산: for-j 루프안의 지정문
-
D[i][j] 계산시 D[i][k], D[k][j]의 값이 사용되기 때문에 앞선 단계에서 구한 D만을 이용하여 다음 단계의 값을 계산할 수 있다.
floyd 알고리즘 2
P[i][j]를 추가
- vi에서 vj까지 가는 최단경로의 중간에 놓여있는 정점이 최소한 하나라도 있는 경우에는 정점 중 가장 큰 인덱스를 가지는 값을 입력하고 하나의 정점도 없으면 0을 입력한다.
pseudo code
최단 경로 출력 pseudo code
최적의 원칙
- 어떤 해의 최적 해가 그 사례를 분할한 부분 사례에 대한 최적해를 항상 포함하고 있으면 그 문제는 최적의 원칙이 적용된다고 표현한다.
- 최적의 원칙이 적용 가능해야 동적 계획법을 사용할 수 있다.
- 최장 경로를 구하는 문제 등 최적의 원칙이 적용되지 않는 문제도 존재한다.
KHU, SWCON