SEB Section 3 Greedy

Greedy Algorithm

그리디 알고리즘은 선택의 순간마다 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법이다. 다음 단계로 문제를 해결할 수 있다.

1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사 : 선택된 해가 문제의 조건에 만족하는지 검사한다.
3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

매 순간, 최적이라 생각되는 해답을 찾으며 이를 토대로 최종 ㅜㅁㄴ제의 해답에 도달하는 문제 해결 방식 이다.

따라서 다음 두가지의 조건을 만족해야 최적의 해를 보장할 수 있다.

• 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결방법으로 구성된다.

그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 근사 알고리즘으로 사용할 수 있다.

하지만 매 순간 최적의 선택을 찾게 된다면 결과는 최적의 경우의 수가 아닌 경우도 있다. 그래서 이때 Dynamic Programming(Dp; 동적 계획법)을 사용한다.

Dynamic Programming(DP)

DP의 방식은 모두의 경우의 수를 조합해 최적의 해법을 찾는 방식이다. 원리로는 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식이다. 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 즉, 하나의 문제는 단 한번만 풀도록 하는 알고리즘 이다.

DP는 다음 두가지 가정이 만족할 때 사용할 수 있다.

• 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

첫 번째 조건을 만족을 하더라도 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 한다. 두 번째 조건도 마찬 가지로, 작은 문제들의 최적의 해법을 결합을 하여 전체 문제의 최적의 해법을 구할 수 있어야 한다.

Recursion + Memorization

앞서 해결책을 저장을 하여 나중에 해결책을 적용할 수 있어야 한다고 했다. 이때 사용하는 방법이 Memorization이다. Memorization이란 컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 저장함으로써 동일한 계산의 반복 수행을 제거하여 실행 속도를 빠르게 하는 기술이다.

보통 큰 문제를 해결하기 위해 작은 문제를 호출 하게 되는데, 이 방식을 Top-down 방식이라 부른다.

Iteration + Tabulation

하위 문제의 결괏값을 배열에 저장하고, 필요할 때 조회하여 사용하는 것은 같다. 이 방식은 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법으로, Bottom-up 방식이라 부른다.