2019-12-10 TIL

이전에 공부한 DP에 대한 잘못된 이해가 있어서 오늘 다시 알게 되었다. 이전에는 DP를 하기 위해 top down 방식, bottom up 방식, memoization 방식이 있다고 생각했다. 3가지 방식이 아니라 2가지 방식이 존재한다. bottom up 방식과 top down 방식이 존재한다.

1. bottom-up 방식

   • 한 문제를 subproblem들로 나눈 가장 작은 문제들을 해결해 가면서 해결하는 방식이다. 이전의 분할 정복 방식에서는 top down 방식을 사용하여 동일한 연산을 여러번 해야하는 문제를 해결할 수 있다.
   • 밑의 코드와 그림을 보면 작은 것 부터 해결하여, 상위 문제들을 푸는데 이용함으로 연산을 최소화 한다.
   • 

2. top-down 방식

   • 이 방식은 분할 정복 문제를 해결하는 것과 유사하다. 하지만, 분할 정복으로 해결할 경우 특정 문제는 밑의 그림과 같이 동일한 연산을 무수히 많이 하게 되기 때문에, memoization을 사용하여, 해결한 문제를 배열 또는 테이블에 저장하여 모든 문제는 한번만 연산이 되도록 하는 방식이다.
   • 
   • 밑의 코드는 memoization을 이용한 top-down 방식으로 문제를 해결한 것이다.

   int inb(int n)
   {
       if (n==1 || n==2)
           return 1;
       else if(f[n] >-1)
           return f[n];
       else {
           f[n] = fib(n-2) + fib(n-1);
           return f[n];
       }
   }

1. 5F

1.Fact

동적 계획법에 대해서 잘못된 이해가 있었는데 공부를 계속 하면서 올바르게 이해할 수 있었다. 동적 계획법에는 크게 2가지 방법이 존재하고 한가지는 top down 방식 또 다른 방법은 bottom up 방식이다. 방식에 대한 자세한 설명은 위를 참고 하면된다. 그 이후에 알고리즘 스터디에 가서 카카오 블라인드 테스트에서 기출 문제인 실패율 문제를 짝프로그래밍으로 풀었는데 모두 풀지 못했다. 빠른 시일 내에 문제를 풀어 봐야겠다.

2. Feelings

같이 공부하는 모임에서 나혼자 알고리즘 이론에 대해서 공부를 하고 있다. 다른 멤버들은 주제가 비슷해서 짝프로그래밍을 하고 있는데 확실히 혼자 공부를 하니 효율이 많이 떨어지는것을 느낀다. 나보다 좀 더 알고 있건, 아니면 다른 사람과 같은것을 공부하면서 의견을 공유한다면 좀 더 효율적으로 공부를 할 수 있을것 같은데.. 역시 함께 하는것이 혼자 하는것이 나음을 이번에도 절실히 느낀다.

3. Findings

오늘은 마크다운 린트에 대해서 알게 되었다. 마크다운을 좀 더 문법에 맞게 작성해야겠다. 또 입사 코딩테스트에서는 DP나 그리디알고리즘을 이용한 효율성 문제는 기출율이 높지 않음을 알게되었다. 하지만 가끔씩 출제되는 문제이기 때문에 공부는 해둘 필요가 있다.

4. Future Action Plan

마크다운린트를 이용하여 문법에 맞게 작성하려고 노력 해야겠다. 그리고 공부를 하면서 잘안된다고 짜증 내기보다는 침착하게 어떻게 공부를 할지 계획을 세우고 하는 노력을 해야겠다.