[코딩테스트 합격자 되기 스터디] 9주차 - 동적 계획법

✅ 동적 계획법

• 복잡한 문제를 단순한 하위 문제로 나눠서 접근하는 방법
• 중복 계산을 줄이기 위해, 이전에 구한 해를 활용함 (메모이제이션)

 

✅ 이전의 해를 활용해야 효율적인 문제의 조건

• 최적 부분 구조 (Optimal Substructure)
  • 문제의 최적 해결책이 하위 문제의 최적 해결책으로 부터 구성되는 경우
• 중복 부분 문제 (Overlapping Subproblems)
  • 동일한 하위 문제가 여러번 계산 됨

 

 

✅ 예시 1. 팩토리얼 - 동적 계획법으로 풀어도 효율 X

 

✅ 예시 2. 피보나치 수 - 동적 계획법으로 풀면 효율적

 

✅ 동적계획법을 문제에 적용하려면?

1. 예제 입력으로 출력 만드는 과정을 직접 손으로 작성
2. 과정을 일반화 한다. 이 때 최종해를 구하는 과정을, 이전해를 구하는 과정을 통해 나타낼 수 있는지 확인
3. 2번 과정에서 이전해를 구하는 과정이 중복되는 지 확인

 

✅ 예시 1 : 계단 오르기

• N개의 계단이 존재하고, 한 번에 1개 혹은 2개의 계단을 오를 수 있음. 계단을 오르는 방법의 총 수는?
• 적용
  1. 예제 입력으로 출력 만드는 과정을 직접 손으로 작성

 

2. 과정을 일반화 한다. 이 때 최종해를 구하는 과정을, 이전해를 구하는 과정을 통해 나타낼 수 있는지 확인

 

3. 2번 과정에서 이전해를 구하는 과정이 중복되는지 확인

 

✅ 정리

• 아래 두 조건을 만족하는 경우 동적계획법으로 접근하면 효율적
  • 중복부분구조
    • 현재 해를 구하기 위해 이전 해가 중복적으로 사용되는지 확인
  • 최적부분문제
    • 현재 해가 이전 해를 활용해서 해결할 수 있는지 확인
• 현재 해가 이전해를 활용해서 해결할 수 있지만, 이전해가 중복되지 않는 경우는 동적계획법으로 풀어도 효과가 없다.
  • 팩토리얼 (최적부분문제 O , 중복부분구조 X)
  • 피보나치 (최적부분문제 O , 중복부분구조 O)

---

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]

 

[참고 도서]

코딩테스트 합격자 되기 - 파이썬 편

[ https://www.yes24.com/Product/Goods/123272392 ]