[알고리즘]동적 계획법, 탐욕(그리디) 알고리즘

동적 계획법

다이나믹 프로그래밍이라고 칭함

큰 문제를 작은 문제로 나누어 해결 하는 알고리즘

메모제이션을 활용하여 이전에 찾은 해결 법을 이용하여 중복 계산 방지

분할 정복과 다른 점은 중복되는 결과를 다시 계산 하지 않도록 한다는 점

대표적으로 최장 공통 부분 순서

- Top-Down : 재귀 호출을 통해 큰 문제를 작은 문제로 나누어 푸는 방식

- Bottom-Up : 작은 문제에서부터 풀어 큰 문제를 푸는 방식

탐욕(그리디) 알고리즘

근시안적인 답을 찾는 알고리즘

미래를 고려하지 않고 현재 상태에서 가장 좋은 해를 찾는 방식

대표적으로 거스름돈 계산, 허프만 코딩, 크루스칼, 프림, 다익스트라

위 문제는 가장 큰수를 구하는 문제

 일반적으로 구하는 가장 큰값 구했을 시 / 탐욕 알고리즘으로 큰 값을 구했을 시