[ JAVA ] Greedy, Divide Conquer

1. Greedy (그리디)

---

 

1. 그리디란?

 

현재 단계에서 선택할 수 있는 것 중 가장 좋은 것을 선택하는 알고리즘으로

현재 단계에서 가장 좋은 것을 선택했지만 모든 선택을 끝낸 최종의 값은 가장 좋은 선택이 아닐 수도 있으니 유의!!!

---

2. 문제 해결 최적화 방법

 

2-1. 국소적 최적화

최선의 선택을 위해 문제 해결을 위한 기준(가치)으로 정렬을 하여 가장 좋은 것을 선택한다.

       

2-2. 전역적 최적화

정렬할 수 없는 경우 현재 선택할 수 있는 데이타 중 가장 좋을 것을 탐색하여 선택한다.

---

3. 그리디 알고리즘 성립 조건

 

3-1. 탐욕적 속성

각 단계에서의 국소적 최적 선택이 전체 해의 최적성을 해치지 않아야 한다.

부분 문제에서 얻은 해 -> 전체 문제에서도 최적임을 유지

 

3-2. 최적 부분 구조

문제의 최적 해가 작은 부분 문제들의 최적 해로 구성될 수 있다.

부분 문제의 해결 = 전체 문제의 해결

N의 수가 많으면 DP(동적계획법) 사용하기

 

2. Divide Conquer (분할 정복)

---

1. 분할 정복이란?

 

복잡한 문제를 간단한 문제들로 나누어 처리하는 알고리즘 설계 기법으로

보통 재귀적으로 문제를 해결하는 과정에서 주로 사용된다.

• 분할: 해결할 문제를 여러 개의 작은 부분으로 나눈다.
• 정복: 나눈 작은 문제를 각각 해결한다.
• 통합: (필요하다면) 해결된 해답을 모은다.

---

2. 분할 정복의 대표적인 알고리즘

 

ex. 4 method

합병정렬: O(n log n) 

퀵정렬: O(n log n)

이진탐색:  O(log n)

최근접두점문제

 

• 합병정렬( Merge Sort ): 재귀적으로 정렬한 뒤, 정렬된 배열들을 병합
• 퀵정렬( Quick Sort ): 
• 이진 탐색( Binary Search )
• 최근접 두 점 문제( Closest Pair of Points )