시행착오로 다져지는 프로그래밍 실력이지만, 동적계획법만큼은 다소 다른 접근법을 취하는게 맞다는 생각이 든다. PS를 하다보면 항상 동적계획법을 만나지만, 아무리 문제를 풀어도 풀이 방법을 익히지 못하고 있음을 매번 경험하기 때문이다. 구현에만 너무 집착한 나머지, 원칙을 경시하고 있는게 아닌가 싶어 조금씩 여러 블로그나 기사를 보면서 배운 내용을 정리해보려고 한다.
1. 동적 계획법을 사용할 수 있는 문제
-
최적 부분 구조(Optimal substructure)를 가져야 한다.
이전의 그리디 알고리즘에서 본 '문제의 최적 해결 방법은 부분 문제의 최적 해결 방법으로 구성된다' 와 완전히 동일한 개념이다. 생각해보면 이전부터 축적해왔던 계산을 기반 삼아 최적의 답을 내놓는 문제 풀이니 어느정도 일맥상통하는 면이 있다고 보여진다. -
1에서의 원칙에 따라, 점화식 형태의 수식으로 작성될 수 있는 문제여야 한다.
그렇지 못하다면 부분 문제를 정의할 수가 없는 문제이며, 따라서 점화식으로도 작성이 불가능하다.
2. 일반적인 접근론
예전에 공부한 기억에 따르면 Top-down 접근법과 Bottom-up 접근법이 존재한다고 알고 있다. 이 둘은 재귀로 구현하나, 아니면 배열을 활용해 반복문을 통해 구현하나로 다시 나뉘게 된다. 당연하지만 구현이 직관적인 것은 Top-down, 즉 재귀로 구현을 하는 것이나 프로그램 스택에 계속 함수가 쌓여가는 구조이므로 상황을 봐가면서 사용하는 것이 좋다.
하지만 지금은 걸음마 단계이므로 모든 문제를 Top-down으로 접근하고, 공간 복잡도에 문제가 생길 경우 Bottom-up으로 구현을 바꿔보는 방식으로 문제를 풀려고 한다.
Top-down 접근법의 가장 중요한 점은 문제를 거꾸로 해결 한다는 것이다. 미로 문제를 푼다고 하면 도착지점에서 출발지점이 어디인지를 찾는 것과 유사하다고 볼 수 있다.
미로 문제 풀이 영상
2배속으로 봐도 문제 없다. 영상 제작자가 육성으로 말하는 내용은 그렇게 영양가가 있진 않다.
동적 계획법은 다음 3가지 구성 요소로 이루어진다.
1. 단계
문제를 어떤 단계로 풀어나갈 것인가? 를 정한다. 컴퓨터는 한번에 하나의 값밖에 볼 수 없다. 그렇다면 어떤 값을 어느 순서로 검토할 것인지 단계를 정해야 한다.
2. 상태
단계를 구성하는 각 요소를 상태라고 한다. 프로그래밍에서는 부분 최적 구조에 근거해, 각 단계에서의 최적의 답을 상태값으로써 저장하게 된다.
3. 결정 변수
해당 상태에서 한정된 자원을 몇 개를 쓰는가? 에 대한 정보이다.
3. 문제 접근
아래와 같은 문제가 있다고 생각하자. 이하의 문제는 다른 블로그(출처)에서 가져온 것이다.
당신은 총 5개의 토큰을 갖고 있다. 이 5개의 토큰을 3개의 회사에 적절히 분배 투자해서 최대의 이득을 얻으려고 한다. 각 회사별로 투자한 토큰 대비 얻게 되는 이득은 다음과 같다.
위에서 본 것과 같이 단계와 상태, 결정 변수를 정해보자.
1. 단계
문제 풀이를 통해 얻은 직관이 있다면 명백히 단계는 회사1 -> 회사2 -> 회사3으로 정의되어야 한다고 볼 수 있다. 우리는 Top-down으로 문제를 풀 것이므로, 점화식은 회사3부터 파고 내려가야 한다.
2. 상태
각 단계를 이루는 구성 요소는 회사이다. 회사1의 상태는 즉 회사1에서의 최적의 답이 된다. 따라서 회사1의 상태는 토큰 2개를 투자하는 선택이 된다.
3. 결정 변수
해당 상태에서 총 몇 개의 토큰을 사용하는가? 가 된다. 즉, 결정 변수는 토큰이 된다.
문제 풀이는 다음과 같이 이루어 진다.
일반식
(현재 상태의 최대 이익) = (이전 상태의 최대 이익) + (현재 결정 변수로 얻는 이익)
이를 기반 삼아 회사1부터 최대 이익을 고려하면 다음과 같다.
회사3 최대 이익
(회사3 최대 이익) = (없음) + (회사3에 사용한 토큰으로 얻는 이익)
결론: 회사3에는 2개의 토큰을 투자해 90의 이득만을 얻는다.회사2 최대 이익
(회사2 최대 이익) = (회사3 최대 이익) + (회사2의 토큰으로 얻는 이익)
결론: 회사2에는 3개의 토큰을 투자해 총 190의 누적 이득을 얻는다.회사1 최대 이익
(회사1 최대 이익) = (회사2 최대 이익) + (회사1의 토큰으로 얻는 이익)
결론: 회사1에는 0개의 토큰을 쓰거나 2개의 토큰을 써서 최대 이익 190을 얻는다.
마지막 회사1 최대 이익에서 모순된 결론을 얻은 것처럼 보인다. 하지만 최적 부분 구조 문제임을 기억하자. 위 문제에서 190의 이익을 얻는 방법은 총 2가지이다.
- (회사1, 회사2, 회사3) = (0, 3, 2)
- (회사1, 회사2, 회사3) = (2, 1, 2)
4. 맺으며
프로그래머인 이상 구현을 해야한다. 내일 포스트에서는 이걸 구현 하는 방법을 써보고 싶다.
