티스토리 뷰

Dynamic Programming(동적 알고리즘)이란?

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

 

1.입력 크기가 작은 '부분 문제'들을 모두 해결

2.그 해들을 이용하여 보다 '큰 크기의 부분 문제'들을 해결

3.최종적으로 원래 주어진 입력의 문제를 해결.

 

Divide&Conquer(분할 정복 알고리즘) 방식과 구조적으로 유사하지만, 순서는 반대이다.

 

거기에 더해, 동적 계획 알고리즘은 B와 C의 해를 구하는 데 E와 F의 해 모두를 이용한다.

 

분할 정복 알고리즘의 경우,

D,E,F,G는 각각 더 이상 분할할 수 없는 부분 문제들이다.

D와 E의 해를 취합하여 B의 해를 구하고,

F와 G의 해를 취합하여 C의 해를 구하고,

B와 C의 해를 취합하여 A를 구한다...

 

동적 계획 알고리즘의 경우, 

먼저 최소 단위의 부분 문제 D, E, F, G의 해를 각각 구하고, 

D, E, F의 해를 이용하여 B의 해를 구한다.

E, F, G의 해를 이용하여 C의 해를 구한다.

B와 C의 해를 구하는데 있어 E와 F의 해 모두를 이용했다는 점에서 차이를 볼 수 있다.

 

 

동적 계획 알고리즘의 예시

 

1.모든 쌍 최단 경로 문제

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

 

A와 B 사이의 최단 경로를 찾는 문제가 있다. 그런데 그래프에서 둘이 이어지는 경로가 하나가 아니라, 다른 노드들에 의해 N개가 된다면? 컴퓨터는 모든 Path를 다 찾아서 비교하게 될 것이다. Time Complexity O(n^4)

 

-Idea

(1)그래프에 3개의 점이 있는 경우, 점 A에서 점 B까지의 최단 경로를 찾으려면, 2가지 경로, 즉 점 A에서 B로 직접 가는 경로 하나와, 점 1을 경유하는 경로 중에서 짧은 것을 선택하면 된다.(n번 반복)

(2) 그래프에 4개의 점이 있는 경우, A에서 B까지의 최단 경로를 찾을 때 직접 가는 경로 하나와, 점을 하나만 지나는 경로 n개와, 점 2개를 지나는 경로를 선택할 수 있다. 이 때, 점 2개를 지나는 경로의 경우 점 1개를 지나는 경로에 대한 연산과 겹치기 때문에, 반복 작업을 하지 않고 넘어간다. ->모든 경로를 여러 번 계산할 필요가 없다.

(3) 이 때, starting point와 destination을 고정해서 생각하지 말고, 그래프에 존재하는 점을 고정해서 생각하라.

그래프에 존재하는 점 하나에서, 다른 점까지의 최소 경로를 이차원 배열 형태로 출력할 수 있다.

그래프의 경로를 이차원 배열 형태로 출력하기

(4)그리고 존재하는 경로를 통해서, 정해지지 않은 경로의 거리를 구할 수 있다.

1->5로 가는 방법이 현재 존재하지 않지만, 2를 거치는 방법으로 거리 1만큼 걸려 갈 수 있다.

(5)이를 여러 번 반복해서 배열을 업데이트 해준다.

 

Dijkstra와 비슷한 느낌이 들기도 한다.

 

이처럼 문제 해결 과정에 반복 연산이 여러 번 있으면 동적 알고리즘이라 표현한다. 

피보나치 수열도 이와 같은 계열이다.

 

정리하면 위와 같다

 

 

-구현 방법

 

 

플로이드-워샬 알고리즘

-warshall은 그래프에서 모든 쌍의 '경로 존재 여부'를 찾아내는 동적 계획 알고리즘을 제안했다.

-Floyd는 이를 변형하여 모든 쌍의 '최단 경로'를 찾는 알고리즘을 고안했다.

-따라서 모든 쌍의 최단 경로를 찾는 동적 계획 알고리즘을 플로이드-워샬 알고리즘이라 한다.

-플로이드-워샬 알고리즘의 시간복잡도는 O(n^3)으로 다익스트라 알고리즘을 n번 사용할때의 시간복잡도와 동일하다.

-그러나 플로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적이다.

 

 

1.

A에서 B로 직접 가는 경로, A에서 점 1을 경유하여 B로 가는 경로가 있다.

B에서 C로 직접 가는 경로, B에서 점 1을 경유하여 C로 가는 경로가 있다.

이런 식으로 모든 쌍에 대하여, 직접 가는 경로와 1을 경유하는 경로를 비교한다. 

2.

그 다음엔 점 2를 경유하여 가는 거리와 비교한다. 

이때, 점 2는 1을 경유하는 경로를 거친다.

이런 식으로 모든 쌍에 대하여 두 개의 점을 경유하는 경로를 비교한다.

3.

n번 반복하여 가장 짧은 것을 고른다.

 

 

-수행 과정

배열 D를 만들어 갱신해 나간다.

그래프와 배열 D

 

 

위는 배열 D를 갱신하는 과정이다. 직접 가는 경로와, 점 1을 거쳐서 가는 경로 중에서 어떤 값이 더 작은지 비교하고, 갱신한다.

k를 1씩 증가시켜가며 n번 반복한다.

 

 

-시간복잡도

k n번반복

2차원 배열 D에 있어 행n번 반복, 열 n 번 반복 

총 n^3번 반복

O(n^3)

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함