알고리즘 - Dynamic Programming(동적 계획법)

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

1. Dynamic Programming이란?

큰 문제를 작은 문제로 나누어 푸는 방식이다. 이러한 방법을 통해 한번 푼 문제를 여러번 푸는 비효율적인 방식을 개선시켜 하나의 문제는 단 한번만 풀도록 하는 알고리즘이다.

 

2. 그럼 어떤 상황에서 Dynamic Programming을 사용하나?

첫번째 조건 : 작은 문제를 여러번 반복한다.

두번째 조건 : 같은 문제는 구할때마다 정답이 반드시 같다.

 

3. 어떻게 사용하나?

첫번째 방법 : Bottom-up : 작은 문제부터 차근차근 구하는 방법

두번째 방법 : Top-down  : 큰 문제부터 해결하다 작은문제가 아직 해결이 안됐을 경우 그때 작은 문제를 해결하는 방법.

 

그러면 어느게 더 좋아?

모른다.

Bottom-up은 풀기 쉽다. 하지만, 가독성이 저하될 수 있다.

Top-down은 가동성이 좋다. 하지만 작성하기 힘들다.

 

문제별로 더 나은것 같은 방향으로 작성하면 된다. 그걸 모르겠으면 그냥 본인 편한대로 작성하면 된다. 

 

4. 핵심 기술 : Memoization(메모이제이션)

Dynamic Programming의 핵심이자 전부이다. 

값들을 저장하면서 한번 계산한 값을 더이상 계산하지 않아도 되게 하는 방법이다. 

 

5. Example

https://naemamdaelo.tistory.com/26

[Java] 백준 1463번 : 1로 만들기

동적 프로그래밍 방법을 사용하면 정말 알고리즘 문제 푸는데 편하다. 꼭 익히는 것을 추천한다.

 

-꿑-