JAVA 알고리즘 (1) Greedy 알고리즘이란

1. Greedy 알고리즘이란?

- 최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘

- 미래를 고려하지 않고, 오직 현재 시점에서 가장 좋은 선택을 구하는 방법

 -> 현재 내린 선택이 나중에 어떤 결과를 가져올지 고려하지 않고, 지금 가장 빠르거나 저렴한, 혹은 가장 가치 있는 선택을 내리는 알고리즘이다.

 

2. Greedy 알고리즘의 특징

- 최적의 답을 항상 보장하지 않는다...

 => 현재의 최적의 답이 전체의 최적의 답이 될 수 없기 때문이다 !!!

- 따라서 최적의 답이 보장되는 조건에서만 활용이 가능하다....

 

 2.1 Greedy 알고리즘 사용 조건

   - 현재의 선택이 미래의 선택에 영향을 주지 않을 때 적용이 가능하다.

   - 부분의 최적의 해가 모여 전체의 최적의 해가 될 때

    => 하나의 큰 문제를 여러개의 작은 문제로 나눌 수 있고, 작은 문제의 답이 모여 전체 문제의 답이 될 때

첫번째 조건을 만족하고, 두번 째 조건도 같이 만족한다.

위 예시의 경우 서울에서 부산까지의 최단 거리를 구하는 문제이다. 이 때, 서울에서 대전까지의 최단거리의 선택이 대전에서 부산까지의 최단거리 선택에 영향을 주지 않는다. (1번째 조건 만족)

서울에서 대전까지 최단거리와 대전에서 부산까지의 최단거리의 합이 결국 문제의 답이 된다 (2번째 조건 만족)

 

3. 전략

- 결국 핵심은 문제 분해와 정렬이다.

- 서울 - 부산을 서울 -대전 / 대전-부산으로 큰 문제를 2개의 작은 문제로 나누고, 각 거리를 Sorting하여 최단거리를 구한 후 합하면 간단한 문제가 된다.

- 다만, 어떻게 정렬을 해야 미래를 고려하지 않고, 현재 문제의 최적의 답을 구할 수 있는지가 중요하며, Greedy 문제는 따로 분류하기가 쉽지 않다

- 이와 관련한 문제를 많이 풀어봐야 그리디 문제를 접목시키는데 유리할 거 같다...