알고리즘 #7_ 동적 프로그래밍: 동적 프로그래밍의 요소

안녕하세요.

우리는 지난 포스팅들을 통해서 동적 프로그래밍(Dynamic programming)의 3가지 예시에 대해 살펴보았습니다.

이번 포스팅에서는 예시들과 같은 최적화 문제에 동적 프로그래밍을 적용하기 위해 가져야 하는 두 가지 중요한 구성요소,

최적 부분 구조와 중복되는 부분 문제에 대해 살펴보도록 하겠습니다.

---

어떤 문제에 대해서 동적 프로그래밍을 적용하기 위해서 해당 문제가 가져야 할 두 가지 구성요소는,

최적 부분구조와 중복되는 부분 문제입니다. 하나씩 자세히 살펴보도록 하겠습니다.

1. 최적 부분 구조(Optimal substructure)

동적 프로그래밍을 적용하기 위해 가장 먼저 확인해야 할 것은 최적해의 구조의 특징입니다.

기본 문제의 최적해가 부분 문제의 최적해를 포함하고 있을 때, 우리는 그 문제가 최적 부분 구조를 가졌다고 할 수 있습니다.

어떤 문제가 최적 부분 구조를 가진다는 것은 동적 프로그래밍이 적용될 수 있다는 좋은 단서가 됩니다.

앞에서 알아보았던 것처럼, 동적 프로그래밍은 부분 문제의 최적해로부터 전체 문제의 최적해를 구하기 때문입니다.

우리는 아래와 같은 보편적인 방법을 통해 최적 부분 구조를 스스로 찾아볼 수 있습니다.

ㄱ. 문제에 대한 해는 선택하는 과정으로 만들어짐을 보여야 한다. 예를 들어, 막대에서 맨 처음 자르는 곳을 선택하거나 행렬 체인을 나눌 위치를 선택하는 과정을 포함하고 있다. 이런 선택을 하는 과정은 한 개 또는 그 이상의 풀어야 할 부분 문제를 남긴다. 즉, 선택을 통해서 한개 이상의 부분 문제를 만들어 낸다.

ㄴ. 주어진 문제에 대해서 최적해에 이를 수 있는 선택이 주어졌다고 가정한다. 이런 선택을 어떻게 결정하느냐는 아직 걱정하지 않는다. 단지 그 선택이 주어졌다고 가정한다.

ㄷ. 주어진 이 선택에 대해서 발생하는 부분 문제가 어떤 것인지를 정하고 그 부분 문제들의 범위를 가장 잘 표현할 수 있는 방법을 전한다.

ㄹ. 한 개의 최적해에 사용된 부분 문제들의 해가 최적이어야 함을 "잘라붙이기(cut and paste)" 방법을 이용해 보인다. 이것은 각 부분 문제들의 해가 최적이 아니라고 가정하고 모순임을 보이면 된다. 특히, 각 부분 문제들의 최적해가 아닌 부분을 "잘라내고(cutting)" 거기에 최적해를 "붙이면(paste)", 원래의 해보다 좋은 해를 얻게 된다. 따라서 잘라 붙이기 이전의 해가 최적해라는 가정에 모순이 되는 결론에 도달한다. 최적해에서 발생하는 부분 문제가 하나 이상이면 그 부분 문제들은 일반적으로 모두 비슷하므로 하나에 대해 적용한 잘라 붙이기 방법을 다른 부분 문제에도 쉽게 수정해 사용할 수 있다.

쉽게 말해서, 최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것입니다.

예를 들어, A라는 문제의 부분 문제 a,b가 있을 때, a,b의 최적해는 a',b'라고 가정한다면 A의 최적해는 a'와 b'로써 구성됩니다. 다시 말해, A라는 문제가 최적 부분 구조를 가지고 있는데 방금과 같은 조건에서 A의 최적해는 a'와 b'로 구성되는 것을 증명한다면, 최적 부분 구조를 가진다는 것을 언급하며 이로 인해 A의 최적해가 a'와 b'가 아닌 a'와 c'으로 구성된다고 가정한다면 b의 최적해는 c'이어야 하는데 b의 최적해는 b'이기 때문에 가정이 모순임을 보여 증명할 수 있습니다.

이때 문제가 최적 부분 구조를 가지고 있지 않음에도 최적 부분구조를 가지고 있다고 가정하지 않도록 주의해야 합니다.

예시를 통해 바로 확인해보도록 하겠습니다.

위의 그림에 대해 확인하기 앞서 아래 두가지 개념에 대해서 잠깐 설명드리겠습니다.

그래프에서 두 정점 a, b에 대해서,

(비가중)최단 경로: a에서 b까지 연결되는 가장 적은 개수의 간선들로 이루어 지는 경로입니다.

(비가중)최장 경로: a에서 b까지 연결되는 가장 많은 개수의 간선들로 이루어 지는 경로입니다.

또한 각각의 경로는 경로 내에서 순환이 포함되지 않는 단순(simple) 조건을 가지고 있으며 각 간선에 대해서는 가중치가 존재하지 않습니다.

그렇다면 위의 그래프를 보았을 때, q와 t사이의 최단 경로는 무엇일까요?

q -> r -> t 또는 q -> s -> t 입니다.

각각을 부분 문제로 나누어 보았을 때의 최적해는 어떻게 될까요?

q 와 r 사이의 최단경로는 q -> r 이며, r과 t사이의 최단경로는 r -> t 입니다.

이러한 것을 보아 최적 부분 구조를 가지고 있다고 알 수 있습니다.

하지만, 최장 경로에 대해서는 어떨까요?

q와 t사이의 최장 경로 또한 위와 같이 q -> r -> t 입니다.

그런데 그 부분 문제, q와 r사이의 최장 경로는 어떨까요?

q -> r이 아닌, q -> s -> t -> r 이 됩니다.

이러한 예는 최장 단순 경로를 찾는 문제가 최적 부분 구조를 가지지 않을 뿐만 아니라 부분 문제들의 최적해로부터 전체 문제의 조건에 맞는 해를 언제나 만들어 낼 수 있는 것은 아니라는 사실을 보여줍니다.

그렇다면, 최장 단순 경로의 부분 구조와 최단 경로의 부분 구조는 왜 다른 것일까요?

바로, 최장 경로를 찾는 문제의 부분 문제는 독립적(Independence)이지 않기 때문입니다.

여기서, 부분문제가 독립적이다라는 것은 어떤 것을 의미할까요?

독립적이다라는 것의 의미는, 동일한 문제에서 부분 문제 하나의 해가 다른 부분 문제의 해에 영향을 주지 못함입니다.

다시 말해, 위의 최장 단순 경로에서는 하나의 부분 문제를 풀기 위해 사용된 자원이 또 다른 부분 문제에서 사용되기 때문에 독립적이다라고 볼 수 있습니다. 그렇기에 최적 부분 구조 또한 아닙니다.

즉, 최적 부분 구조를 가지기 위해 부분 문제들은 독립성을 가져야합니다.

2. 중복되는 부분 문제(Overlapping subproblems)

동적 프로그래밍을 적용하기 위해 기본 문제가 가져야 할 구성요소 중 두번째입니다.

만약 재귀 알고리즘이 같은 문제를 계속해서 풀게 되는 경우 우리는 그 최적화 문제가 중복되는 부분 문제를 가진다고 말합니다. 반대로, 분학정복 기법을 사용하기에 적합한 문제는 보통 재귀적으로 호출하는 각 문제들이 새로운 것입니다.

동적 프로그래밍 알고리즘은 중복되는 부분 문제를 이용하는데, 각 부분 문제에 대해서 한 번만 계산하고 그 해를 테이블에 저장합니다. 그리고 그 부분 문제가 중복되어 나올 때 마다 상수 시간동안 테이블을 확인하여 해를 반환합니다.

이러한 해결방식 중에서 대표적인 것은 메모하기(memoize)입니다.

기본적인 아이디어는 자연스러우나 계속 되는 호출로 인해 비효율적인 재귀 알고리즘을 메모하는 방법으로써, 각 부분 문제들의 해를 저장하는 테이블을 가집니다. 맨 처음에 테이블의 각 엔트리들은 그 테이블이 아직 채워지지 않았다는 것을 나타내는 특정한 값을 가지고 있다가, 재귀 알고리즘을 수행하는 동안 부분 문제가 처음으로 호출되면 그 문제의 해를 계산하고 그 값을 테이블에 저장합니다. 그리고 이후 동일한 부분 문제가 호출되면 테이블에서 저장된 해를 반환합니다.

---

이렇게 해서 간단하게, 동적 프로그래밍의 요소 두 가지를 알아보았습니다.