분할 정복(Divide and conquer), 동적 계획법(Dynamic Programming), 그리디(Greedy) 개념정리

Divide and conquer = 분할 정복

1. Divide    -> 나누기

2. Conquer   -> 나눈것을 해결하기

3. Combine  -> 합치기

단계를 거친다.

ex) 합병정렬

 

Dynamic Programming

다이나믹 프로그래밍을 사용하기 위해 필요한 2가지 조건

1. 최적 부분 구조 (Optimal Substructure)

 > 길찾기에서 최단거리를 구할때 최종단계 바로 전 단계의 최적값을 구하면
최종단계 값을 간단히 구할 수 있다. 이렇듯 부분 구조의 최적의 답을 구해서 전체의 최적의 답을 찾는 경우를 최적 부분구조라고 한다.

 

2. 중복되는 부분 문제 (Overlapping Subproblems)

 > 피보나치 수열과 같이 fib(5)를 알기 위해선 fib(3) + fib(4)값을 알아야하는데
이때 fib(2)가 여러 번 사용된다. 이런 케이스를 중복되는 부분문제라고 한다.
1.최적부분구조 와 2.중복되는 부분문제 두가지 조건이 충족되는 경우 다이나믹프로그래밍으로 해결 할 수 있다.

다이나믹프로그래밍을 구현하는 방법은 2가지가 있다.

1) memozation  (top - down)

 > 재귀함수 기반이기때문에 너무 많이 호출되면 아웃오브메모리

2. tabulation (bottom - up)

 > 중복 계산을 하게되는 단점 존재
 -> 리스트 저장이 아닌 변수 2개로 계산한다면 공간복잡도는 O(1)로 활용 가능

 

Greedy

미래를 보지 않고 당장 보이는 최적값을 고름

• 장점 : 간단하고 빠름
• 단점 : 최적의 답이 보장되지 않음

 

사용처

• 최적의 답이 필요없는 경우
• 당장 보이는 값이 최적의 답을 보장해 주는 경우

 

Greedy Algorithm을 사용해서 최적의 솔루션을 구하기 위한 필수 조건을 모두 고르세요

• 최적 부분 구조
• 탐욕적 선택 속성 : 큰값부터 처리하는게 최적의 답인 경우