Algorithm Design   알고리즘 설계

(2017-12-04)

분할정복법

1. 알고리즘 설계 기법

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

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

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


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

 
        최근수정     요약목록(시험중)     참고문헌