공부하는 개발 블로그

경우의 수 계산하기
1. 완전탐색을 설계
  1) 모든 선택지를 포함
  2) 두 개 이상의 선택지에 포함되지 않음
2. 이전 조각에서 결정한 것들에 대한 입력을 없애거나 줄임. 남아 있는 조각들을 고르는 경우의 수만 반환
3. 메모이제이션

1. 완전탐색 방법을 생각한다

2. 전체 답이 아니라 앞으로 남은 부분문제에 대한 답을 반환하도록 수정한다.

3. 이전에 구한 답에서 필요한 정보만 남긴다. 입력을 최대한 줄여서 중복을 늘린다.(메모이제이션을 적용했을 때 효율 증가)

4. 메모이제이션

구조

1) 초기화

2) 기저 사례 처리

3) 이미 처리한 값인지 확인(초깃값인지 확인)

4) 계산

시간 복잡도 : 부분 문제의 수 * 부분 문제를 처리하는데 걸리는 시간

메모이제이션을 위해서는 *참조적 투명성* 필요.

함수의 입력값에만 의해서 값이 결정됨.

전역 변수 등의 영향을 받지 않음

비둘기 집의 원리

- 경로는 무수히 많을 수 있지만, 입력의 수는 경로보다 적은 경우, 메모이제이션이 유용할 수 있음

배열의 크기를 하나 더 키워서

첫번째 인덱스를 -1이나 0을 넣어서 예외상황/초깃값 처리를 쉽게 할 수 있다.

관련 문제 : 가장 긴 부분 증가 수열(구종만 p.234 nlog n 해법 다시 공부하기)

quad tree

p.244 quantization 
배열 A를 s개의 숫자로 양자화 
-> 오차의 합을 최소로할 때, 오차합 구하기 

1) 배열을 s개의 집합으로 나누고 
2) 각 집합에서 적정한 숫자를 찾아, 오차합 구하기 

1) s개의 집합을 구하기 : 부분 문제 
2) 적정한 숫자 : 평균, 오차합: 부분합 이용 


p.256 우물을 기어오르는 달팽이 

문제를 분할 할때: 
1) 모든 경우를 포함한다 
1) 두 경우에 동시에 포함되는 경우는 없다.

완전 탐색

기저 사례 작성 -> 반복 제거

dx, dy를 별도의 변수로 분리하자

중복 제거 : 순서를 강제하기