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

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