[Inflearn] 네트워크 선 자르기(재귀, 메모이제이션 : Top-Down)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이전 문제와 같은 문제지만 다른 방법으로 다시 풀어보자.

이전 문제는 Bottom-Up 방식의 DP 를 적용하여 풀었다면,

반대인 Top-Down 방식으로 메모이제이션을 적용하여 풀어보자.

Top-Down 방식은 아래 그림과 같이 위에서 아래로 문제를 잘게 조각내면서 구한다.

D(7)를 구하기 위해서는 D(6)와 D(5)를 알아야하고, 

D(6)와 D(5)를 구하기 위해서는 D(5)와 D(4)와 ...

여기서 이미 구했던 값들이 중복되는 경우가 생기는데

이미 구한 값을 또 재귀함수를 호출하며 구하게 되면 굉장히 시간복잡도의 낭비가 생긴다.

그러므로 문제를 잘게 쪼개면서 구해진 값들을 table에 기록하여 재활용한다면 시간복잡도를 줄일 수 있다.

결론, 이미 구한 값을 기록해두고 불필요한 재귀호출을 방지하는 것이 Memoization

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

#include <cstdio>   int table[50];   int DFS(int n) {     if (table[n]) return table[n];     if (n == 1 || n == 2)         return n;     else         return table[n] = DFS(n - 2) + DFS(n - 1); }   int main(void) {     int N;     //freopen("input.txt", "rt", stdin);     scanf("%d", &N);       printf("%d\n", DFS(N));       return 0; } Colored by Color Scripter

cs

line 5~12) Memoization 동작을 수행하는 DFS 함수

line 7) table에 이전에 구한 해가 있다면 return 해준다. (이미 구했던 해를 재사용함으로써 시간복잡도를 굉장히 줄일 수 있다.

line 8) 직관적인 답인 n이 1 또는 2일 경우

line 11) return과 동시에 table에 결과값을 저장해준다.

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include<bits/stdc++.h> using namespace std;   int dy[50]; int DFS(int n){     if(dy[n]>0) return dy[n];     if(n==1 || n==2) return n;     else return dy[n]=DFS(n-1)+DFS(n-2); } int main(){     ios_base::sync_with_stdio(false);     freopen("input.txt", "rt", stdin);     int n;     cin>>n;     cout<<DFS(n);     return 0; } Colored by Color Scripter

cs

#. Result

  - Input --------------------------------------------------------

7

------------------------------------------------------------------

  - Output --------------------------------------------------------

21

------------------------------------------------------------------