[알고리즘] 동적계획법

Siri·2022년 10월 2일
0

TIL

목록 보기
2/3
post-custom-banner

동적 계획법의 원리와 구현 방식

  1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
  2. 작은 문제들이 반복돼 나타나고 사용되며, 이 작은 문제들의 결괏값은 항상 같아야 한다.
  3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 메모제이션(memoization) 기법이라고 한다.
  4. 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있다.

1. 동적 계획법으로 풀 수 있는지 확인하기

2. 점화식 세우기

3. 메모제이션 원리 이해하기

4. 톱-다운 구현 방식 이해하기

  • 위에서부터 문제를 파악해 내려오는 방식
  • 주로 재귀함수 형태로 구현
  • 코드의 가독성이 좋고 이해하기 편함

5. 바텀-업 구현 방식 이해하기

  • 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식
  • 주로 반복문의 형태로 구현

톱-다운 VS 바텀-업

  • 바텀-업이 좀 더 안전함
  • 톱-다운 방식은 재귀 깊이 깊어지면 런타임 에러 발생 가능

나의 생각

동적계획법 문제를 풀다 보면 바텀-업 방식으로 구현할 일이 많은 것 같다.
점화식을 세우는 것이 중요한 것 같다.
점화식을 잘 세우는 친구에게 점화식을 잘 세우는 방법을 물어봤었는데, 처음에는 하나 하나 숫자를 쓰면서 규칙을 찾아보라고 조언해줬다.


출처

Do it 알고리즘 코딩 테스트 파이썬 편

post-custom-banner

0개의 댓글