Greedy

탐욕 알고리즘이라고 불립니다. 탐욕 알고리즘은 그 뜻 그대로, 결정의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 해답에 도달하는 방법입니다. 뒤를 돌아보지 않고 매우 탐욕적이죠.

그 절차로는 이렇습니다.

현재 상태에서 최적의 답을 선택한다
-> 답이 조건에 부합하는지 검사한다
-> 부합하지 않으면 다시 돌아가 앞의 과정을 반복한다

하지만 탐욕 알고리즘이 최선의 방법만을 돌려주지는 않는 것 같습니다.

다음의 그림을 통해 그 예외 상황을 살펴보죠.

도둑은 35kg까지 수용할 수 있는 가방을 가지고 있고, 성격이 탐욕 알고리즘적이라고 가정합시다.
도둑은 순간의 가장 최적이라 생각되는 물건인 3천달러짜리 그림을 가방에 담을 것입니다. 하지만 그 다음으로는 가방에 담을 수 없죠. 결과적으로 가방에 담긴 물건의 총 가치는 3천달러입니다.
하지만 컴퓨터와 반지를 훔쳤다면 3천 5백달러의 물건을 훔칠 수 있었을텐데요.

이와 같이 탐욕 알고리즘은 최적의 결과를 도출하지 못하는 예외적인 상황들이 있습니다.

Dynamic Programming

Dynamic Programming은 모든 경우의 수를 따져본 뒤에, 이를 조합해 최적의 해법을 찾는 방식입니다.
주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 식의 알고리즘입니다. 미리 해결한 하위 문제의 결과값을 재사용함으로써 계산 횟수를 줄이는 아주 효율적인 방법이죠. 했던 일 안 하겠다는 말입니다.

다이나믹 프로그래밍은 다음 두 조건이 만족해야 사용할 수 있습니다.

• 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제들은 중복된다.
• 작은 문제에서 구한 정답은 큰 문제에서도 동일하다. 즉, 큰 문제에서도 작은 문제의 정답을 사용할 수 있다.

다이나믹 프로그래밍으로 해결할 수 있는 알고리즘 중에 대표적으로 피보나치 수열 알고리즘이 있습니다.
아래의 코드를 통해 확인해보겠습니다.

function fib(n) {
	if(n <= 2) return 1;
	return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...

아래 그림은 fib(5)를 구하는 과정입니다.
재귀를 통해 fib(0), fib(1)을 구하고, 그 결과가 큰 문제를 해결하는 데에 여러 번 사용되고 있다는 것을 확인할 수 있습니다.

...
다이나믹 프로그래밍이 무엇을 말하는 지는 알겠지만, 실제 코드로 구현을 하는 것은 아직 익숙치 않습니다. 부단한 노력이 필요함을 느낍니다.

[알고리즘] 탭에 Greedy, Danamic Programming 관련 알고리즘을 업로드하도록 하겠습니다.