Reference

• 방송통신대학교 3학년 전공과목 - 알고리즘

---

분할 정복 방법

• 순환적으로 문제를 푸는 하향식 접근 방법
• 주어진 문제의 입력을 나눌 수 없을 때까지 두 개 이상의 작은 문제들로 순환 분할
• 분할된 작은 문제들을 각각 해결한 후, 각 해를 결합하여 원래의 문제의 해를 구하는 방식
• 각 순환 호출이 이루어질 때 마다 아래와 같은 세 단계의 작업이 발생

1. 분할(divide) - 문제의 입력을 여러 개의 작은 문제로 분할
2. 정복(conquer) - 작은 문제들을 순환적으로 분할
3. 결합(combine) - 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함

그러나 경우에 따라 결합단계 없이 분할단계와 정복단계만을 통해 해가 구해지기도 한다.

분할된 작은 문제는 원래의 문제에 비해 입력 크기만 작아진 것이며 문제 자체는 원래와 동일하며 분할정복을 적용한 알고리즘의 분할과정에서 분할되는 작은 문제의 개수와 크기는 아래와 같다

이진탐색 - 크기가 n인 문제를 크기가 n/2인 두 개의 문제로 분할
합병정렬 - 크기가 n인 문제를 크기가 n/2인 두 개의 문제로 분할
선택문제 - 크기가 n인 문제를 크기는 감소하지만 일정하지 않은 크기의 두 개의 작은 문제로 분할 ( 그중 하나의 작은 문제는 처리 대상에서 제외 )
퀵정렬 - 크기가 n인 문제를 크기는 감소하지만 일정하지 않은 크기의 두 개의 작은 문제로 분할

---

Dynaminc Programming

• 소문제에 대한 해 저장
• 저장된 해를 이용하여 크기가 더 큰 문제의 해를 점진적으로 생성해나감
• 상향식 접근 방법
• 소문제들이 독립적일 필요 없음
• 한 번 사용된 소문제의 해를 재사용

처리과정
1. 주어진 문제에 대한 최적해를 제공하는 점화식 도출
2. 가장 작은 소문제부터 점화식의 해를 구한 뒤 테이블에 저장
3. 테이블에 저장된 해를 이용하여 점진적으로 큰 상위 문제의 해를 구한다

동적 프로그래밍을 이용한 알고리즘

• 피보나치 수열
  - 피보나치 수열의 순번에 해당하는 수를 찾는 문제
• 연쇄 행렬 곱셈
  - n개의 행렬 곰셈 시 최소 기본 곱셈 횟수를 가진 행렬의 곱셈 순서를 구하는 문제
• 스트링 편집 거리 문제
  - 문자열 X를 Y로 변환하는데 필요한 전체 편집 연산에 대한 최소 비용 도출 문제
• 모든 정점간의 최단 경로
  - 가중 방향 그래프 G = ( V, E ) 에서 모든 조합의 두 정점 간의 최단 경로를 구하는 문제
• 저울 문제
  - 무게 M인 물체를 n개의 추를 이용하여 양팔저울로 달 수 있는지 확인하는 문제

---

Greedy(욕심쟁이)

• local(국부적인) 최적해 선택으로 global(전체적인) 최적해를 구하는 방법
  - 해를 구하는 일련의 선택 단계마다
  - 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 해 선택
• 데이터 간의 관계 고려 x, 현재 상태에 만족하는 최적해 선택 -> 항상 전체적인 최적해를 보장하지 못하는 한계 보유
• 동적 프로그래밍 처럼 최적화 문제 해결에 주로 사용

동전 거스름돈 문제

• 최소 신장 트리
  - 가중 무방향 그래프에 대해 최소 신장 트리를 구하는 문제 (크루스칼, 프림 알고리즘)
• 최단 경로
  - 가중 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치 합이 가장 작은 경로를 찾는 문제 ( 다익스트라 알고리즘 )
• 작업 스케줄링 문제
  - 가장 적은 개수의 기계를 사용해서 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 해당하는 문제

---

각 알고리즘 비교

	분할 정복	동적 프로그래밍	욕심쟁이
계산 방식	순활 분할 하향식	최적해 산출 상향식
주 사용 분야		최적화 문제 해결	근사치 추정
대표 알고리즘	최소, 최대값 찾기, 이진 탐색, 병합 정렬	피보나치 수열 알고리즘	근사 알고리즘, 그리디 알고리즘
설명	문제를 분할하여 계산하며 분할된 문제의 중복이 일어나지 않는다	문제를 분할하여 계산하며 분할된 문제의 중복(반복)이 발생하며 '같은 문제는 구할 때마다 정답이 같다'라는 조건을 통해 큰 문제를 해결한다.	현재 상태에서 가장 좋다고 판단되는 것을 선택하여 진행되는 방법. 효율적이고 간단하지만 최적의 답은 아닐 수 있다.