알고스팟 (algospot) 9장 동적계획법 테크닉

9.1 최적화 문제의 실제 답 계산하기

1. 재귀 호출의 각단계에서 최적해를 만들었던 선택을 배열에 저장후 비교 최신화
2. 별도의 재귀함수를 이용해 선택지를 저장 출력!

**예제)**최대증가 부분수열 실제로 출력하기-> LIS = 각원소가 이전 원소보다 크게 리스트를 구성한것중 가장 길이가 긴것

 

각 문제들

9.2 여행짐싸기

9.4 광학문자인식

 

 

9.6 k번째 답 계산하기

1. 모든 답들을 만들고 메모이제이션(물론 각 블록을 구분할수있다면 스킵하고 저장 가능)
2. k-1개를 스킵하고 답을 출력한다 ---> 최소최대값존재할수도있음 ex) 10000000000 이하임

예제) 모스부호사전-- 부호 만들어 찾기

 

각 문제들

9.7 k번째 최대 증가 부분수열

9.9 드래곤 커브

 

9.11 정수 이외의 입력에 대한 메모이제이션

-> 정수와 1 : 1 대응값으로 만들어계산!

1 ) 입력이 bool값 true —> 1 false —> 0 으로! —> 비트마스크

2 ) 입력이 순열? 묶어서 계산

3 ) 입력의 범위가 좁을 경우 —> 각 배열의 값이 한자리 정수라면? 그배열 자체를 하나의 정수형으로 생각(자릿수)

4 ) 특정 문자열들을 정수로 대응시켜서?

등등

 

예제) 6.7여행하는 외판원

       도시마다 방문여부 체크 → 비트마스크

 

각 문제들

9.12 웨브바짐-인플레이션 —>3 )

9.14실험데이터 복구하기  —> 만들수있는단어 모두 메모이제이션

 

 

9.16 조합게임

—> 게임트리그리기 —>모든 상태에대한 정보 기록? ㅇㅇ

 

예제) 틱택톡

비길경우 0, 이길경우 1, 질 경우 -1 로 반환하여 계산

 

각 문제들

9.17 숫자게임

9.19 블록게임

 

9.21 반복적 동적 계획법

—> 재귀가 아니라 단순 반복문을 통해서도 가능

 

1)슬라이딩 윈도? —> 사용하는 데이터 전체를 메모리에 유지하는것이 아니라 필요한 부분만저장

1. 행렬 거듭제곱? 선형변환형태의 점화식을 좀더 빠르고 쉽게 풀기 가능! ex)피보나치

예제) 8.4 삼각형 위의 최대경로

슬라이딩 윈도 일부분만 저장하여 for문 사용

 

 

재귀적 동적계획법

장점 : 좀더 직관적, 부분문제간의 계산순서 고민 x , 일부의 답만 필요할 경우 더 빠름

단점 : 슬라이딩 윈도 사용 x , 스택 오버플로 발생가능

 

 

반복적 동적 계획법

장점 : 구현이 쉬움, 재귀가 없어서 좀더빠름 , 슬라이딩 윈도 가능

단점 : 구현이 비직관적, 계산순서 고민 —> 생각좀 해야함

 

 

각 문제들

9.22 회전초밥

9.4 광학문자인식

9.26  읽어보기!