Algorithm Design   알고리즘 설계

(2020-08-17)

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

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

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

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

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


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

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

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

  ㅇ 접근 방식
     - 아래에서 위로 해결하면서 전체 문제를 해결하는 상향식 접근 방식
        . 간단한 하위 문제부터 해결하면서,
        . 하위 문제의 해를 테이블에 저장해 놓고,
        . 이를 이용하여, 좀더 복잡한 상위 문제를 해결하여 나아감

  ㅇ 구현 방식
     - 재귀 관계식을 세워, 입력 사례를 더 작은 입력 사례로 분할 함

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

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

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

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


5. 백트래킹 (Backtracking) 방법

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

  ㅇ 백트래킹 (Backtracking)
     - 갈 수 있는데까지 가보다가 막히면 되돌아와서 다른 길로 가는 방식
     - 해를 구할 때까지 모든 가능성을 시도하게 됨
     - 통상, 그래프에 대해 DFS(깊이우선탐색)으로 탐색하는 모든 방법으로써, 재귀적으로 구현됨
     - 문제가 커질 경우 엄청난 시간이 걸리므로, 분기한정법 등 탐색 범위를 줄이는 여러 보완을 취함


6. [기타사항]

  ㅇ NP 문제 (NP, Nondeterministic Polynomial Problem), NP 완비 문제 (NP-complete)
     - 아직까지 다항식 시간 O(nk) 내에 해결 가능한 최적 알고리즘을 찾지 못하였으며,
       그같은 최적 알고리즘이 존재하지 않음을 증명도 못함
     - 꽤 많은 문제가 이같은 성질을 함께 함
     - 그러나, 만일 이같은 문제들 중 하나가 다항식 시간 O(nk) 내 해결 가능한
       알고리즘이 존재하면, 나머지 모든 문제도 다항식 시간 O(nk) 내에 해결 가능 함

     -  ... (작성중) ...


[알고리즘 전략] 1. 알고리즘 설계 2. Brute Force 3. 분할 정복법 4. 탐욕 알고리즘

 
        요약목록     참고문헌