Brute Force vs Dynamic Programming

BOJ 1149 - RGB거리 를 최소 cost 하나만 찾아서 답을 찾는 방식으로 고민하다가, 

문제가 안풀려서 결국 주어진 세 cost 마다 각각 최소합을 찾는 Bottom-up DP로 풀이를 바꾸었다.

여기서, '모든 경우의 수를 다 탐색한다는 점' 에서 Brute-Force와 DP 사이에 유사한 점이 있지 않을까 하는 생각에 관련 글을 찾아보았다.

 

• Brute Force - 모든 경우의 수 무식하게 일일히 탐색; 
• DP - 큰 문제를 작은 문제로 나눔 + 문제 한번 계산할때 '최적의 답'을 찾아 저장 (memoization);
  최적의 답을 찾기 위해선 해당 (작은)문제에서의 모든 경우의 수를 고려해야 함.

 

출저 : kyounju.tistory.com/2

1. Brute Force(완전탐색)

Brute Force의 이름을 살펴보자면, Brute는 짐승을 의미한다. 일반적으로 짐승은 본능에 의지해 '무식함'을 나타낸다. 그렇다면 여기서 '무식함'은 무엇일까? 그것은 모든 경우의 수를 찾아보는 것이다. 아주 간단한 예로 1 ~ 100가지 숫자 중에서 원하는 숫자 하나를 찾아본다고 하자! 100을 찾고 싶다면, 1부터 쭉 조사해서 100번을 찾을 때까지 반복한다. 이런 알고리즘적 '무식함'을 Brute라고 표현한 것이다.
가장 유명한 문제로 '외판원 순회'라는 문제가 있다. 1,2,3,4,5라는 노드가 있고 모든 노드를 1번씩 방문하고 출발했던 노드로 되돌아 오는 최소의 경로를 찾는 문제이다. 아래와 같은 그래프가 있다고 생각해보고 풀어보자!

 

외판원 문제 예

edge에는 임의의 weight가 있다고 가정한다. Brute Force는 모든 경우의 수를 다 계산해본다. 1->2->4->5->3->1을 방문했을 때, w의 합을 구한다. 또, 3->5->1->2->4->3도 가능하다. w의 합을 계산해 이전에 구한 w와 최소인 것을 저장한다. 이런식으로 조건과 맞는 모든 경우의 수를 계산해서 최소값을 구하는 것이다. 경우의 수는 몇개나 될까? 처음에 노드를 선택하는 개수 5개, 그 다음은 선택한 노드 외의 다른 노드 4개, 그 다음은 3개 따라서 5!이다. 여기서 더 줄일 수 있는 방법은 없을까? 당연히 존재한다. 만약 최소경로를 찾았다고 해보자!

 

최소 경로

위의 그림처럼 만약 1->2->4->5->3->1이 최소경로라고 할 때 1번부터 출발하는 w의 합과 나머지 2~5번부터 출발했을 때의 w의 합은 같다. 따라서 어느지점부터 시작하던지 최소값은 똑같다. 모든 경우의 수가 4!로 줄어들게 된다. Brute Force(완전 탐색)는 Time Complexity가 많이 소요되기 때문에 제외시킬 수 있는 경우의 수가 없는지 조사하는 것이 중요하다.
사실 문제를 풀 때 반복문(for, while 등..)을 많이 떠올리지만 구조적으로 풀 수있다. 자료구조의 Graph, Tree를 들여다보면 Graph의 모든 노드를 방문하는 방법은 대표적으로 BFS, DFS가 있을 것이고 Tree는 Inorder, Preorder, Postorder, Level Traverse방법이 있을 것이다. 내가 문제를 어떻게 생각하느냐에 따라서 쓸 수 있는 알고리즘은 많다.

 

2. Dynamic Programming(동적 프로그래밍)

Dynamic Programming일명 DP라 불리는 알고리즘은 Brute Force를 개선시킬 수 있다. Brute Force와 DP의 큰 차이점 중 하나는 어떤 경로나 수를 탐색했을 때의 값을 저장해주는 공간이 존재한다.

int dp[];

왜 이 공간이 필요할까? 이미 찾은 경로를 다시 탐색 하지 않기 위함이다.위의 외판원 문제로 돌아가보자! 1번에서 출발하여 3번 노드를 방문했다고 가정하자! 3번 노드를 방문 한 후 5번 노드를 방문 하거나 4번 노드를 방문했다가 5번 노드를 방문 할 수도 있을 것이다. 이 3가지 경우의 수 중 가장 짧은 w의 값을 dp공간에 저장해 놓는 것이다! 그렇다면 나중에 탐색을 하다가 또 3번에 방문을 한다면 다시 연산할 필요없이 계산된 값을 그대로 반환만 해주면 된다. 그래서 Brute Force보다 훨씬 빠르게 동작한다. 다시 연산 할 필요가 없다는 것은 1번을 방문하고 3번을 방문한 경우의 3번에서 찾을 수 있는 모든 경우의 수를 다 고려한 다음에 dp배열 공간에 저장해야한다. 만약 3번 노드를 방문했을 때 3번 노드에서 5번 노드로 방문한 경우의 수를 고려하지 못했다면 문제에 따라 2번 노드에 방문한 경우의 수가 더 짧을 수 있으므로 최소 값을 반환하지 못 할 수도 있다. 그래서 공간을 정의할 때 모든 경우의 수를 다 포함 할 수 있도록 공간을 정의해야 한다.

int dp[MAX][MAX];

외판원 문제는 이 같이 정의를 하면된다. 이 문제에서는 2차원으로 정의하였지만 문제에 따라 3차원 4차원이 될 수도 있다. 이 공간을 크기는 어떻게 정하면 좋을까? 가장 좋은 방법은 점화식이다. 함수 Traverse( 현재 노드, 다음 노드 )는 방문 노드의 최소값을 반환하는 함수라고 가정할 때 3번에서 4번 노드로 가는 방법과 3번에서 5번 노드로 가는 방법중의 최소값을 찾아야 한다. 따라서 점화식은 아래와 같다. w는 3번노드에서 인접노드로 가는 weight를 의미한다.
$$ dp[3][4] = min(Traverse(3, 4) + w, Traverse(3, 5) + w) $$
점화식을 보면 알겠지만 2차원 배열로 해결 할 수 있다는 것을 의미한다. 그래서 점화식을 잘 세울 수 있는 연습이 필요하다.