그리디 알고리즘, 동적 계획법

[그리디]

 

그리디 알고리즘은 매 순간마다의 선택은 최적이지만 결과값이 최적이라는걸 보장할수 없음.

탐욕적 선택 속성과 최적 부분 구조가 만족되면 최적의 결과값을 보장할 수 있다. (=매트로이드 구조 성립)

프림 알고리즘, 크루스칼 알고리즘, 다익스트라 알고리즘 등에 사용된다.

대표적인 문제는 거스름돈 문제. 하지만 동전이 임의의 금액 40원 등으로 설정된다면 최적의 해를 구할 수 없다.

문제를 보고 조건을 잘 설정하는게 중요한 것 같다.

 

 

 

[다이나믹 프로그래밍] =(동적 계획법, DP)

 

동적 계획법의 결과는 언제나 최적이지만 그리디 알고리즘에 비해 속도가 느리다.

중복 부분 해결과 최적 부분 구조가 성립되면 적용할 수 있다.

대표적인 문제는 피보나치 수열. 하향식(재귀)과 상향식(반복문)으로 구현할 수 있다.

보통 Bottom-up 방식이 많이 사용된다.

점화식을 세우는게 나에겐 가장 어렵다. 식만 세워지면 구현은 어렵지 않다