본문 바로가기

공부/알고리즘

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

반응형

오늘은 알고리즘 동적 계획법 4번째를 설명하도록 하겠습니다!

진짜 동적 계획법 엄~~~청 길어서 거의 10까지 할 것 같아요.


이번 동적 계획법에서는 k번째 답을 계산할때 쓰는 방법입니다!


예를 들면, 한 배열에서 LIS들은 한 가지 방법만 있는 것이 아닙니다.

가능한 LIS들을 사전순으로 나열한다고 할 때, k번째 LIS를 구하려면 어떻게 해야할까요?


우선, 사전순으로 개수를 세는 알고리즘을 만드는 경우를 생각해 봅시다.



1번째 답으로 올 수 있는 경우가 3개 있다고 합시다.

그럼, 경우 1에서 만들어 질 수 있는 수가 n1개 있을것이고,

경우 2에서 만들어질 수 있는 경우의 수가 n2개 있을 것 입니다.


하지만, 만약 경우 1에서 만들어질 수 있는 수가 k개 보다 작으면 어떨까요?

그럼, 경우 1의 경로를 보지 않아도 경우 1이 답이 될 수 없다는 것을 알 수 있습니다!

그렇다면 경우 1을 직접 세보지 않고 n1번을 스킵하면 됩니다.

그리고 바로 경우 2번을 보면 되는 것이죠!

한마디로, k에서 n1개를 뺀 다음에 2번째 경우를 보면 됩니다!



k에서 n1을 뺐었는데 n2보다 작으면 어떨까요? 

이 경우에는, 경우 2 를 고른 후에 만든 답 안에 k번째 답이 있다는 것을 알 수 있습니다!

그럼 1번을 경우 2번의 답으로 넣고 다시 1번 처럼 하는것을 반복하면 결국 답을 얻을 수 있습니다!




k번째 답을 계산하기 위해서 수행해야 하는 단계입니다.


1. 답들을 사전순서대로 만들며 경우의 수를 세는 완전 탐색 알고리즘을 설계합니다. 그리고 이것을 메모이제이션을 적용해서 동적계획 

   알고리즘으로 변환합니다.


2. 이제 모든 답들을 세는 경우의 수를 만들었으면, k번을 건너뛸 수 있다면 건너뛰어 가면서 k와 비교합니다.

1) 경우의 수가 k 보다 작다 : 

원하는 답이 이 안에는 없다는 것이므로 k에서 나온 경우의 수를 빼준 다음에 다음 경우의 수를 확인합니다.

2) 경우의 수가 k 보다 크다 : 

해당 경우 안에 원하는 답이 있기 때문에 이 경우를 선택하고, 재귀 호출로 나머지 부분을 만듭니다. 해당 경우에서 가장 처음에 만들 수 있는 값부터 k번 스킵한 값이 바로 원하는 값이 됩니다!


오늘은 여기까지 하겠습니다!

반응형