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 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제 보기

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

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

백트래킹(Backtracking)은 문제에서 주어지는 한정된 조건을 만족하는 해를 구할 때 사용하는 알고리즘이다.

문제에서 가능한 모든 해 집합을 대입하면, 당연히 만족하는 해를 찾을 수 있다. 여기서, 백트래킹을 이용하면 시간을 크게 단축시킬 수 있다. 쉽게 말하자면 다음과 같다:

노드의 유망성을 확인한 후, 유망하지 않으면 그 노드의 부모 노드로 돌아간다. 즉, 유망하지 않은 노드는 배제한다.

DFS(Depth-First Search, 깊이 우선 탐색)과 BFS(Breadth-First Search, 너비 우선 탐색)은 그래프 탐색 시 사용되는 알고리즘이다.

각각을 자세히 설명하기 전에, 간단한 모형으로 설명하자면 다음과 같다.