![]()
다이나믹 프로그래밍: 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성 대부분의 재귀 알고리즘은 최적 부분 구조 문제를 풀 수 있음 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해나감 알고리즘 풀이 가능한 문제들의 특징 풀이 가능한 문제 및 알고리즘 다이나믹 프로그래밍 - 최적 부분 구조 - 중복된 하위 문제들 - 0-1 배낭 문제 - 피보나치 수열 - 다익스트라 알고리즘 그리디 알고리즘 - 최적 부분 구조 - 탐욕 선택 속성 - 분할 가능 배낭 문제 - 다익스트라 알고리즘 분할 정복 - 최적 부분 구조 - 병합 정렬 - 퀵 정렬 다익스트라 알고리즘 - 최적 ..
그리디 알고리즘: 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘 대부분 뛰어난 결과를 도출하지 못하지만, 드물게 최적해 보장 최적해를 찾을 수 있으면 그것을 목표로 삼고, 그것이 어렵다면 주어진 시간 내에 최적에 가까운 해를 찾음 탐욕 선택 속성 + 최적 부분 구조 에 해당하는 문제에 좋다 탐욕 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않는 것 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우 예) 다익스트라, 허프만 코딩, ID3 DP vs Greedy DP: 하위 문제에 대한 최적 솔루션을 찾고, 이 결과들을 결합한 정보로 전역 최적 솔루션 선택 Greedy: 각 단계마다 로컬 최적해를 찾는 문제로 접근..
