[알고리즘] 3. 동적 계획법 개념

동적 계획법 이란,

동적 계획법(Dynamic Programming), 
줄여서 DP는 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

조금 장난스럽게 말해서 답을 재활용하는거다. 앞에서 구했던 답을 뒤에서도 이용하는 것으로 볼 수있다.

(출처 : 나무위키 - 동적계획법
https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95?from=%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95)


이 말처럼 DP, 동적계획법은 완전 탐색에서 중복된 부분 문제를 한번만 계산 하기 위한

메모이제이션(Memoization)이다.

메모이제이션이란, 
같은 계산을 여러 번 해야 할 때, 한 번 계산한 결과를 메모리에 저장해 이후 동일한 계산 과정을 생략할 수 있게 하는 기법이다.

(출처 : 나무위키 - 메모이제이션)
 https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98)



보통 동적계획법 알고리즘 구현은,

1. 주어진 문제를 완전 탐색 이용 해결,

2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션 적용

두가지 방법으로 나뉜다.


이를 토대로 탐색을 통해 이전 값을 참고하는 것을 해 본다면,

[취업] 삼성 SW후기 포스팅의 문제를 동적계획법으로 설계 해 보려 한다.

일단 문제는, Player 비행기가 끝까지 도달하였을 때, 코인의 최대값이 문제다

(자세히는 포스팅을 참조...)

보통 완전탐색으로 모든 경우의 수 탐색을 통해 해결할 수 있지만,

크기가 커지면 탐색하는데 시간 초과가 발생한다.

이를 해결하기위해 동적계획법을 쓴다면,

좌표 (5,0)을 예로 들어, 여기에 비행기가 도달 하였을 경우,

이 시점에서 플레이어가 가진 코인의 가능성을 체크해 본다면, 2 혹은 1이 될 수 있다.

바로앞의 코인을 먹고 5,0에 도착하거나 5,0에 도착 한 상황 두가지로 들 수 있는데,

좌표마다 최대값을 메모이제이션 한다면, 어느정도의 중복을 제거 할 수 있다.

(어느 루트를 통해서 왓든, 5,0 에서 코인이 2 밑으로 나온다면 탐색을 종료해도 된다는 가정)




어느 루트를 통하든 5,0까지 왔다면,  2 미만의 값은 계산을 제외하면

어느 정도경우의 수를 제거 할 수 있다.


5,0에서 출발 하는 경우는

어느 루트를 통해서 왓든 동일 경로로 진행하기 때문이다.

이것이 '최대값'을 구하는 문제이기에

가능한 부분이라 생각한다.






하지만 문제는 '어느 시점'에서 좌표에 도달한 코인 값을 제외 할 것인가가 문제다

모든 좌표마다 도달한 코인 수를 계산할 것인지, 일정 좌표만 검사할지가 문제다.

이는 아직 생각할 부분이지만,

아마 모든 배열에 적용을 해야 할 듯 싶다.

그래야 동적계획법이 의미가 있을거 같은..

어쨋든, 완전 탐색을 통해, 중복을 제거하는 방법을 찾는것이 가장 중요하다.

추가로 읽으면 좋을 것