본문 바로가기

공부/알고리즘

[알고리즘] 동적 계획법(dynamic programming) - 3

반응형

이번에는 경우의 수, 확률과 동적 계획법에 대해서 알아보겠습니다!

경우의 수나 확률의 경우에도 재귀적인 특징을 많이 가지고 있기 때문에 동적 계획법을 많이 이용합니다.


대표적으로, 이항 계수를 구하는 가 있습니다!


경우의 수를 세는 것도 이전의 최적 부분 구조를 이용합니다.

이전까지 어떤 경로로 왔던 상관없이, 현재 진행중인 부분부터 끝까지의 경우의 수를 센 뒤에 이 값을 반환하면,

이 반환된 값을 통해 더하든 곱하든 해서 처리하는 방식이 일반적인 경우의 수를 동적 계획법으로 풀어가는 방식입니다.


이 때, 다음 경로를 선택해야할 때 고려해야할 것이 2개 있습니다.


첫 번째는 모든 경로가 내가 선택하려고 하는 범위 내에 있어야 한다는 것이고,

두 번째는 어떤 경우더라도 내가 선택하려고하는 선택지에 두 번 포함되면 안된다는 것입니다!


만약 첫 번째 조건을 어긴다면, 생각보다 답이 작게 나올 것이고, 두 번쨰 경우를 어긴다면, 중복으로 세는 문제 때문에 답이 크게 나올 것입니다.


지금까지 배운 경우의 수 계산하는 방법을 단계적으로 나타내면 다음과 같습니다.


1. 우선, 완전탐색 알고리즘에 대해서 생각해봅니다. 이 때, 2 가지를 고려합니다.

a) 모든 경우는 이 선택지에 포함된다!

b) 어떤 경우도 두 개 이상의 선택지에 포함되지 않는다!


2. 이전 조각에서 사용한 요소들의 입력을 없애거나 줄여나가야 합니다. 그리고 다음 순서에서는 현재 남아있는 조각들을 고르는 경우만

   반환해야 합니다!


3. 이제 메모이제이션을 통해서 중복되는 부분을 제거합니다!






확률의 경우에는 '마르코프 연쇄'라는 이론이 사용될 때가 많습니다.


우선 마르코프 연쇄란, 유한 개의 상태가 있고, 이것이 시간에 따라서 변화하는 모델을 말합니다.

그리고, 현재 상태 a에서 미래 상태 b로 옮겨갈 확률은 현재 상태 a에만 좌우됩니다. a이전에 일어났던 어떤 과거 상황도 상태 b로 옮겨가는 데에는 영향을 주지 않는다는 것입니다. 

물론, 과거 상태가 현재 상태 a까지 오는데에는 영향을 주지만, 미래의 상황에는 영향을 주지 않습니다!


최적 부분 구조 처럼 a에서 부터 선택하고, 재귀함수를 이용해 b에서 반환된 값을 통해 적절한 처리를 해준 다음에 다시 그 값을 반환하는 형식이 일반적인 풀이 방식입니다!

그림은 위키피디아에서 가지고 왔습니다.


위를 예로 들면, 처음 상황이 E이고 3번 뒤에 A일 확률은


E - E * (E에서 2번 뒤에 A일 확률) = 0.3 * (E에서 2번 뒤에 A일 확률)

E - A * (A에서 2번 뒤에 A일 확률) = 0.7 * (A에서 2번 뒤에 A일 확률)


이렇게 두 가지의 경우로 나누어서 확인하는 방법으로 나눌 수 있습니다.

마찬가지로, E에서 2번 뒤에 A일 확률은


E - E * (E에서 1번 뒤에 A일 확률 = E - A) = 0.3 * 0.7 = 0.21

E - A * (A에서 1번 뒤에 A일 확률 = A - A) = 0.7 * 0.6 = 0.42

 

두 가지로 나뉘고, E에서 2번 뒤에 A일 확률은 0.63이 됩니다.


이런식으로 계산하면 A에서 2번 뒤에 A일 확률은 0.64가 됩니다.

결국, E에서 3번 뒤에 A일 확률은 0.3 * 0.63 + 0.7 * 0.64 = 0.637인 것 입니다!


설마.. 계산이 틀리진 않았겠죠? 계산이 틀렸다면.. 댓글로 알려주시기 바랍니다 ㅠㅠ


어쨌든, 오늘의 동적 계획법은 여기까지 하겠습니다!

반응형