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. 일고리즘 분류
  1.   기술공통
  2.   기초과학
  3.   파동/광학/음향
  4.   방송/멀티미디어/정보이론
  5.   전자/전기/제어
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
      1.   프로그래밍 언어론
      2.   객체지향
      3.   자료구조
      4.   알고리즘
        1.   1. 알고리즘
            2. 알고리즘 설계
            3. 계산 복잡도
            4. 정렬 알고리즘
            5. 탐색 알고리즘
            6. 그래프 알고리즘
            7. 해쉬 알고리즘
            8. 해싱 탐색
            9. 하노이 탑
            10. 일고리즘 분류
      5.   자료표현(알파벳/코드)
      6.   시스템 프로그래밍
      7.   프로그래밍언어 종류
      8.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   기계/재료/공업일반
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     참고문헌