Algorithm Design   알고리즘 설계

(2020-01-01)

알고리즘 전략, 다이내믹 프로그래밍, 동적 계획법, 백트래킹

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

  ㅇ 새로운 문제를 해결하는 과정에서, 어떤 전략과 접근방식으로,
     - 그 해법을 찾아가야 하는지에 대한 다양한 방법론/해결법들을 다룸

  ㅇ 주요 분류
     - 무작위 대입 기법 (Brute Force Technique)
     - 분할 정복법
     - 욕심쟁이 방법
     - 동적 계획법
     - 백트래킹 등

  ㅇ 위 방법론에 따라, 문제를 푸는 독특한 해결 단계/절차를 알고리즘 이라고 함


2. 분할 정복/분할 통치 (Divide and Conquer) 전략

  ㅇ 기본 생각
     - 큰 문제를 보다 작은 문제로 분할하는 것이, 복잡함에 대처하는 좋은 수단임

  ㅇ 例)
     - 이진 탐색, 퀵 정렬, 합병 정렬, 선택 문제(최대값/최소값 찾기, n번째 작은 원소 찾기 문제 등)
     - 선형 시스템 풀기, 함수근 찾기, 보간법, 수치 적분
3. 동적 계획법 (Dynamic Programming, 다이내믹 프로그래밍) 전략

  ㅇ 접근 방식
     - 아래에서 위로 해결하면서 전체 문제를 해결하는 상향식 접근 방식
        . 간단한 하위 문제부터 해결하면서,
        . 하위 문제의 해를 테이블에 저장해 놓고,
        . 이를 이용하여, 좀더 복잡한 상위 문제를 해결하여 나아감
     - 재귀 관계식을 세워, 입력 사례를 더 작은 입력 사례로 분할 함

  ㅇ 주요 특징
     - 소 문제들이 서로 독립일 필요 없음
     - 최소값/최대값을 구하는 최적화 문제를 다룰 때 적합

  ㅇ 例) 프로이드의 최단경로 알고리즘
4. 탐욕 알고리즘 (Greedy Algorithm) 전략 

  ㅇ 기본 생각
     - 완벽한 해결책 보다는 차선책(Suboptimal)
        . 전체 최적 해를 구하는 보장이 없으므로, 최적 해를 얻는지 확인하는 절차 필요
     - 그때그때 상황에 맞는 최상의 해결책을 찾는다는 의미로 `탐욕(Greedy)`라는 말을 씀
        . 과거나 미래는 생각 않고, 오직 현재 최대의 만족을 추구(근시안적임)

  ㅇ 例)
     - 동전 거스름돈을 가장 적은 수의 동전으로 주는 문제 
     - 최소비용 신장트리를 구하는 알고리즘(크루스칼 알고리즘,프림 알고리즘) 등


5. 백트래킹 (Backtracking) 방법

  ㅇ 문제를 푸는 과정에서 발생할 수 있는 모든 가능한 상태트리로 구축하고,
     깊이우선(Depth First) 알고리즘을 이용하여 해답을 찾아가는 기법


6. [기타사항]

  ㅇ NP 완비 이론 (NP, Nondeterministic Problem) 
     - NP 문제
        . 다항식 시간(O(n),O(log n),O(n log n),O(n2),O(n3) 등) O(nk) 내에 해결할 수 있는 문제
     -  ... (작성중) ...


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

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