1. Dynamic Programming(동적 계획법)

1. Dynamic Programming이란

문제를 풀기 위해서 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음 그것을 결합하여 최종적인 목적에 도달하는 것이다(Bottom-Up Approach). 각 하위 문제의 해결을 구한 뒤, 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 또 다시 계산하지 않고 간단하게 해겨할 수 있다. ^dp 즉 하나의 문제는 한번만 풀도록 하게 하는것.^dp2 [^DP]: 출처 : 위키 https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95 [^DP2]: 출처 : http://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221233570962&parentCategoryNo=&categoryNo=128&viewDate=&isShowPopularPosts=false&from=postView

2. 어디에서 사용할 수 있을까

• 큰 문제를 작은 문제로 나눌 수 있을때
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 경우

• 문제

  • 최단 경로 문제
  • 행렬의 제곱 문제 등의 최적화에 사용된다.

3. 동적 계획법이 왜 필요하지?

• 분할 정복을 이용하여 문제를 풀 때, 분할하여 풀지만 동일한 문제를 연속해서 풀어야 하기 때문에 효율이 좋지 않다. 동일한 문제를 한번만 풀게하고 효율을 높히기 위해 나옴.
• quick sort 또는 merge sort같은 경우엔 동일한 문제를 분할해서 풀지 않기 때문에 문제가 되지 않는다.
• 피보나치수열을 분할 정복을 사용하여 풀 경우에 subProblem으로 여러번 풀 경우가 생김.

• 출처 : http://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221233570962&parentCategoryNo=&categoryNo=128&viewDate=&isShowPopularPosts=false&from=postView

  • 위의 피보나치 문제에선 색깔이 있는 경우는 모두 동일한 계산을 하는 것을 나타냄.
• 이미 계산한 결과는 배열에 저장해 놓고 나중에 동일한 값을 계산하지 않도록 함.

4. 1차 동적 계획법

• 재귀식에서 1개의 변수가 필요한 문제
• 1차원 배열로 동적계획법 구현

• 문제

  • 피보나치
  • 2*N 직사각형 타일 채우기
  • 동전교환

5. 2차 동적계획법

• 재귀식에서 2개의 변수가 필요한 문제
• 2차원 배열로 동적 계획법 구현

• 문제

  • 이항 계수(binomial coefficient)
  • 동전 교환
  • 최장 공통 부분 수열

2. 5F

1.Fact

오늘은 동적 계획법에 대해서 공부를 시작했다. 사실 내일모래 시험이기도 하고, 코딩 테스트를 하는데 있어서 필요하기 때문에 공부를 하기 시작했다. Dynamic Programming 은 한번 계산한 것은 또 다시 계산하지 않기 위한 방법이다. 그래서 오늘은 1차 동적 계획법으로 피보나치, 2*n 타일, coin dp 문제를 공부해 봤는데 이해가 쉽지 않아서 다른 레퍼런스를 보면서 공부를 해봐야 겠다.

2. Feelings

이전에 동적 프로그래밍은 어려운 부분이라서 사실 공부하기 이전에는 장벽이 느껴졌는데, 실제로 공부를 해보니 그렇게 어려운 개념은 아닌것 같다. 이전에 알고리즘을 공부를 했을땐 정말 다 어려웠는데, 내 수준에 맞는 문제들을 여러번 풀어보고 익숙해지면서 어려웠던 부분도 쉽게 받아들일 수 있게 된것 같다. DP 예제를 보면서 이해를 하기는 쉽지는 않았지만, 더 접해보고 공부한다면 익숙해 질것이라고 생각한다.

3. Findings

학교에서 교수님이 배포한 유인물을 보고 공부를 시도 했는데 이해하기가 더 어렵고 쉽지 않은것 같다. 그래서 수형이형이 참고해서 공부할 수 있는 알고리즘 깃레포를 추천해 줬는데 그걸 보고 공부를 해봐야 겠다.

4. Future Action Plan

내일은 위에서 이야기한 레포의 내용을 보고 DI를 공부 해보려고 한다. 또 그곳엔 여러 자료구조 코드들도 있어서, 그 부분들은 매일 한두번씩 따라 쳐보면서 익히려고 한다.

5. Feedback