Algorithm Design   알고리즘 설계

(2017-12-04)

분할정복법

1. 알고리즘 설계 기법

  ㅇ 분할정복(Divide and Conquer) 전략
     - 문제를 작은 문제로 나눠 순환적으로 푸는 하향식 접근 방식
        . 쪼개진 작은 문제들은 원래 문제와 동일한 성격과 특징을 지님
     * 큰 문제를 보다 작은 문제로 분할하는 것은 복잡함에 대처하는 좋은 수단임
     - 例) 이진 탐색, 퀵 정렬, 합병 정렬 등

  ㅇ 동적계획법(Dynamic Programming) 전략
     - 아래에서 위로 해결하면서 큰 전체 문제를 해결하는 상향식 접근 방식
        . 간단한 하위 문제부터 해결하면서, 해를 테이블에 저장하고 이를 이용하여,
          좀더 복잡한 상위 문제를 해결하여 나아감
     - 최적화 문제를 다룰 때 적합
     - 例) 프로이드의 최단경로 알고리즘 등

  ㅇ 탐욕 알고리즘(Greedy Algorithm) 전략 
     - 좋은 해결핵을 찾아가는 기법
        . 그때그때 상황에 맞는 최상의 해결책을 찾는다는 의미로 `탐욕(Greedy)`라는 말을 씀
           .. 과거나 미래는 생각 않고, 오직 현재 최대의 만족을 추구(근시안적임)
        . 해를 구하는 일련의 선택 과정 마다,
           .. 가장 좋아보이는 최선을 선택하면, 전체적으로 최적 해를 구할 수 있다는 방법론
     - 완벽한 해결책 보다는 차선책(Suboptimal)
        . 언제나 최적 해를 구하는 보장이 없어, 최적 해를 얻는지 확인하는 절차 필요
     - 최적화 문제를 다룰 때 적합
     - 例)
        . 동전 거스름돈을 가장 적은 수의 동전으로 주는 문제 
        . 최소비용 신장트리를 구하는 알고리즘(크루스칼 알고리즘,프림 알고리즘) 등


[알고리즘] 1. 알고리즘 2. 알고리즘 설계 3. 계산 복잡도 4. 정렬 알고리즘 5. 탐색 알고리즘 6. 그래프 알고리즘 7. 해쉬 알고리즘 8. 해싱 탐색 9. 하노이 탑 10. 일고리즘 분류

 
        최근수정     참고문헌