Dynamic programming

meeeeju·2022년 5월 14일
0

Algorithm

목록 보기
2/2

Dynamic programming 이란?

큰 문제를 작은 문제로 나눠서 푸는 알고리즘 이다 !

Dynamic(동적?) 은 아무 의미가 없다

비슷한 알고리즘으로 Divide and conquer(분할정복)가 있는데 차이점은 D.P는 중복이 있고 D&C 는 중복이 없다 라는 점이다.

📌 중복이 있다/없다는 것이 무슨 말인가?

큰 문제를 작은 문제로 나눠서 푸는 과정에서 똑같은 작은 문제가 자꾸 발생하는지,,?

핵심

  • Overlapping
  • Optimal Substructure
    • 큰 문제의 정답을 작은 문제의 정답에서 구하는 것이 가능하다.
      • 서울에서 부산을 가는 가장 빠른 길은 대전과 대구를 순서대로 거쳐야한다면 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야한다!
    • 한 문제의 정답은 항상 일정하다

📌  따라서 D.P 에서는 중복을 효율적으로 처리하는 것이 중요하다. 정답을 한번 구했으면 정답을 어딘가에 메모해놓자. 실제 코드에 구현할때는 배열에 저장해주면 된다. 이처럼 어딘가에 메모해놓는다고 해서 메모리제이션(memorization)이라고한다.


접근법

  1. top-down(recursion) Or bottom- up(iteration)으로 풀면 됨
    1. 두가지 접근 방식의 시간차이? 솔직히 알 수 없다. 때에 따라 다름
  2. 편한 방식으로 우선 연습 많이하자.
  3. 둘 중에 한가지로만 풀리는 문제가 있으면 그건 그럼 어떡해?
    1. 그건 그때까서 공부하면 됨 지금 신경 x (라고 백준쓰앵님께서 솔루션 주심,,)
profile
기록 '' 하장 ''

0개의 댓글