이제 dynamic programming 챕터를 끝으로 LEETCODE에서 제공하는 모든 챕터를 둘러본것이된다. 아직 세부적으로 문제를 구현해 내는것은 연습이 부족하여 풀진 못하겠지만 전체적인 뿌리와 방향을 알 수 있게 된것같다. 이제 그 속을 세부적으로 단단히 다져나가야겠다.
오.. 다이나믹 프로그래밍은 문제 해결 테크닉의 한종류로 인터뷰에서 잘나오지않지만 만약 나오면 인터뷰어에게 가장 공포스러운? 문항이라고한다. 근데 알기만하면 겁먹을 필요가 없다고함 :(..
what is DP?
짧게 설명하면 다이나믹 프로그래밍은 단지 최적화된 회귀 문제라고한다. recursive function 에서 argument 로 들어가는것이 State 라 불리며 예를 들어 DFS 문제에서는 방문했던곳을 다시 가지않도록 State를 만드는것이 있다. 허나 Dp 에서는 state 는 다시 반복될 수 있으며 이문제를 해결하기 위해 memoization 이라는 방법을 사용한다.( 간곳을 cash화해서 기억하는 방법으로 보통 hash map이 이 역할을 한다.) 후에 만약 재방문하게된다면 cash 값이 쓰이게되서 다시 계산되는것을 방지한다고한다. (방문은되나 hash map의 검색속도가 빠른것을 이용해 바로 리턴해주는 느낌).
대표적인 예제로 피보나치 수열이 있다.
int fibonacci(int n) {
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}위에서 작성된 대표 recursive 기능으로 되면 O(2^n)이 되면서 무지막하게 computation이 증가하게된다. 이때 다시 반복되며 계산되는것을 방지하기 위해 memoization (메모이제이션) 추가하면,
unordered_map<int, int> memo;
int fibonacci(int n) {
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
if (memo.find(n) != memo.end()) {
return memo[n];
}
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}이렇게 되면 시간복잡도는 O(n)이 되면서 기존 알고리즘을 최적화 할 수 있다! (hash 에서 find()는 O(n)의 시간복잡도)
When should I consider using DP?
일단 다양한 문제를 많이 접해봐야하겠지만 우선
- The problem will be asking for an optimal value (max or min) of something, or the number of ways to do something.
- What is the minimum cost of doing ...
- What is the maximum profit of ...
- How many ways are there to ...
- What is the longest possible ...
- At each step, you need to make a "decision", and decisions affect future decisions.
- A decision could be picking between two elements
- Decisions affecting future decisions could be something like "if you take this element, then you can't take that element in the future
요런게 있다고 한다.
Top down vs bottom up
DP 문제를 접근하는 법은 탑 다운 방법과 바텀 업 방법이있는데 첫번쨰 탑다운은 위에서 봤던 메모이제이셔을 사용해 위에서부터 아래로 접근하는 방식으로 두번째 바텀업은 아래에서부터 위로 올라간다고하여 Array를 사용해서 구성된다.
int fibonacci(int n) {
vector<int> arr(n + 1);
// base case - the second Fibonacci number is 1
arr[2] = 1;
for (int i = 3; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}위에 코드가 bottom up 방식으로 다른 용어로는 "tabulation" 해석하면 "도표" 라고하는데 왜 이 이름이 붙었는지는...
두개 방식의 특징이있는데
- 보통 바텀업 이 작동시간이 더 빠르다고한다
- 탑다운 방식이 코드 작성하기가 쉽고 보통 많이 사용하는 방식이라함.
댓글