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. 탐욕 알고리즘

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