[동적 계획법][비트 마스크][시도 x] RESTORE 실험 데이터 복구하기

1. 완전 탐색

 

이 문제는 먼저 문자열들이 주어졌을 때

모든 문자열이 어떤 문자열에

얼마나 곂칠 수 있는지 계산해야한다.

 

이 계산은 모든 문자열의 개수 n에 대하여

 

overap[A][B] = A다음으로 B가 왔을때 중복되는 것을 제외한 최소의 길이

 

에 저장되어진다.

 

이 배열의 초기는 A = -1일때 B는 자기 자신의 길이를 나타낸다.

 

이후 계산할 restore()함수에서 이것을 더하여 최소 값을 나타낸다

 

 

next는 모든 문자열을 가리키며, 이미 쓴 문자열일경우 패스한다.

 

restore(last, used) = min( overlap[last][next] + restore(next, used + (1<<next)) 

 

2. 동적 계획법

 

위에서 restore함수는 last 와 used에 따라 일대일 대응 함수가 되기 때문에 

메모이제이션이 가능해진다.

 

cache[last][used] = 이때까지 used의 문자열들을 사용했고 이전에 last를 선택했을때 최소값을 리턴

 

이를 통해 우리는 최소길이를 구할 수 있게된다.

 

이 정보를 토대로 또한 답을 O(n)만에 재구성할 수 있다.

 

restore(last, used) == restore(next, used + (1<<next)) + overlap[last][next] 

 

인 값을 따라가면 최적해를 재구성할 수 있다.

3. overlap 의미 변경

책에서는 overlap을 중복가능한 최대 값으로 설정하여 설명하였다

 

이런 정의를 통해 restore또한 최대값을 선택하는 것으로 함수를 수정하면

 

답을 구할 수 있게된다.

 

4. 코드 구현

 

16장의 비트마스크를 공부하고 나서 구현 해보도록 하자.

 

 

 

- 알고리즘 문제해결전략 332p

 

RESTORE