알고리즘/동적계획법(DP)

동적계획법(DP)

동적계획법 (Dynamic Programming)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

최적화 문제를 해결하는 알고리즘

정의 :

어떤 문제가 반복적이고 최적 하위 구조로 이루어진다고 할 때, 하위 구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을구하는 방법

최적 하위 구조 란?

전체 문제의 답이 부분 문제의 답으로 부터 만들어지는 구조어떤 문제를 7개의 하위 문제로 나눌 수 있을 때, 7개의 하위 문제의 답을모두 얻어야 주어진 문제의 답을 구할 수 있다면 이 문제는 최적 하위 구조를갖추었다고 함.

분할정복의 해결 방식

• 문제를 큰 부분에서 작은 부분으로 나누어 전체 문제를 해결해 가는과정(top-down방식)
• 나눈 문제들을 완전히 새로운 하나의 독립된 문제
• 한번 풀이된 문제의 결과는 해당 문제를 해결한 이후에 소멸

동적계획법의 문제 해결 방식

• 작은 부분부터 큰 문제를 점차 해결해 올라가는 과정(bottom-top방식)
• 이전 단계의 답에 의존적이기 때문에 한번 풀이된 문제는다시 풀이되지 않도록 테이블 등에 저장 후 재사용

---

모든 쌍 최단 경로

• 각 쌍의 점 사이의 최단 경로를 찾는 문제

문제의 해결 방법

→ 시작점을 정하여 다익스트라의 최단경로알고리즘을 수행

이때의 시간복잡도는 O(n^3) n은 점의 수임.

D= distance임.

문제해결방법 1>

문제해결방법 2>

문제해결방법 3>

예시

다이렉트로 1→5로 가는 숫자가 없으면 <무한대>로 표기

다이렉트로 갈수 있다면 정수로 표기한다.

ppt에선 for문이 1로 나와있는데,0으로 수정해야한다.

#include<stdio.h>
#include <limits.h>
// 정점의 수를 지정한다.
#define V 5
// INF를 무한대라고 지정하고, INT_MAX를 이용한다.
#define INF 10000
// 플로이드 워셜의 결과를 출력하는 함수
void printSolution(int dist[][V]) {
	printf("Following matrix shows the shortest distances, between everypair of vertices \n\n");
		printf("\t to→ ");
	for (int i = 0; i < V; i++)
		printf("[%d] ", i);
	printf("\n ↓from \n");
	for (int i = 0; i < V; i++) {
		printf("\t[%d]", i);
		for (int j = 0; j < V; j++) {
			if (dist[i][j] == INF)
				printf("%7s", "INF");
			else
				printf("%7d", dist[i][j]);
		}
		printf("\n");
	}
}
void floydWarshall(int graph[][V]){
	int dist[V][V];
for (int i = 0; i < V; i++)
	for (int j = 0; j < V; j++)
		dist[i][j] = graph[i][j];
/* 플로이드 워셜 알고리즘의 핵심 */
for (int k = 0; k < V; k++) {
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			// i에서 j로 가는 기존 거리와 i에서 k를 거쳐 j로 가는 거리를 비교하여// 더 작은 값을 선택
			if (dist[i][k] + dist[k][j] < dist[i][j])
				dist[i][j] = dist[i][k] + dist[k][j];
		}
	}
}
// 모든 최단거리가 구해지고 난 뒤, 출력을 해준다.
printSolution(dist);
}
int main(void) {
	int graph[V][V] = {
	{ 0, 8, 4, 5, 5 },
	{ 7, 0, 6, 2, 2 },
	{ 3, 2, 0, 3, 7 },
	{ 7, 3, 7, 0, 1 },
	{ 3, 7, 4, 2, 0 },
	};
	// 플로이드 워셜 알고리즘으로 진입
	floydWarshall(graph);
}

---

벨만 포드 알고리즘

최단 경로 알고리즘

• 가중치를 갖는 방향성 그래프에서 최단 경로 문제를 풀기 위한 알고리즘
• 다익스트라 알고리즘과 같이 단일 시작점으로부터 각 정점에 이르는 최단 경로를 구함
• 최대 간선의 수는 정점의 수 -1
• 다익스트라 알고리즘보다는 시간이 오래 걸리나, 간선의 가중치가 음수일 때도 사용이 가능
• 음의 사이클 존재 여부 파악 가능

최단 경로 예시

→ 다익스트라알고리즘의 경우

S-E까지 가는 최단 경로의 값을 10

WHY> 음수는 고려하지 않음.

→ 벨만포드알고리즘의 경우

S-E까지 가는 최단 경로의 값 7

WHY > 가중치의 음수 가중치도 고려하기 때문

주의사항

→ 항상 무한대 사이클을 고려해야함. < 최단경로는 순환을 포함하면 절대 안됨 >

음의 가중치를 갖는 CYCLE이 있는경우 false를 리턴하게 만들어주어야함

S로부터 도달 가능한 지점으로의 최단 경로의 길이는 최대

V

-1이다.

시작점이 s, 목적지가 g인경우

s→ a → b → g : 문제 X

s → c → d → g : 문제 X

s → e → f → g : 문제 O

초기화 과정 : O(

V

)

O(

V

-1)*O(E)

시간복잡도 = O(

V

E

)

---

연속 행렬 곱셈 문제

→ 동적 계획법으로 해결되는 대표적인 문제

행렬 C의 1개의 원소를 위해서 행렬 A의 1개의 행에 있는 20개 원소와 행렬B의 1개의 열에 있는 20개의 원소를 각각 곱한값을 더해야함.

→ 행렬C의 1개 원소의 값을 구하기 위하여 20번의 곱셈이 필요함