Algorithm Design   알고리즘 설계

(2018-12-29)

알고리즘 전략, 탐욕 알고리즘, Divide and Conquer, 분할 정복법, 분할 통치법, 동적 계획법

1. 알고리즘 설계 기법 / 문제 해결 접근 전략 (Algorithm Design Paradigm)

  ㅇ 분할 정복/분할 통치 (Divide and Conquer) 전략
     - 기본 생각
        . 큰 문제를 보다 작은 문제로 분할하는 것은, 복잡함에 대처하는 좋은 수단임
     - 접근 방식
        . 문제를 작은 문제로 나눠 순환적으로 푸는 하향식 접근 방식
           .. 쪼개진 작은 문제들은 원래 문제와 동일한 성격과 특징을 지님
           .. 작은 문제를 해결한 해를 결합하여 원래 문제의 해를 구함
           .. 각 순환 마다, 분할,정복,결합의 단계를 거침
     - 주요 특징
        . 분할된 소 문제들은 서로 독립적임
        . 소 문제는 원래 문제와 단지 크기 만 작아진 동일한 형태임
        . 통상, 재귀적인 수행을 수반함

     - 例) 이진 탐색, 퀵 정렬, 합병 정렬,
           선택 문제(최대값/최소값 찾기, n번째 작은 원소 찾기 문제 등)
     - 例) 선형 시스템 풀기, 함수 찾기, 보간법, 수치 적분 등

  ㅇ 동적 계획법 (Dynamic Programming) 전략
     - 접근 방식
        . 아래에서 위로 해결하면서 큰 전체 문제를 해결하는 상향식 접근 방식
           .. 간단한 하위 문제부터 해결하면서, 해를 테이블에 저장해 놓고,
           .. 이를 이용하여, 좀더 복잡한 상위 문제를 해결하여 나아감
     - 주요 특징
        . 소 문제들이 서로 독립일 필요 없음
        . 최소값/최대값을 구하는 최적화 문제를 다룰 때 적합

     - 例) 프로이드의 최단경로 알고리즘 등

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


[알고리즘] 1. 알고리즘 2. 알고리즘 설계 3. 계산 복잡도 4. 하노이 탑 5. 순서도 6. 재귀 호출
[알고리즘 종류]

 
        최근수정     요약목록     참고문헌