WEEK04 | DP

다이나믹 프로그래밍 - 동빈나

• 탑다운(topdown) vs 바텀업(bottomup) 탑다운 : 메모이제이션 방식, 하향식

  • 구현과정에서 재귀를 활용

  • 큰 문제를 위해 작은 문제를 재귀적으로 호출해서 해결하고 큰문제까지 해결되도록 코드를 작성

  • 한번 계산된 결과를 기록하기 위해 메모이제이션을 활용

  • 바텀업 : 상향식

  • 아래쪽에서부터 작은 문제를 하나씩 해결해나가면서

  • 먼저계산된 값을 활용해 다음 문제까지 차례대로 해결

  • 반복문을 이용

• 다이나믹의 전형적인 건 바텀업
• 이때 쓰는 결과저장용 리스트는 dp테이블이라고 부름

메모이제이션은 이전에 계산된 결과를 일시적으로 기록해놓는 넓은 개념
// dp랑 상관없이 넓은 의미의 용어임

문제를 접했을 때

이 문제를 해결하기 위한 아이디어로 어떤 알고리즘을 활용할 수 있는지

// 그리디, 구현, 완전탐색으로 풀수 있는지
// 다른걸로 안될거 같으면 그때 다이나믹을 생각해볼 것

작은 문제로 나뉘어지며 부분문제가 중복되는지

일단 재귀로 비효율적인 완탐을 쓰고 작은 문제에서 구한 답이 큰문제에 쓰일수 있다면

거기에 메모이제이션을 추가해서 코드를 개선시킬 수도 있음

보통 코테는 기본 유형의 난이도로 나올 확률이 높음
// 점화식을 떠올리는데 보통 오래걸리기도 하고
// 어려우려면 한도끝도없다...

피보나치수열

리스트사용(이런게 메모이제이션인가봐) < dp < 그냥 재귀

그래프 이론

서로소집합

union fine

사이클

크루스칼알고리즘

위상정렬