#21.05.26 Section5 - Sprint3 (4)

TDL

다이나믹 프로그래밍
- 특정한 문제를 해결하는 알고리즘이 아닌, 문제를 해결하기 위한 접근 방식 중 하나.
- 점화식, 메모제이션, 큰문제->작은문제
- 재귀적 + 불필요한 계산 줄이기

그리디 알고리즘

NOTE4

0. 소스코드 분석하기

   • 새로운 알고리즘과 방법론을 알게 될 경우 기본적으로 주어진 문제와 어떤 주제에서 파생되었는지 알고 시작해야한다.
   • 코드가 어려우면 쉬운 말로 손코딩 또는 주석 달기
   • 코드 분석 + 흐름이해(재귀를 기반으로 함수의 호출흐름과 변수가 사용되는 목적 파악하면서 소스 코드 분석)

1. DP (Dynamic Programming, 동적 계획법)

   • 문제의 일부분을 풀고 그 결과를 재활용하는 방법
   • 하나의 문제를 중복되는 서브문제로 나누어 푸는 방법
   • 분할정복(Divide and Conquer)과 유사한 개념

2. DP 사용 : 이진 검색, 최단경로 알고리즘, 최적화 문제, 외판원 문제

3. DP와 분할정복 차이점
   
   - DP는 문제를 분할할 때 중복되는 서브문제가 있어 메모이제이션을 활용해 같은 문제를 재사용할 수 있고, 분할정복은 분할된 서브문제가 독립적이다.
   - DP를 활용하면 해결할 수 있는 문제의 범위가 넓어진다.
   - DP = 분할정복 + Overlapping Subproblems(중복) + Optimal Substructure(재사용)
   

4. DP의 2가지 방법론

   • 메모이제이션(하향식방법) : 메인문제를 분할하면서 해결
   • 태뷸레이션(상향식방법) : 가장 작은 문제 먼저 해결하고 최종적으로 메인문제 해결

5. 실전

   • 현업에서는 발생하는 문제와 정답을 하나로 정의할 수 없다.(입출력 조건이 다양함) 따라서 연습을 위해 같은 문제에 대해 DP와 Greedy로 접근해 문제를 풀어보고 다양한 입력조건에 따른 문제해결에 대해서도 생각해봐야함.

6. Greedy (탐욕 알고리즘)

   • 발견법(heuristic method)중 하나. 중복되지 않는 서브문제.
     *발견법: 최선,최적보다도 주어진 상황을 한단계씩 빠른 시간 내에 해결하기 위해 사용하는 방법론. backtracking(역추적)과 같이 알고리즘 수행시간이 많이 걸릴 때 사용함.
   • 탐욕법은 역추적과는 반대 개념으로 다른 문제들과 독립이다.(다른 노드의 선택에 영향을 고려x)

7. 탐욕법 실제상황 예시

   • 물건담기 : 정해진 시간 내에 물건을 담으려는 경우, 우선순위가 높은 순서대로 물건을 담는다. 한번 담은 물건은 다시 빼지 않는다.
   • 여행경로 짜기(도시방문) : 도시가 많아질수록 도시를 방문(배열)할 수 있는 가짓수가 많아지며 알고리즘 연산 비용도 함께 증가. 이럴 때 탐욕 알고리즘을 활용한다.
     - 방문하지 않은 도시 중 가장 가까운 도시로 간다.
     • 모든 도시를 방문할 때까지 반복.
   • 전력망 연결(전력공급) : 발전소 한 개로 여러 마을 전력을 공급하는 경우 최소비용을 들여서 모든 마을에 전력을 공급하려면 ?
     - 전력이 공급되지 않는 마을, 공급되는 마을 사이가 가장 가까운 것을 골라 두 마을을 연결
     • 모든 마을에 전력이 공급될 때까지 반복.

8. 정리 ( DP와 Greedy)

   • DP : 문제를 작은 단위로 분할해 해결한 뒤, 해결된 중복문제들의 결과를 기반으로 전체문제를 해결함.
   • Greedy : 각 단계마다 최적해를 찾는 문제로 접근, 해결해야 할 전체문제의 갯수를 줄이기 위해 개별적으로 문제를 해결해나가는 선택을 함.