분치법과 귀속

4044 단어

사상과 전략을 설계하다

  • 분치법의 설계 사상은 직접적으로 해결하기 어려운 큰 문제를 규모가 비교적 작은 같은 문제로 나누어 각각 격파하고 나누어 치료하도록 하는 것이다
  • 분치 전략은 하나의 규모가 n인 문제에 대해 만약에 이 문제가 쉽게 해결될 수 있다면 (예를 들어 규모 n이 비교적 작다) 직접 해결하고 그렇지 않으면 이를 k개의 규모가 비교적 작은 자 문제로 분해한다. 이런 자 문제는 서로 독립적이고 원 문제와 형식이 같으며 이 자 문제들을 귀속적으로 해결한 다음에 각 자 문제의 해를 합쳐서 원 문제의 해를 얻는다.이런 알고리즘 설계 전략을 분치법이라고 하는데..

    • 원문제를 이미 해결된 부분과 미해결된 부분으로 분해할 수 있다. 이 두 부분의 길이는 모두 0이 될 수 있다. 이미 해결된 부분에 대해 우리는 탐구하지 않고 미해결된 부분에 대해 우리는 몇 개의 최소자 문제의 집합으로 분해할 수 있다. 모든 최소자 문제에 대해 우리는 간단하게 해답을 구할 수 있다.

    분치법의 적용 조건

  • 이 문제의 규모를 어느 정도 축소하면 쉽게 해결할 수 있다.절대 다수의 문제는 모두 만족할 수 있다. 왜냐하면 문제의 계산 복잡성은 일반적으로 문제 규모가 증가함에 따라 증가하기 때문이다
  • 이 문제는 규모가 비교적 작은 몇 가지 같은 문제로 분해할 수 있다. 즉, 이 문제는 최우선자 구조적 성격을 가지고 있다.이 특징은 분치법을 응용하는 전제이고 대다수 문제가 만족할 수 있는 것이다. 이 특징은 귀속 사상의 응용을 반영한다
  • 이 문제를 이용하여 분해된 서브문제의 해는 이 문제의 해로 합칠 수 있다.이 특징이 관건이다. 분치법을 이용할 수 있는지의 여부는 문제가 제3조 특징을 가지고 있는지에 달려 있다. 만약에 제1조와 제2조 특징을 갖추고 제3조 특징을 갖추지 못하면 욕심법이나 동태기획법을 고려할 수 있다
  • 이 문제가 분해한 각 하위 문제는 서로 독립적이다. 즉, 하위 문제 사이에는 공공적인 하위 문제가 포함되지 않는다.이 특징은 분치법의 효율과 관련된다. 만약에 각 자 문제가 독립적이지 않으면 분치법은 많은 불필요한 작업을 하고 공공의 자 문제를 반복적으로 풀어야 한다. 이때 분치법을 사용할 수 있지만 일반적으로 동적 기획법을 사용하는 것이 비교적 좋다

    • 단계 및 설계 모드

  • 분해: 원문제를 몇몇 규모가 작고 서로 독립적이며 원문제와 형식이 같은 자문제로 분해한다
  • 해결: 만약에 자 문제의 규모가 비교적 작고 쉽게 해결되면 직접 풀고 그렇지 않으면 각 자 문제를 귀속적으로 푼다
  • 합병: 각 하위 문제의 해를 원래 문제의 해로 통합..

    • 디자인 모델

    

Divide-and-Conquer(P)
    1. if |P|≤n0
    2. then return(ADHOC(P))
    3.  P  P1 ,P2 ,...,Pk
    4. for i←1 to k
    5. do yi ← Divide-and-Conquer(Pi) △  Pi
    6. T ← MERGE(y1,y2,...,yk) △  
    7. return(T)
  • 여기서 |P|는 문제 P의 규모를 나타냅니다
  • n0은 한도값으로 문제 P의 규모가 n0을 초과하지 않을 때 문제를 직접 풀기 쉬우므로 더 이상 분해할 필요가 없음을 나타낸다
  • ADHOC(P)는 이 분치법의 기본 서브 알고리즘으로 소규모 문제 P를 직접 해결하는 데 사용된다.따라서 P의 규모가 n0을 초과하지 않을 때 직접 알고리즘 ADHOC(P)로 해답을 구한다
  • 알고리즘 MERGE(y1, y2,..., yk)는 이 분치법의 병합 서브 알고리즘으로 P의 서브 문제 P1, P2,..., Pk의 상응하는 해 y1, y2,..., yk를 P의 해로 병합하는 데 사용된다

    • 사유 과정


    실제로는 수학 귀납법과 유사하여 본 문제를 해결하는 구해 방정식 공식을 찾은 다음에 방정식 공식에 따라 귀속 프로그램을 설계한다.
  • 반드시 가장 작은 문제 규모를 먼저 찾았을 때의 해답 방법을 찾아야 한다
  • 그리고 문제의 규모가 커지면서 해답을 구하는 방법을 고려한다
  • 해답을 구하는 귀속 함수식을 찾은 후(각종 규모나 인자) 귀속 프로그램을 설계하면 된다

    • 관례
    Write function void stringSplit (char *str, int n, int *length, ...); which is able to split the string str into an undefined number of sub-strings whose sizes are stored in length[0], length[1], . . ., length[n-1]. Write an error message when it is not possible to split the string into sub-strings of those lengths. Print-out the generated sub-strings when it is possible. For example, with: • str = Hello, n = 2, and length = (2, 3), the program may produce sub-strings (He, llo), or (Hel, lo). • str = Hello, n = 2, and length = (3, 4), there is no decomposition. • str = sampleTest, n = 3, and length = (2, 3, 6), the program may produce sub-strings (sa, mp, le, Te, st), or sub-strings (sa, mp, leT, est), or sub-strings (sa, mpleTe, st), etc. 
    
#include 
#include 
#include 
#define MAX 1024;

void stringSplit (
  char *str,
  int n,
  int *length
  )
{
  char *s;
  int i;

  s = (char *) malloc ((strlen (str) + 1) * sizeof (char));
  if (s==NULL) {
    fprintf (stderr, "Allocation Error.
    ");
    exit (1);
  }
  for (i=0; istrlen (str)) {
    return (0);
  }

  // Termination with a solution
  if (len==strlen (str)) {
    for (i=k=0; i
    LeetCode 17번: Letter Combinations of a Phone Number
    106-LeetCode는 중차순과 후차순을 반복하여 두 갈래 트리를 구성합니다

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage