본문 바로가기

공부/알고리즘

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

반응형

오랜만에 쓰는 알고리즘 글입니다!

요즘 뭔가 하고싶은 일이 많다보니 알고리즘을 조금 줄이게 됐네요!

종만북 1권도 도대체 언제 끝낼지 모르겠습니다 후덜덜;;


각설하고 이제 동적 계획법에 대해서 설명하겠습니다!


오늘은 정수 이외의 입력에 대해서 어떻게 메모이제이션을 할 것인가? 에 대해 알아보겠습니다!


지금까지는 메모이제이션에 사용되는 값이 정수였습니다!

하지만, 가끔씩 메모이제이션에 사용해야 하는 값이 문자열이거나 배열인 경우가 있습니다. 

이런 경우에는 어떻게 메모이제이션을 해야할까요!?


첫번째로는 STL의 힘을 빌리는 방법이 있습니다.

C++ STL에는 map과 vector라는 아주 훌륭한 stl이 있기 때문에 다음과 같이 메모이제이션을 사용할 수 있습니다.


map<vector<int>, int> memoi


STL의 컨테이너는 자체적인 대소 비교가 이미 만들어져 있기 때문에 아주 쉽게 메모이제이션을 사용할 수 있습니다. 다만, 시간이 아주 오래 걸리게 되죠.


두번째 방법으로는 일대일 대응 함수를 만드는 방법이 있습니다!

아마 가장 자주 쓰는 방법이 될 것입니다.

문자열이나 배열을 적절하게 정수로 변환할 수 있는 함수를 만드는 것이죠.


일대일 대응이 아니라면 어떤 문제가 발생할까요?


만약 두 개의 다른 입력의 반환 값이 같아진다면, 메모이제이션이 잘못된 값을 반환하기 때문에 이상한 값이 저장될 수도 있습니다.

그리고 어떤 배열 위치에 대응되는 입력이 없다면, 필요 없는 메모리 공간을 사용하게 됩니다.



부분 문자열의 경우에는 시작하는 인덱스와 끝나는 인덱스를 이용하여 일대일 대응 함수를 만드는 방법이 있습니다.


또 다른 경우는 어떤 경우가 있을까요?


입력의 값이 true와 false 두 개의 값으로 주어지는 경우를 생각해봅시다.

그렇게 되면, 각각의 인덱스를 이진수로 하여 데이터의 개수가 n개라면, 2^n의 표현으로 사용하는 방법이 있습니다.

대표적인 예로 경로를 만들 때 해당 배열을 선택했다 / 안선택했다 의 경우를 표현하는 경우입니다.


지수 함수이기 때문에 굉장히 시간 복잡도가 크다고 느껴지시겠지만, 문제가 팩토리얼의 시간 복잡도를 가진다면 이 방법을 사용하더라도 굉장히 큰 효과를 볼 수 있습니다!


보통 팩토리얼은 데이터가 12를 넘어가면 어마무시한 시간이 걸립니다!

2^n은 n이 20일때 까지는 사용할 수 있으니 팩토리얼을 최적화해야할 경우에는 한번 고려해 볼만 합니다.


위를 응용하면 만약 배열이 m개의 값으로 나타내는 경우에는 n 자리수를 가지는 m진수를 사용할 수 있습니다.


입력이 순열인 경우에도 일대일 대응 함수를 만들 수 있습니다.

해당 순열을 사전순으로 만들 경우, 몇 번째 위치에 있는지 만드는 방법입니다.




위와 같이 3412라는 순열의 순서를 알고 싶다고 가정합시다.

3보다 뒤에 있으면서 3보다 작은 수는 1과 2 2개 입니다.

그렇다면, 1XXX의 순열과 2XXX순열이 앞에 있었을 것입니다.

즉, 3XXX이전에 2 * 3! = 2 * 3 * 2 * 1 = 12개의 순열이 있었다는 것이죠!

이제 3XXX이전에 12개가 있다는 것을 알았으니

34XX는 몇번째 숫열인지 알아볼 시간입니다!

전과 마찬가지로 4다 작은 수들을 찾습니다.

마찬가지로 1과 2 2개입니다!

그렇다면 34XX이전에 31XX 가 2! = 2개, 32XX 순열이 있다는 것을 알 수 있습니다!

2 * 2! = 2 * 2 * 1= 4개 이군요!

1X 앞에는 아무 순열이 없습니다! 첫번인거죠!


그렇다면 3412는 12 + 4 = 16번째 순열이라는 것입니다!

한번 확인해 볼까요? 1234로 만들수 있는 순열을 사전식으로 나열해봅시다.


1234 - 0

1243 - 1

1324 - 2

1342 - 3

1423 - 4

1432 - 5


2134 - 6

2143 - 7

2314 - 8

2341 - 9

2413 - 10

2431 - 11


3124 - 12

3142 - 13

3214 - 14

3241 - 15

3412 - 16


정확하게 16이 나왔습니다!

이렇게 일대일 대응시키는 방법이 있죠!


오늘의 동적 게획법은 여기까지 입니다!


반응형