[알고리즘 전략] 탐욕법(Greedy)/ DP(동적 계획법)

※ 구글링하면서 재구성한 내용입니다. 세상 모든 개발자 블로그 만만세

※ 계속 공부하면서 내용 채울 것임. 

📌 탐욕법 (Greedy Algorithm)

⭐ 푸는 방법 
1. 일단 완전 탐색을 고민해본다. 제한시간/메모리 초과되는지 확인한다. 
2. 문제에서 규칙성을 찾으면 풀 수 있는 편이다. 
3. 아이디어를 떠올리고, 반레가 있는지 따져보면 된다. 

•  ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘

💡 각각 상황에서 '최적'이라고 생각하는 방법을 선택한다.(상황에서 가장 높은 수를 선택합니다.)

위의 경우 최댓값을 만들기 위한 탐욕법 알고리즘이 적용된 순서

 

그리디 알고리즘을 적용하기 위해서는 아래 2가지 속성을 만족해야 한다고 한다. 

 

1. 탐욕 선택 속성(Greedy Choice Property) 이란?
   • 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말합니다. 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것입니다.
2. 최적 부분 구조(Optimal Substructure) 란?
   • 전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우를 말합니다. 즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미합니다.

 

📌 동적 계획법 (DP: Dynamic Programming)  

• 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘
• 일반적으로 재귀적으로 구현되며 메모이제이션(Memoization) 기법을 사용하여 중복 계산을 피합니다.

 

>> DP 푸는 방법 1

1. 문제를 하위 문제로 쪼갭니다.
2. 하위 문제를 재귀적으로 해결합니다.
3. 결과를 저장합니다. (메모이제이션)
4. 저장된 결과를 이용하여 큰 문제를 해결합니다.

>> DP 푸는 방법 2

1. 문제의 조건대로 손으로 그려보며 반복되는 부분을 찾습니다.
   
   
2. dp테이블 dp[i]는 무엇을 의미하는지 정의해봅니다.  
   dp[i] = ???
   
   
3. 디테일한 점화식을 세웁니다.
   dp[i] = dp[i-1] + dp[i-2]
   
   
4. 필요하다면 dp 테이블을 확장합니다.
   dp[i] → dp[i][j]
   
   
5. 중복되는 부분을 어떻게 활용할 수 있을지 생각합니다.
   어떤 방법으로도 점화식 세워지지 않으면 계산 과정이나 정의의 순서를 뒤집어서 생각해봅니다.
   예를 들면 계산 과정을 완전히 거꾸로 뒤집어보는 발상을 해봅니다.
   즉 1+1=2 이 아니라 2=1+1 이라는 발상을 하는 것입니다.
6. 1번으로 되돌아가서 다시 진행합니다.

 

📢 동적 계획법을 사용하려면 다음의 조건을 만족해야 한다.

1. 최적 부분 구조 (Optimal Substructure)
   • '큰 문제의 최적해'가 '작은 문제의 최적해'를 포함하는 성질입니다.
     즉, 작은 문제의 최적해를 구한 후 그것을 이용하여 큰 문제의 최적해를 구할 수 있습니다.
2. 중복 부분 문제 (Overlapping Subproblems)
   • '동일한 작은 문제를 반복적으로 해결'해야 하는 성질입니다.
     즉, 작은 문제를 해결할 때 반복적으로 같은 문제를 해결해야 합니다.

 

📢 동적 계획법 푸는 방식 2가지 

1. 탑다운(Top-Down) 방식

• 재귀적으로 호출해 문제를 해결한다. 
• 분할정복 방식과 비슷함. 
• 단, 중복되는 작은 문제들은 한번만 푼다.
• 문제점: 스택 오버플로가 발생할 수 있다. 

2. 바텀업(Bottom-Up) 방식

• 작은 문제 ==> 큰 문제까지 해결 
• 이전에 계산한 부분의 결과는 저장해둔다 -> 나중에 같은 부분문제 나타날 때 저장된 값을 사용한다. 
• 재귀 수행 X 반복문 수행 O 

 

# 참고하기 좋은 사이트 

(하나씩 계속 추가해야됨.. 아직 멀고 먼 DP와 그리디..)

• https://stonejjun.tistory.com/48