그리디 알고리즘(Greedy Algorithm) & 동적 계획법(Dynamic Programming)

 

그리디 알고리즘(Greedy Algorithm)

---

다음 단계를 생각하지 않고, 현재 단계에서 가장 최선을 선택하는 기법이다

조건

• 탐욕 선택 속성(Greedy Choice Property)
  • 이전의 선택이 이후에 영향을 주지 않음
• 최적 부분 구조(Optimal Substructure)
  • 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다

특징

• 전체 상황에서의 최적의 결과를 보장하지 못한다.
• 속도가 매우 빠르다
• 사용 예시 : 거스름돈, 활동 선택(Action Selection) 문제 등

 

 

동적 계획법(Dynamic Programming)

---

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용

조건

• 겹치는 부분 문제(Overlapping Subproblems)
  • 동일한 작은 문제들이 반복하여 나타나는 경우
    • 결과를 재활용하여 큰 문제를 해결한다.
• 최적 부분 구조(Optimal Substructure)
  • 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

특징

• 모든 가능성을 확인하므로, 최적의 결과를 보장한다.
• 사용 예시 : 피보나치 수열, 배낭 문제, 부분집합의 합, 최장 공통 부분 수열 등

방식

하향식 접근 방식(Top-Down Approach)

• Memoization 라고도 부른다.
• 재귀로 구현한다.

상향식 접근 방식(Bottom-Up Approach)

• Tabulation 라고도 부른다.
• 반복문으로 구현한다.

 

 

질문

---

Q. 그렇다면, 동적 계획법으로 풀 수 있는 모든 문제는 재귀로 변환하여 풀 수 있나요?

• 풀 수 있지만 Stack Overflow를 발생시킬 위험이 있다.
• 반대로, 모든 재귀 문제도 동적 계획법으로 풀 수 있다.

•