알고리즘 학습 의 척 취 법

어제 문 제 를 봤 는데 아마도 정수 S 를 정 하고 n 의 길이 (모든 요 소 는 정수) 에서 S 보다 작 지 않 은 연속 서브 시퀀스 의 길이 의 최소 값 을 구하 고 존재 하지 않 으 면 0 을 출력 하 라 는 것 이다.이 문제 의 소박 한 사 고 는 이 서열 의 모든 sum (i) 을 구 한 다음 에 고등학교 에서 배 운 수열 지식 a (n) = s (n) - s (n - 1) 와 같은 방법 으로 출발점 s 를 0 부터 매 거 하고 제한 sum [s] + S < = sum [n] 을 매 거 하 는 과정 에서 2 분 검색 을 통 해 서열 과 S 보다 작 지 않 은 엔 딩 t 의 최소 치 를 찾 는 것 이다. 이렇게 푸 는 시간 복잡 도 는 O (nlogn) 이다.더 빠 른 방법 이 있 지 않 을까요?여기 서 자 료 를 읽 으 면서 나 는 '척 취 법' 이라는 방법 을 배 웠 다.이런 방법 은 두 개의 아래 표 (출발점, 종점) 의 끊 임 없 는 수축 을 이용 하여 벌레 가 신축 기어 가 는 것 처럼 하 나 를 걸 어 내 는 것 이 가장 좋 은 방법 이다.이 알고리즘 은 한 번 만 옮 겨 다 니 면 답 을 구 할 수 있 기 때문에 시간 복잡 도 는 O (n) 이다.다음은 이 알고리즘 의 위조 코드 와 사고방식 을 제시한다.
  

void worm_solve()
{
    int res=MAX;
    int s=0,t=0,sum=0;
    for(;;)
     {
      while(tn)
   {
    res=0;
 }
 printf("%d
",res);
}

  이렇게 짧 습 니 다. 개인 적 으로 이해 해 보 겠 습 니 다. 이 알고리즘 의 어 려 운 점 은 어떻게 가장 잘 걸 리 는 지 하 는 것 입 니 다. 먼저 조건 을 만족 시 키 는 말단 t 의 위 치 를 찾 아야 합 니 다. 그래서 0 부터 벌레 의 머리 t 를 앞으로 기어 오 르 게 하고 꼬리 s 는 움 직 이지 않 습 니 다. 조건 을 만족 시 킬 때 까지 멈 춰 야 합 니 다. 이때 여러분 은 이 a [s]... a [t] 를 쉽게 생각 할 수 있 습 니 다.] 의 서열 에는 많은 '불필요 한 값' 이 있 을 수 있 습 니 다. 즉, 이러한 값 을 제거 한 후에 서열 의 총 계 는 S 보다 큽 니 다. 이때 우 리 는 벌레 의 꼬리 부분 을 이동 시 켜 야 합 니 다. 이동 길 이 를 확정 할 수 없 기 때문에 매번 한 단 위 를 이동 하면 됩 니 다. 꼬리 부분 이 1 로 줄 어 들 때마다 sum 에서 해당 하 는 들 여 쓰기 값 을 제거 하고 현재 의 서열 과 S 와 의 관 계 를 다시 판단 해 야 합 니 다.조건 을 어떻게 만족 시 키 면 res 를 업데이트 할 수 있 습 니까? 그렇지 않 으 면 벌레 의 머리 를 다시 전진 시 킬 수 있 습 니 다. 바로 이렇게 늘 어 나 고 줄 어 들 며 벌레 처럼 알고리즘 이 가장 좋 은 해 를 구 했 습 니 다.이 알고리즘 의 적용 유형 은 바로 연속 적 인 구간 커버 문 제 를 해결 하 는 것 이다. 이런 해법 을 보고 나 는 제호 가 머리 에 들 어 오 는 것 처럼 수학 과 산법 의 아름다움 을 다시 한 번 느 꼈 고 알고리즘 을 점점 사랑 하 게 되 었 다.