Dynamic Programming

DP = 다이나믹 프로그래밍

DP문제나 다이나믹 프로그래밍 과 같은 단어를 들었을 때, 너무 어렵게 느껴져서 알아보기 꺼려졌다.

그런데 요즘 기업 코테를 보거나 코테 사이트에서 레벨업을 하고 싶을 때 DP문제가 빠지질 않았다....

이제는 물러설 곳이 없기 때문에 빠른 시일 내에 DP에 대해 이해해보고 정복해보려고 한다.

 

다이나믹 프로그래밍이 먼데?

다이나믹이라는 단어를 듣자마자, 무언가가 엄청 막~ 화려하게 동작하게끔 코딩을 해야하는 줄 알았다.

하지만 그런 뜻이 아니라, 다이나믹 프로그래밍은 아래 한 문장으로 설명할 수 있을 것 같다.

메모리(배열or자료구조)를 사용해서 중복 연산을 줄이고(연산한 결과를 배열or자료구조에 담는다) 중복 연산을 줄여서 수행시간을 줄이자.

 

그래서 DP문제를 풀때는 아래 문장을 기억하고 접근하려고 한다.

"중간 계산 값을 어딘가에 저장 해놓자"

 

DP문제를 분류하는 방법!!

결론 부터 말하자면 아직 나한텐 명백한 기준은 없다. (24.11.10)

물론 있을 수 있다. 하지만 현재 나로서 이렇다할 기준을 못찾겠어서 알게되면 업데이트할 예정이다.

 

다른 영상이나 블로그 글들을 보면 어느정도 판단하는 기준은 있다고 한다.

•  DFS/BFS, 완전탐색으로 풀 수 있지만, 경우의 수가 너무 많은 경우(500depth 이상)
  • 이상적으로 DFS나 완전탐색으로 풀 수 있는 마지노선은 대충 500만 개 -> 5 x 10^6
  • 500만개 이상이라면 DP로 해결하는 방법을 생각해본다.
• 경우의 수들에 중복적인 연산이 많은 경우
• 다양한 문제들을 최적화 할 때 고려

그리고 재귀함수를 이용한 Top-Down 방식과 메모하는 것처럼 최적의 값을 저장해놓는 Bottom-Up방식이 있다고 하는데

나는 아직 재귀에 익숙하지 않기 때문에 대부분 Bottom-Up 방식처럼 풀 것 같다.

문제 해결 접근 방법

1. 직접 경우의 수를 따져가면서 패턴을 분석해보자. --> 점화식이든 다른 어떤 패턴이 나오는지 직접 손으로 써보기!

2. 문제를 많이 풀어보자 (30분 정도 도전 -> 정답 이해 -> 구현) --> DP식 사고방식을 습득해보자!

3. 어떻게 하면 뒤로 돌아가지 않을까? --> 어떻게 정보를 남길지, 누적할지 고민해보자!

 

마무리

DP는 큐나 스택 또는 특정 알고리즘처럼 정형화된 알고리즘이 아니라고 한다. 

수행시간을 단축하는 기법이기 때문에 방법은 끝도 없다고 하니깐 자신감을 가지고 최대한 많은 문제를 풀어보자!

 

---

 

현재까지 알게된 경우의 수들

 

(24.11.10)

1.  최소값을 알아야할 때 하나의 배열에 최솟값들을 미리 저장해기

2. 쉬운 경우의 수 3~5가지 정도로 패턴을 찾아 점화식이 가능한지 찾아보기

2-1. 경우의 수를 찾을 때 무작정 패턴을 그리는게 아니라 앞에서 그려봤던 그림과 패턴을 참고해서 다음 패턴을 찾아보자.