M으로 나눌 수 있는 유효한 시퀀스가 ​​있는지 확인하세요.

시퀀스는 객체의 모음입니다. 우리의 경우에는 정수의 모음입니다. 과제는 덧셈과 뺄셈 연산자를 사용하는 일련의 요소가 M으로 나누어지는지 여부를 결정하는 것입니다.

문제 설명

정수 M과 정수 배열이 주어졌습니다. 요소 간의 덧셈과 뺄셈만을 사용하여 해를 M으로 나눌 수 있는 유효한 시퀀스가 ​​있는지 확인합니다.

예 1

으아아아 으아아아

설명 - 주어진 배열에 대해 2로 나눌 수 있는 유효한 수열 {1 + 2 + 5} = {8}이 있을 수 있습니다.

예 2

으아아아 으아아아

설명 - 주어진 배열에 대해 해가 4로 나누어지는 시퀀스를 갖는 것은 불가능합니다.

방법 1: 잔혹한 방법

이 문제를 해결하는 간단한 방법은 재귀 함수를 사용하여 배열의 가능한 모든 시퀀스를 찾은 다음 M으로 나눌 수 있는 시퀀스가 ​​있는지 확인하는 것입니다.

의사코드

으아아아

예: C++ 구현

다음 프로그램에서는 재귀적 방법을 사용하여 모든 유효한 시퀀스를 찾은 다음 유효한 시퀀스가 ​​M으로 나누어지는지 확인합니다.

으아아아

출력

으아아아

시간 복잡도 - 재귀 사용으로 인한 O(2^n).

공간 복잡성 - 재귀 스택 공간으로 인해 O(n)입니다.

방법 2: 역추적

이 방법은 역추적을 사용하여 M으로 나눌 수 있는 유효한 시퀀스가 ​​없는 경로로 내려가는 것을 피하기 위해 검색 공간을 역추적할 수 있다는 점을 제외하면 이전의 무차별 재귀 방법과 유사합니다.

의사코드

으아아아

예: C++ 구현

아래 프로그램에서는 문제에 대한 해결책을 찾기 위해 역추적을 사용하여 검색 공간을 정리합니다.

으아아아

출력

으아아아

Time Complexity - 최악의 경우 시간 복잡도는 O(2^n)이지만 실제로는 검색 공간을 잘라내기 때문에 무차별 방식보다 더 좋습니다.

공간 복잡성 - 재귀 스택 공간으로 인해 O(n)입니다.

방법 3: 탐욕스러운 방법

이 문제에 대한 탐욕스러운 해결책은 먼저 배열을 오름차순으로 정렬한 다음 합계가 M을 초과하지 않는 경우 덧셈 함수를 탐욕스럽게 적용하는 것입니다. 이 방법은 전체 최적 솔루션을 제공하지 못할 수도 있지만 로컬 최적 솔루션을 제공합니다.

의사코드

으아아아

예: C++ 구현

다음 프로그램에서는 M으로 나눌 수 있는 최상의 로컬 하위 배열을 찾기 위해 배열이 정렬됩니다.

으아아아

출력

으아아아

방법 4: 동적 프로그래밍

동적 프로그래밍 개념을 사용하여 이 솔루션에서는 평가의 중간 결과를 저장합니다. N+1개의 행과 M개의 열이 있는 테이블을 생성할 것이며, 배열 요소를 사용하지 않는 경우 기본 사례는 % M == 0이 됩니다. 그런 다음 가능한 모든 나머지 모듈로 M을 반복하여 테이블을 업데이트합니다.

의사코드

으아아아

예: C++ 구현

아래 프로그램에서는 문제를 하위 문제로 나누고 해결합니다.

으아아아

출력

으아아아

결론

요약하자면, M으로 나눌 수 있는 유효한 시퀀스를 찾기 위해 무차별 대입의 경우 O(2^n)부터 동적 경우의 O(NM)에 이르기까지 다양한 방법과 다양한 관계형 및 공간 분석을 적용할 수 있습니다. 가장 효과적인 방법입니다.

위 내용은 M으로 나눌 수 있는 유효한 시퀀스가 ​​있는지 확인하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!