Greedy Algorithm (그리디 알고리즘, 탐욕 알고리즘) 은 문제를 작은 문제들로 나눈 후, 각 순간순간의 문제마다 최적의 결정을 택하는 알고리즘이다. 작은 문제들로 나누어 풀기 때문에, 일종의 DP (동적계획법) 문제의 예라고 생각할 수 있다.

Baekjoon 12865, 백준 12865 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제 보기

Baekjoon 9251, 백준 9251 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제 보기

우선, Dynamic Programming에 대해 알아보자.

Dynamic Programming (동적계획법) 이란, 쉽게 말해 큰 문제를 작은 문제로 나누어 푸는 것을 말한다. 여기까지는 분할정복 (Divide and Conquer)와 개념이 일치한다. Dynamic Programming의 핵심 포인트는, 작은 문제들을 반복해서 풀지 않는다는 것이다. 이는 시간을 크게 절약할 수 있다.

두 번째로 소개할 Dynamic Programming 알고리즘은 배낭 문제(Knapsack problem) 이다.

Knapsack Problem(배낭문제)란, 주어진 가치와 무게를 가진 짐들을 배낭에 넣을 때, 주어진 무게의 최댓값을 넘지 않으면서 가치의 합이 최대가 되도록 짐을 넣는 방법을 찾는 문제이다.

Baekjoon 2580, 백준 2580 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제 보기